Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477786 | European Journal of Operational Research | 2007 | 14 Pages |
Abstract
This paper addresses the NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup times and no preemption where the objective is to minimize the maximum tardiness. An algorithm based on branch-and-bound permutation schemes is developed including the implementation of lower and upper bounding procedures, and three dominance rules. Computational experiments demonstrate the effectiveness of the algorithm. In the experiments, the impacts of control parameters to generate test instances on algorithm performance (CPU times) are studied by statistics methods.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Xiaochuan Luo, Chengbin Chu,