Flexible job shop scheduling with blockages
Tóm tắt
Motivated by an application in rail car maintenance, we study a variant of makespan-minimizing flexible job shop scheduling with work centers (FJc). In standard FJc a work center contains parallel machines, i.e. any machine in the work center is accessible whenever idle. In our variant, a work center consists of a linearly ordered set of machines with restricted accessibility, i.e. a busy machine blocks access to all succeeding machines. In rail car maintenance, the machines of a work center are located sequentially along a track. Therefore, a rail car waiting before or after some maintenance step can neither reach nor leave an idle machine if another rail car blocks the access path on the track. We call the resulting problem FJc with blockages. It turns out to be weakly
$$\fancyscript{N\!\!\!P}$$
-hard even for a single work center with two machines, and strongly
$$\fancyscript{N\!\!\!P}$$
-hard for a single work center. We derive a mixed integer linear optimization model, we present heuristic as well as exact solution methods, and we discuss computational results. In particular, we observe that our implementation of a branch&bound procedure is quite competitive with the commercial solvers Cplex 12.4 and Gurobi 5.0.
Tài liệu tham khảo
Alaykran K, Engin O, Döyen A (2007) Using ant colony optimization to solve hybrid flow shop scheduling problems. Int J Adv Manuf Technol 35(5):541–550
Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. The MIT Press, Cambridge
Fattahi P, Mehrabad MS, Jolai F (2007) Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J Intell Manuf 18(3):331–342
Gröflin H, Pham DN, Bürgy R (2011) The flexible blocking job shop with transfer and set-up times. Comb Optim 22(2):121–144
Haouari M, Hidri L, Gharbi A (2006) Optimal scheduling of a two-stage hybrid flow shop. Math Methods Oper Res 64(1):107–124
Hmida AB, Haouari M, Huguet M-J, Lopez P (2010) Discrepancy search for the flexible job shop scheduling problem. Comput Oper Res 37(12):2192–2201
Jansen K, Mastrolilli M, Solis-Oba R (2005) Approximation algorithms for flexible job shop problems. Int J Found Comput Sci 16(2):361–379
Jungwattanikit J, Reodecha M, Chaovalitwongse P, Werner F (2008) Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Int J Adv Manuf Technol 37(3):354–370
Kis T, Pesch E (2005) A review of exact solution methods for the non-preemptive multiprocessor flowshop problem. Eur J Oper Res 164(3):592–608
Luo H, Huang GQ, Zhang Y, Dai Q, Chen X (2009) Two-stage hybrid batching flowshop scheduling with blocking and machine constraints using genetic algorithm. Robotics Comput Integr Manuf 25(6):962–971
Mati Y, Lahlou C, Dauzere-Peres S (2011) Modelling and solving a practical flexible job-shop scheduling problem with blocking constraint. Int J Prod Res 49(8):2169–2182
Néron E, Baptiste P, Gupta JND (2001) Solving hybrid flow shop problem using energetic reasoning and global operations. Int J Manag Sci 29:501–511
Pinedo ML (2008) Scheduling: theory, algorithms, and systems. Springer, Berlin
Quadt D, Kuhn H (2007) A taxonomy of flexible flow line scheduling procedures. Eur J Oper Res 178(3):686–698
Ribas I, Leisten R, Framinan JM (2010) Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Comput Oper Res 37(8):1439–1454
Ruiz R, Vasquez-Rodriguez JA (2010) The hybrid flow shop scheduling problem. Eur J Oper Res 205(1):1–18
Tavakkoli-Moghaddam R, Safaei N, Sassani F (2009) A memetic algorithm for the flexible flow line scheduling problem with processor blocking. Comput Oper Res 36(2):402–414
Tay JC, Ho NB (2008) Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput Ind Eng 54:453–473