The single machine early/tardy problem

The single machine early/tardy problem

0.00 Avg rating0 Votes
Article ID: iaor1988982
Country: United States
Volume: 35
Issue: 2
Start Page Number: 177
End Page Number: 191
Publication Date: Feb 1989
Journal: Management Science
Authors: ,
Keywords: scheduling
Abstract:

The authors 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, the authors 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.

Reviews

Required fields are marked *. Your email address will not be published.