×

Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates. (English) Zbl 1208.90066

Summary: We address the parallel machine total weighted tardiness scheduling problem with release dates. We describe dominance rules and filtering methods for this problem. Most of them are adaptations of dominance rules based on solution methods for the single-machine problem. We show how it is possible to deduce whether or not certain jobs can be processed by a particular machine in a particular context and we describe techniques that use this information to improve the dominance rules. On the basis of these techniques we describe an enumeration procedure and we provide experimental results to determine the effectiveness of the dominance rules.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akturk, M. S.; Ozdemir, D., An exact approach to minimizing total weighted tardiness with release dates, IIE Transactions, 32, 1091-1101 (2000)
[2] Akturk, M. S.; Ozdemir, D., A new dominance rule to minimize total weighted tardiness with unequal release dates, European Journal of Operational Research, 135, 394-412 (2001) · Zbl 1051.90013
[3] Azizoglu, M.; Kirca, O., Tardiness minimization on parallel machines, International Journal of Production Economics, 55, 163-168 (1998)
[4] Baker, K. R., Introduction to sequencing and scheduling (1974), John Wiley and Sons
[5] Baptiste, Ph., Scheduling equal-length jobs on identical parallel machines, Discrete Applied Mathematics, 13, 21-32 (2000) · Zbl 0971.90027
[6] Baptiste, Ph.; Carlier, J.; Jouglet, A., A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates, European Journal of Operational Research, 158, 3, 595-608 (2004) · Zbl 1056.90054
[7] Baptiste, Ph.; Jouglet, A.; Savourey, D., Lower bounds for parallel machine scheduling problems, International Journal of Operational Research, 3, 6, 661-682 (2008)
[8] Brucker, P., Scheduling algorithms (1995), Springer Lehrbuch · Zbl 0839.90059
[9] Carlier, J., Ordonnancements à contraintes disjonctives, RAIRO, 12, 333-351 (1978) · Zbl 0401.90052
[10] Chu, C., A branch and bound algorithm to minimize total flow time with unequal release dates, Naval Research Logistics, 39, 859-875 (1992) · Zbl 0766.90039
[11] Chu, C., A branch and bound algorithm to minimize total tardiness with different release dates, Naval Research Logistics, 39, 265-283 (1992) · Zbl 0762.90035
[12] Chu, C.; Portmann, M.-C., Some new efficients methods to solve the \(n | 1 | r_i | \sum T_i\), European Journal of Operational Research, 58, 404-413 (1991) · Zbl 0760.90055
[13] Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of scheduling (1967), Addison-Wesley: Addison-Wesley Reading · Zbl 1058.90500
[14] Ignall, E.; Schrage, L., Applications of the branch-and-bound technique to some flow-shop scheduling problems, Operations Research, 13, 400-412 (1965)
[15] Jouglet, A.; Baptiste, Ph.; Carlier, J., Branch-and-bound algorithms for total weighted tardiness, (Leung, J. Y.-T., Handbook of scheduling: algorithms models and performance analysis, vol. 13 (2004), Chapman & Hall/CRC edition), 1-21
[16] Jouglet, A.; Savourey, D.; Carlier, J.; Baptiste, Ph., Dominance-based heuristics for one-machine total cost scheduling problems, European Journal of Operational Research, 184, 3, 879-899 (2008) · Zbl 1141.90019
[17] Kohler, W. H.; Steiglitz, K., Enumerative and iterative computational approaches, (Coffman, E. G., Computer and job-shop scheduling theory, vol. 6 (1976), John Wiley & Sons), 229-287
[18] Lenstra, J.; Kan, A. R.; Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362 (1977)
[19] Liaw, C.-F.; Lin, Y.-K.; Cheng, C.-Y.; Chen, M., Scheduling unrelated parallel machines to minimize total weighted tardiness, Computers & Operations Research, 1777-1789 (2003) · Zbl 1047.90021
[20] Mitten, L., Branch-and-bound methods: general formulation and properties, Operations Research, 18, 1, 24-34 (1970) · Zbl 0225.90030
[21] Nessah, R.; Yalaoui, F.; Chu, C., A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates, Computers & Operations Research, 35, 4, 1176-1190 (2008) · Zbl 1180.90133
[22] Savourey D. Ordonnancement sur machines parallèles: minimiser la somme des coûts. PhD thesis, Université de Technologie de Compiègne, France; 2006.; Savourey D. Ordonnancement sur machines parallèles: minimiser la somme des coûts. PhD thesis, Université de Technologie de Compiègne, France; 2006.
[23] Shim, S.-O.; Kim, Y.-D., Scheduling on parallel identical machines to minimize total tardiness, European Journal of Operational Research, 135-146 (2007) · Zbl 1111.90046
[24] Walker, R., An enumerative technique for a class of combinatorial problems, American Mathematical Society Symposia in Applied Mathematics, 10, 91-94 (1960)
[25] Yalaoui, F.; Chu, C., Parallel machine scheduling to minimize total tardiness, International Journal of Production Economics, 76, 265-279 (2002)
[26] Yalaoui, F.; Chu, C., New exact method to solve the \(Pm | r_i | \sum C_i\) problem, International Journal of Production Economics, 100, 1, 168-179 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.