Job-shop scheduling with blocking and no-wait constraints. (English) Zbl 1082.90528

Summary: We study the job-shop scheduling problem with blocking and/or no-wait constraints. A blocking constraint models the absence of storage capacity between machines, while a no-wait constraint occurs when two consecutive operations in a job must be processed without any interruption. We formulate the problem by means of a generalization of the disjunctive graph of Roy and Sussman, that we call an alternative graph, and investigate the applicability to the blocking and no-wait cases of some of the most effective ideas from the literature on the job shop with unlimited buffers. We show that several key properties, used to design heuristic procedures, do not hold in the blocking and no-wait cases, while some of the most effective ideas used to develop branch and bound algorithms can be easily extended. We presents several complexity results and solution procedures. Computational results for fast heuristics and exact algorithms are also reported.


90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization


Full Text: DOI


[1] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Management science, 34, 3, 391-401, (1988) · Zbl 0637.90051
[2] Adenso-Dı́az, B.; Oliva González, M.; González-Torre, P., On-line timetable re-scheduling in regional train services, Transportation research part B, 33, 387-398, (1999)
[3] Applegate, D.; Cook, W., A computational study of the job shop scheduling problem, ORSA journal on computing, 3, 2, 149-156, (1991) · Zbl 0755.90039
[4] Arbib, C.; Italiano, G.F.; Panconesi, A., Predicting deadlock in store-and-forward networks, Networks, 20, 861-881, (1990) · Zbl 0718.68009
[5] Arbib, C.; Pacciarelli, D.; Smriglio, S., A three-dimensional matching model for perishable production scheduling, Discrete applied mathematics, 92, 1-15, (1999) · Zbl 0917.90184
[6] Balas, E., Machine sequencing via disjunctive graphs: an implicit enumeration approach, Operations research, 17, 941-957, (1969) · Zbl 0183.49404
[7] Balas, E., Disjunctive programming, Annals of discrete mathematics, 5, 3-51, (1979) · Zbl 0409.90061
[8] Brucker, P.; Jurish, B.; Sievers, B., A branch and bound algorithm for the job-shop scheduling problem, Discrete applied mathematics, 49, 107-127, (1994) · Zbl 0802.90057
[9] Cai, X.; Goh, C.J.; Mees, A.I., Greedy heuristics for rapid scheduling of trains on a single track, IIE transactions, 30, 481-493, (1998)
[10] Carlier, J., The one-machine sequencing problem, European journal of operational research, 11, 42-47, (1982) · Zbl 0482.90045
[11] Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Management science, 35, 2, 164-176, (1989) · Zbl 0677.90036
[12] Carlier, J.; Pinson, E., A practical use of Jackson’s preemptive schedule for solving the job-shop problem, Annals of operations research, 26, 269-287, (1990) · Zbl 0709.90061
[13] Carlier, J.; Pinson, E., Adjustment of heads and tails for the job-shop problem, European journal of operational research, 78, 146-161, (1994) · Zbl 0812.90063
[14] Della Croce, F.; Tadei, R.; Volta, G., A genetic algorithm for the job-shop problem, Computers and operations research, 22, 1, 15-30, (1995) · Zbl 0816.90081
[15] Dell’Amico, M.; Trubian, M., Applying taboo search to the job-shop scheduling problem, Annals of operations research, 41, 231-252, (1993) · Zbl 0771.90056
[16] Dorn, J.; Shams, R., Scheduling high-grade steelmaking, IEEE expert, 11, 1, 28-35, (1996)
[17] French, S., Sequencing and scheduling: an introduction to the mathematics of the job shop, (1982), Ellis Horwood Chichester, UK · Zbl 0479.90037
[18] Grabowski, J.; Pempera, J.; Smutnicki, C., Scheduling in production of concrete wares, (), 192-196 · Zbl 0918.90082
[19] Hall, N.J.; Sriskandarajah, C., A survey on machine scheduling problems with blocking and no-wait in process, Operations research, 44, 3, 510-525, (1996) · Zbl 0864.90060
[20] Kubiak, W.; Sethi, S.; Sriskandarajah, C., An efficient algorithm for a job shop problem, Mathematical industrial systems, 1, 203-216, (1996) · Zbl 0838.90064
[21] Lawrence, S., Supplement to resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques, (1984), GSIA, Carnegie Mellon University Pittsburgh, PA
[22] Lixin, T.; Liu, J.; Rong, A.; Yang, Z., A mathematical programming model for scheduling steelmaking-continuous casting production, European journal of operational research, 120, 423-435, (2000) · Zbl 0955.90035
[23] Martin, P.; Shmoys, D.B., A new approach to compute optimal schedules for the job shop scheduling problem, (), 389-403
[24] A. Mascis, D. Pacciarelli, Machine scheduling via alternative graphs, Report DIA-46-2000, Dipartimento di Informatica e Automazione, Università Roma Tre, Roma, Italy, 2000 · Zbl 1082.90528
[25] Mc Cormick, S.T.; Pinedo, M.L.; Shenker, S.; Wolf, B., Sequencing in an assembly line with blocking to minimize cycle time, Operations research, 37, 6, 925-935, (1989) · Zbl 0689.90048
[26] ()
[27] Nahmias, S., Perishable inventory theory: A review, Operations research, 30, 4, 680-708, (1982) · Zbl 0486.90033
[28] Nowicki, E., The permutation flow shop with buffers: A tabu search approach, European journal of operational research, 116, 1, 205-219, (1999) · Zbl 1009.90039
[29] Nowicki, E.; Smutnicki, C., A fast taboo search algorithm for the job shop scheduling problem, Management science, 42, 6, 797-813, (1996) · Zbl 0880.90079
[30] Ovacik, I.M.; Uzsoy, R., Decomposition methods for complex factory scheduling problems, (1997), Prentice-Hall Englewood Cliffs, NJ · Zbl 0901.90132
[31] Papadimitriou, C.; Kanellakis, P., Flowshop scheduling with limited temporary storage, Journal of associated computer machinery, 27, 533-549, (1980) · Zbl 0475.68014
[32] Pinedo, M., Scheduling – theory, algorithms and systems, (1995), Prentice-Hall (International Series in Industrial and System Engineering) Englewood Cliffs, NJ · Zbl 1145.90393
[33] Pinson, E., The job shop scheduling problem: A concise survey and some recent developments, (), 277-294
[34] Reklaitis, G.V., Review of scheduling of process operations, Aiche symposium series, 78, 119-133, (1982)
[35] B. Roy, B. Sussman, Les problèm d’ordonnancement avec contraintes disjonctives. Note DS No. 9 bis, SEMA, Paris, 1964
[36] Şahin, İ., Railway traffic control and train scheduling based on inter-train conflict management, Transportation research part B, 33, 511-534, (1999)
[37] 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-467, (1995) · Zbl 0843.90059
[38] Taillard, E., Parallel tabu search technique for the job shop scheduling problem, ORSA journal on computing, 6, 108-117, (1994) · Zbl 0807.90066
[39] Timkovsky, V.G., On the complexity of scheduling an arbitrary system, Soviet journal of computer and system sciences, 5, 46-52, (1985) · Zbl 0586.90055
[40] van Laarhoven, P.J.M.; Aarts, E.H.L.; Lenstra, J.K., Job shop scheduling by simulated annealing, Operations research, 40, 113-125, (1992) · Zbl 0751.90039
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.