Branch and Bound Algorithms for Single Machine Scheduling with Batching to Minimize the Number of Late Jobs |
| |
Authors: | H?A?J?Crauwels C?N?Potts Email author" target="_blank">D?Van?OudheusdenEmail author L?N?Van Wassenhove |
| |
Affiliation: | (1) De Nayer instituut, J. De Nayerlaan 5, 2860 Sint-Katelijne-Waver, Belgium;(2) Faculty of Mathematical Studies, University of Southampton, Southampton, SO17 1BJ, UK;(3) Centrum voor Industrieel Beleid, Celestijnenlaan 300 A, 3001 Leuven, Belgium;(4) INSEAD, Boulevard de Constance, 77305 Fontainebleau, France |
| |
Abstract: | This paper considers the problem of scheduling a single machine to minimize the number of late jobs in the presence of sequence-independent family set-up times. The jobs are partitioned into families, and a set-up time is required at the start of each batch, where a batch is a maximal set of jobs in the same family that are processed consecutively. We design branch and bound algorithms that have several alternative features. Lower bounds can be derived by relaxing either the set-up times or the due dates. A first branching scheme uses a forward branching rule with a depth-first search strategy. Dominance criteria, which determine the order of the early jobs within each family and the order of the batches containing early jobs, can be fully exploited in this scheme. A second scheme uses a ternary branching rule in which the next job is fixed to be early and starting a batch, to be early and not starting a batch, or to be late. The different features are compared on a large set of test problems, where the number of jobs ranges from 30 to 50 and the number of families ranges from 4 to 10. |
| |
Keywords: | scheduling single machine batches families set-up time branch and bound |
本文献已被 SpringerLink 等数据库收录! |
|