Cyclic job shop scheduling problems with blocking. (English) Zbl 1151.90397
Summary: A tabu search algorithm for a cyclic job shop problem with blocking is presented. Operations are blocking if they must stay on a machine after finishing when the next machine is occupied by another job. During this stay the machine is blocked for other jobs. For this problem traditional tabu search moves often lead to infeasible solutions. Recovering procedures are developed which construct nearby feasible solutions. Computational results are presented for the approach.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Beasley, J. E. (2005). Benchmark problems. http://people.brunel.ac.uk/\(\sim\)mastjjb/jeb/info.html . |
| [2] | Brucker, P. (2004). Scheduling algorithms (4th edn.) Berlin: Springer. · Zbl 1060.90034 |
| [3] | Brucker, P., & Kampmeyer, T. (2005). Tabu search algorithms for cyclic machine scheduling problems. Journal of Scheduling, 8, 303–322. · Zbl 1123.90018 · doi:10.1007/s10951-005-1639-4 |
| [4] | Brucker, P., & Kampmeyer, T. (2007, to appear). A general model for cyclic machine scheduling problems. Discrete Applied Mathematics. · Zbl 1152.90430 |
| [5] | Carlier, J., & Chrétienne, P. (1988). Les Problèmes d’ordonnancement. Paris: Masson. · Zbl 0774.90043 |
| [6] | Dasdan, A., Irani, S. S., & Gupta, R. K. (1999). 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 (pp. 37–42). Annual ACM IEEE design automation conference, NY, USA. New York: ACM. |
| [7] | Glover, F. (1989). Tabu search. I. ORSA Journal on Computing, 1, 190–206. · Zbl 0753.90054 |
| [8] | Glover, F. (1990). Tabu search. II. ORSA Journal on Computing, 2, 4–32. · Zbl 0771.90084 |
| [9] | Hanen, C. (1994). Study of a NP-hard cyclic scheduling problem: the recurrent job-shop. European Journal of Operations Research, 72, 82–101. · Zbl 0801.90061 · doi:10.1016/0377-2217(94)90332-8 |
| [10] | Kampmeyer, T. (2006). Cyclic scheduling problems. Ph.D. thesis, University of Osnabrück. · Zbl 1197.90004 |
| [11] | Mascis, A., & Pacciarelli, D. (2002). Job-shop scheduling with blocking and no-wait constraints. European Journal of Operations Research, 143, 498–517. · Zbl 1082.90528 · doi:10.1016/S0377-2217(01)00338-1 |
| [12] | McCormick, S. T., Pinedo, M., Shenker, S., et al. (1989). Sequencing in an assembly line with blocking to minimize cycle time. Operations Research, 37(6), 925–935. · Zbl 0689.90048 · doi:10.1287/opre.37.6.925 |
| [13] | Nieberg, T. (2002). Tabusuche für Flow-Shop und Job-Shop Probleme mit begrenztem Zwischenspeicher. Master’s thesis, University of Osnabrück. |
| [14] | Song, J. S., & Lee, T. E. (1998). Petri net modeling and scheduling for cyclic job shops with problems. Computers Industrial Engineering, 34(2), 281–295. · doi:10.1016/S0360-8352(97)00325-2 |
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.
