The Single Machine Early/Tardy Problem

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs. Two dispatch priority rules are proposed and tested for this NP-complete problem. These were found to perform far better than known heuristics that ignored early costs. For situations where the potential cost savings are sufficiently high to justify more sophisticated techniques, we propose a variation of the Beam Search method developed by researchers in artificial intelligence. This variant, called Filtered Beam Search, is able to use priority functions to search a number of solution paths in parallel. A computational study showed that this search method was not only efficient but also consistent in providing near-optimal solutions with a relatively small search tree. The study also includes an investigation of the impacts of Beam Search parameters on three variations of Beam Search for this problem.

• 저널Management Science · 35(2) · 177–191
• 토픽Scheduling and Optimization Algorithms · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.35.2.177
• 저자Peng Si Ow, Thomas E. Morton