Effective dynamic dispatching rule and constructive heuristic for solving single-machine scheduling problems with a common due window

Abstract

This study addresses the single-machine scheduling problem with a common due window (CDW) that has a constant size and position. The objective is to minimise the total weighted earliness–tardiness penalties for jobs completed out of the CDW. To determine a schedule as close to optimum as possible, this study develops a dynamic dispatching rule and an effective constructive heuristic. The better performance of the proposed heuristic is demonstrated by comparing the results of it with those of a state-of-the-art greedy heuristic on a well-known benchmark problem set. In addition, we incorporate the constructive heuristic into a best-so-far meta-heuristic to examine the benefit of the proposed heuristic. The results show that the best known solutions in 144 out of the 250 benchmark instances are improved.

Keywords:

• scheduling
• heuristics
• common due window
• dispatching rule

Acknowledgements

The first and corresponding authors of the work are grateful to the Ministry of Science and Technology, Republic of China (Taiwan) for financially supporting this research with projects: MOST104-2221-E-027-045 and NSC 102-2410-H-027-011-MY3, respectively. The second author is grateful to the Ministry of Science and Technology, Republic of China (Taiwan) and the Linkou Chang Gung Memorial Hospital for financially supporting this research grants MOST104-2410-H-182-011 and BMRPA19, respectively.