×

Algorithms for single machine total tardiness scheduling with sequence dependent setups. (English) Zbl 1142.90399

Summary: We consider the problem of scheduling a single machine to minimize total tardiness with sequence dependent setup times. We present two algorithms, a problem space-based local search heuristic and a Greedy Randomized Adaptive Search Procedure (GRASP) for this problem. With respect to GRASP, our main contributions are – a new cost function in the construction phase, a new variation of Variable Neighborhood Search in the improvement phase, and Path Relinking using three different search neighborhoods. The problem space-based local search heuristic incorporates local search with respect to both the problem space and the solution space. We compare our algorithms with Simulated Annealing, Genetic Search, Pairwise Interchange, Branch and Bound and Ant Colony Search on a set of test problems from literature, showing that the algorithms perform very competitively.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Conway, R.; Maxwell, W.; Miller, L., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500
[2] Allahverdi, A.; Gupta, J. N.; Aldowaisan, T., A review of scheduling research involving setup considerations, Omega, 27, 219-239 (1999)
[3] Panwalkar, S.; Dudek, R.; Smith, M., Sequencing research and the industrial scheduling problem, (Beckmann, M.; Goos, P.; Zurich, H., Symposium on the Theory of Scheduling and Its Applications (1973), Springer-Verlag: Springer-Verlag New York), 29-38 · Zbl 0269.90025
[4] Kim, S.; Bobrowski, P., Impact of sequence dependent setup time on job shop scheduling performance, International Journal of Production Research, 32, 7, 1503-1520 (1994) · Zbl 0901.90130
[5] Du, J.; Leung, J. Y.-T., Minimizing total tardiness on one machine is np-hard, Mathematics of Operations Research, 15, 483-495 (1990) · Zbl 0714.90052
[6] Koulamas, C., The total tardiness problem: Review and extensions, Operations Research, 42, 1025-1041 (1994) · Zbl 0824.90083
[7] Graham, R.; Lawler, E.; Lenstra, J.; Kan, A. R., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044
[8] Tan, K.-C.; Narasimhan, R.; Rubin, P. A.; Ragatz, G. L., A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times, Omega, 28, 313-325 (2000)
[9] K.R. Baker, Elements of sequencing and scheduling, Tuck School of Business, Dartmouth College, Hanover, 2002.; K.R. Baker, Elements of sequencing and scheduling, Tuck School of Business, Dartmouth College, Hanover, 2002.
[10] G.L. Ragatz, A branch and bound method for minimum tardiness sequencing on a single processor with sequence dependent setup times, in: Proceedings of the Twenty Fourth Annual Meeting of the Decision Sciences Institute, 1993, pp. 1375-1377.; G.L. Ragatz, A branch and bound method for minimum tardiness sequencing on a single processor with sequence dependent setup times, in: Proceedings of the Twenty Fourth Annual Meeting of the Decision Sciences Institute, 1993, pp. 1375-1377.
[11] Rubin, P. A.; Ragatz, G. L., Scheduling in a sequence dependent setup environment with genetic search, Computers and OR, 22, 1, 85-99 (1995) · Zbl 0813.90065
[12] Tan, K.-C.; Narasimhan, R., Minimizing tardiness on a single processor with sequence dependent setup times: a simulated annealing approach, Omega, 25, 6, 619-634 (1997)
[13] Lee, Y.; Bhaskran, K.; Pinedo, M., A heuristic to minimize total weighted tardiness with sequence dependent setups, IIE Transactions, 29, 1, 45-52 (1997)
[14] França, P. M.; Mendes, A.; Moscato, P., Theory and methodology: A memetic algorithm for the total tardiness single machine scheduling problem, European Journal of Operational Research, 132, 224-242 (2001) · Zbl 0996.90042
[15] Gagné, C.; Price, W.; Gravel, M., Comparing an aco algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times, Journal of the Operational Research Society, 53, 895-906 (2002) · Zbl 1130.90326
[16] Desrosiers, J.; Dumas, Y.; Solomon, M.; Soumis, F., Chapter 2: Time constrained routing and scheduling, (Ball, M.; Magnanti, T.; Monma, C.; Nemhauser, G., Handbooks in Operations Research and Management Science. Handbooks in Operations Research and Management Science, Network Routing, vol. 8 (1995), North-Holland: North-Holland Amsterdam, The Netherlands), 35-139 · Zbl 0861.90052
[17] Resende, M. G.; Ribeiro, C. C., Chapter 8: Greedy randomized adaptive search procedures, (Glover, F. W.; Kochenberger, G. A., Handbook of Metaheuristics. Handbook of Metaheuristics, International Series in Operations Research and Management Science, vol. 57 (2002), Kluwer Academic Publishers) · Zbl 1102.90384
[18] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers and OR, 24, 11, 1097-1100 (1997) · Zbl 0889.90119
[19] C. Blum, A. Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, Tech. Rep. TR/IRIDIA/2001-13, IRIDIA, Université Libre de Bruxelles, Belgium, October 2001.; C. Blum, A. Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, Tech. Rep. TR/IRIDIA/2001-13, IRIDIA, Université Libre de Bruxelles, Belgium, October 2001.
[20] I. Or, Travelling salesman-type combinatorial problems and their relation to the logistics of blood banking, Ph.D. thesis, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, 1976.; I. Or, Travelling salesman-type combinatorial problems and their relation to the logistics of blood banking, Ph.D. thesis, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, 1976.
[21] Storer, R. H.; Wu, S. D.; Vaccari, R., New search spaces for sequencing problems with application to job shop scheduling, Management Science, 38, 10, 1495-1509 (1992) · Zbl 0759.90048
[22] Storer, R. H.; Wu, S. D.; Vaccari, R., Problem and heuristic space search strategies for job shop scheduling, ORSA Journal on Computing, 7, 4, 453-487 (1995) · Zbl 0843.90059
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.