×

A neighborhood for complex job shop scheduling problems with regular objectives. (English) Zbl 1375.90120

Summary: Due to the limited applicability in practice of the classical job shop scheduling problem, many researchers have addressed more complex versions of this problem by including additional process features, such as time lags, setup times, and buffer limitations, and have pursued objectives that are more practically relevant than the makespan, such as total flow time and total weighted tardiness. However, most proposed solution approaches are tailored to the specific scheduling problem studied and are not applicable to more general settings. This article proposes a neighborhood that can be applied for a large class of job shop scheduling problems with regular objectives. Feasible neighbor solutions are generated by extracting a job from a given solution and reinserting it into a neighbor position. This neighbor generation in a sense extends the simple swapping of critical arcs, a mechanism that is widely used in the classical job shop but that is not applicable in more complex job shop problems. The neighborhood is embedded in a tabu search, and its performance is evaluated with an extensive experimental study using three standard job shop scheduling problems: the (classical) job shop, the job shop with sequence-dependent setup times, and the blocking job shop, combined with the following five regular objectives: makespan, total flow time, total squared flow time, total tardiness, and total weighted tardiness. The obtained results support the validity of the approach.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

Software:

Tabu search; JOBSHOP
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Applegate, D., & Cook, W. (1991). A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3(2), 149-156. · Zbl 0755.90039 · doi:10.1287/ijoc.3.2.149
[2] Balas, E., Simonetti, N., & Vazacopoulos, A. (2008). Job shop scheduling with setup times, deadlines and precedence constraints. Journal of Scheduling, 11(4), 253-262. · Zbl 1168.90419 · doi:10.1007/s10951-008-0067-7
[3] Blazewicz, J., Domschke, W., & Pesch, E. (1996). The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 93(1), 1-33. · Zbl 0980.90024 · doi:10.1016/0377-2217(95)00362-2
[4] Brucker, P., & Knust, S. (2011). Complex scheduling (2nd ed.). Berlin: Springer. · Zbl 1154.90002
[5] Brucker, P., & Thiele, O. (1996). A branch and bound method for the general-shop problem with sequence dependent setup-times. OR Spectrum, 18(3), 145-161. · Zbl 0852.90087 · doi:10.1007/BF01539706
[6] Brucker, P., Jurisch, B., & Sievers, B. (1994). A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49(1), 107-127. · Zbl 0802.90057 · doi:10.1016/0166-218X(94)90204-6
[7] Bülbül, K., & Kaminsky, P. (2013). A linear programming-based method for job shop scheduling. Journal of Scheduling, 16(2), 161-183. · Zbl 1280.90035 · doi:10.1007/s10951-012-0270-4
[8] Bürgy, R. (2014). Complex Job Shop Scheduling: A General Model and Method. PhD thesis, Department of Informatics, University of Fribourg. · Zbl 1280.90035
[9] Bürgy, R., & Gröflin, H. (2016). The blocking job shop with rail-bound transportation. Journal of Combinatorial Optimization, 31(1), 151-181. · Zbl 1338.90161 · doi:10.1007/s10878-014-9723-3
[10] Eilon, S., & Hodgson, R. (1967). Job shops scheduling with due dates. International Journal of Production Research, 6(1), 1-13. · doi:10.1080/00207546708929764
[11] Glover, F. W., & Laguna, M. (1997). Tabu search. Norwell: Kluwer. · Zbl 0930.90083 · doi:10.1007/978-1-4615-6089-0
[12] Gonçalves, J. F., & Resende, M. G. C. (2014). An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling. International Transactions in Operational Research, 21(2), 215-246. · Zbl 1291.90093 · doi:10.1111/itor.12044
[13] González, M. A., Vela, C. R., Sierra, M., Varela, R. (2010). Tabu search and genetic algorithm for scheduling with total flow time minimization. In COPLAS 2010: ICAPS Workshop on constraint satisfaction techniques for planning and scheduling problems (pp. 33-41). · Zbl 1251.68202
[14] González, M. Á., González-Rodríguez, I., Vela, C. R., & Varela, R. (2012a). An efficient hybrid evolutionary algorithm for scheduling with setup times and weighted tardiness minimization. Soft Computing, 16(12), 2097-2113. · doi:10.1007/s00500-012-0880-y
[15] González, M. A., Vela, C. R., & Varela, R. (2012b). A competent memetic algorithm for complex scheduling. Natural Computing, 11(1), 151-160. · Zbl 1251.68202 · doi:10.1007/s11047-011-9300-y
[16] Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287-326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[17] Grimes, D., & Hebrard, E. (2015). Solving variants of the job shop scheduling problem through conflict-directed search. INFORMS Journal on Computing, 27(2), 268-284. · Zbl 1329.90061 · doi:10.1287/ijoc.2014.0625
[18] Gröflin, H., & Klinkert, A. (2007). Feasible insertions in job shop scheduling, short cycles and stable sets. European Journal of Operational Research, 177(2), 763-785. · Zbl 1102.90021 · doi:10.1016/j.ejor.2005.12.025
[19] Gröflin, H., & Klinkert, A. (2009). A new neighborhood and tabu search for the blocking job shop. Discrete Applied Mathematics, 157(17), 3643-3655. · Zbl 1185.90076 · doi:10.1016/j.dam.2009.02.020
[20] Gröflin, H., Pham, D. N., & Bürgy, R. (2011). The flexible blocking job shop with transfer and set-up times. Journal of Combinatorial Optimization, 22(2), 121-144. · Zbl 1226.90036 · doi:10.1007/s10878-009-9278-x
[21] Hooker, J. N. (1995). Testing heuristics: We have it all wrong. Journal of Heuristics, 1(1), 33-42. · Zbl 0853.68155
[22] Lawrence, S. (1984). Supplement to resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques. Pittsburgh, PA: GSIA: Carnegie Mellon University.
[23] Mascis, A., & Pacciarelli, D. (2002). Job-shop scheduling with blocking and no-wait constraints. European Journal of Operational Research, 143(3), 498-517. · Zbl 1082.90528 · doi:10.1016/S0377-2217(01)00338-1
[24] Mati, Y., Dauzère-Pérès, S., & Lahlou, C. (2011). A general approach for optimizing regular criteria in the job-shop scheduling problem. European Journal of Operational Research, 212(1), 33-42. · Zbl 1237.90093 · doi:10.1016/j.ejor.2011.01.046
[25] Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management Science, 42(6), 797-813. · Zbl 0880.90079 · doi:10.1287/mnsc.42.6.797
[26] Nowicki, E., & Smutnicki, C. (2005). An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8(2), 145-159. · Zbl 1154.90479 · doi:10.1007/s10951-005-6364-5
[27] Oddi, A., Rasconi, R., Cesta, A., Smith, S. F. (2012). Iterative improvement algorithms for the blocking job shop. In Twenty-second international conference on automated planning and scheduling. · Zbl 1267.68217
[28] Peng, B., Lü, Z., & Cheng, T. C. E. (2015). A tabu search/path relinking algorithm to solve the job shop scheduling problem. Computers and Operations Research, 53, 154-164. · Zbl 1348.90298 · doi:10.1016/j.cor.2014.08.006
[29] Perregaard, M., & Clausen, J. (1998). Parallel branch-and-bound methods for the job-shop scheduling problem. Annals of Operations Research, 83, 137-160. · Zbl 0911.90218 · doi:10.1023/A:1018903912673
[30] Pinedo, M. L. (2012). Scheduling: Theory, algorithms, and systems (4th ed.). Berlin: Springer. · Zbl 1239.90002 · doi:10.1007/978-1-4614-2361-4
[31] Potts, C. N., & Strusevich, V. A. (2009). Fifty years of scheduling: A survey of milestones. Journal of the Operational Research Society, 60, S41-S68. · Zbl 1168.90311 · doi:10.1057/jors.2009.2
[32] Pranzo, M., Pacciarelli, D. (2015). An iterated greedy metaheuristic for the blocking job shop scheduling problem. Journal of Heuristics, 22(4), 587-611.
[33] Taillard, E. (1994). Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing, 6, 108-108. · Zbl 0807.90066 · doi:10.1287/ijoc.6.2.108
[34] Tufte, E. R. (2001). The visual display of quantitative information (2nd ed.). Norwich: Bertrams.
[35] Vela, C., Varela, R., & González, M. (2010). Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times. Journal of Heuristics, 16, 139-165. · Zbl 1184.90064 · doi:10.1007/s10732-008-9094-y
[36] Zhang, C. Y., Li, P., Rao, Y., & Guan, Z. (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers and Operations Research, 35(1), 282-294. · Zbl 1149.90345 · doi:10.1016/j.cor.2006.02.024
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.