×

Tabu search algorithms for cyclic machine scheduling problems. (English) Zbl 1123.90018

Summary: Tabu search algorithms are developed for solving a large class of cyclic machine scheduling problems with the objective to minimize the cycle time. Neighborhoods are derived which generalize the block-approach based neighborhoods which have been successfully applied to noncyclic job-shop problems. For a variant of this neighborhood opt-connectivity is proved.
The tabu-search procedure is applied to cyclic job-shop scheduling problems. Computational results are presented.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

PESPLib
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allan, V., R. Jones, R. Lee, and S. Allan, ”Software pipelining,” ACM Computing Surveys, 27(3), 367–432 (1995). · doi:10.1145/212094.212131
[2] Beasley, J. E. ”Benchmark problems,” http://people.brunel.ac.uk/\(\sim\)mastjjb/jeb/info.html.
[3] Brucker, P. Scheduling Algorithms. Springer-Verlag, Berlin, fourth edition, 2004. · Zbl 1060.90034
[4] Carlier, J. and P. Chretienne, ”Les Problémes d’Ordonnancement,” Technical report, Masson, Paris, 1988. · Zbl 0494.90040
[5] Cohen, G., D. Dubois, J. P. Quadrat, and M. Viot, ”A linear system theretic view of discrete event process and its use for performance evaluation in manufacturing,” IEEE Transactions on Automatic Control, 30(2), 210–220 (1985). · Zbl 0557.93005 · doi:10.1109/TAC.1985.1103925
[6] Dasdan, A., S. S. Irani, and R. K. Gupta. ”Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems,” in Proceedings of the 36th ACM/IEEE Conference on Design Automation Conference, Annual ACM IEEE Design Automation Conference, ACM Press New York, NY, USA, 1999, pp. 37–42.
[7] Glover, F. ”Tabu search I,” ORSA Journal on Computing, 1, 190–206 (1989). · Zbl 0753.90054
[8] Glover, F. ”Tabu search II,” ORSA Journal on Computing, 2, 4–32 (1990). · Zbl 0771.90084
[9] Hall, N. G., T. E. Lee, and M. E. Posner, ”The complexity of cyclic shop scheduling problems,” Journal of Scheduling, 5(4), 307–327 (2002). · Zbl 1009.90048 · doi:10.1002/jos.100
[10] Hanen, C. ”Study of a NP-hard cyclic scheduling problem: The recurrent job-shop,” European Journal of Operational Research, 72, 82–101 (1994). · Zbl 0801.90061 · doi:10.1016/0377-2217(94)90332-8
[11] Hanen, C. and A. Munier, ”Cyclic scheduling on parallel processors: on overview,” chapter 4. In P. Chretienne, E. G. Coffman, J. K. Lentra, and Z. Liu (eds.), Scheduling Theory and Its Applications, Wiley, New York, 1995. · Zbl 0830.68009
[12] Hanen, C. and A. Munier, ”A study of the cyclic scheduling problem on parallel processors,” Discrete Applied Mathematics, 57(2–3), 167–192 (1995). · Zbl 0830.68009 · doi:10.1016/0166-218X(94)00102-J
[13] Korst, J., ”Periodic multiprocessor scheduling,” PhD thesis, TU Eindhoven, 1992. · Zbl 0765.90055
[14] Lee, T. and M. Posner, ”Performance measures and schedules in periodic job shop,” Operations Research, 45, 72–91 (1997). · Zbl 0892.90102 · doi:10.1287/opre.45.1.72
[15] Rau, B. R. and J. A. Fisher, ”Instruction-level parallel processing: History, overview and perspective,” Journal of Supercomputing, 7, 9–50 (1993). · Zbl 05917080 · doi:10.1007/BF01205181
[16] Roundy, R., ”Cyclic schedules for job-shops with identical jobs,” Mathematics of Operations Research, 17, 842–865 (1992). · Zbl 0770.90036 · doi:10.1287/moor.17.4.842
[17] Serafini, P. and W. Ukovich, ”A mathematical model for periodic scheduling problems,” SIAM Journal of Discrete Mathematics, 2(4), 550–581 (1986). · Zbl 0676.90030 · doi:10.1137/0402049
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.