nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Logic-Based Benders Decomposition for Two-Stage Flexible Flow Shop Scheduling with Unrelated Parallel Machines

verfasst von : Yingcong Tan, Daria Terekhov

Erschienen in: Advances in Artificial Intelligence

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study a two-stage flexible flow shop scheduling problem (FFSP) with the objective of makespan minimization. There is a single machine in stage 1 and unrelated parallel machines in stage 2. We propose a logic-based Benders decomposition (LBBD) algorithm, which decomposes this problem into a mixed-integer programming (MIP) master problem that sequences jobs on stage 1 and assigns jobs to machines on stage 2, and a set of constraint programming sub-problems that aim to find a feasible schedule on stage 2. Extensive computational results show that LBBD outperforms the best-known MIP model for this problem in terms of both computational time and ability to prove optimality over the majority of test instances. Additional experiments show that the superiority of LBBD over the monolithic MIP model holds regardless of whether algorithm tuning features are applied.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Synthesizing Controllers: On the Correspondence Between LTL Synthesis and Non-deterministic Planning

Nächstes Kapitel Advice-Based Exploration in Model-Based Reinforcement Learning

Beck, J.C.: Checking-up on branch-and-check. In: Cohen, D. (ed.) CP 2010. LNCS, vol. 6308, pp. 84–98. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15396-9_10CrossRef

Bülbül, K., Şen, H.: An exact extended formulation for the unrelated parallel machine total weighted completion time problem. J. Sched. 20(4), 373–389 (2017)MathSciNetCrossRefMATH

Camm, J.D., Raturi, A.S., Tsubakitani, S.: Cutting big \(M\) down to size. Interfaces 20(5), 61–66 (1990)CrossRef

Ciré, A.A., Coban, E., Hooker, J.N.: Logic-based Benders decomposition for planning and scheduling: a computational analysis. Knowl. Eng. Rev. 31(5), 440–451 (2016)CrossRefMATH

Demir, Y., İşleyen, S.K.: Evaluation of mathematical models for flexible job-shop scheduling problems. Appl. Math. Model. 37(3), 977–988 (2013)MathSciNetCrossRefMATH

Dessouky, M.M., Dessouky, M.I., Verma, S.K.: Flowshop scheduling with identical jobs and uniform parallel machines. Eur. J. Oper. Res. 109(3), 620–631 (1998)CrossRefMATH

Fei, H., Meskens, N., Chu, C.: A planning and scheduling problem for an operating theatre using an open scheduling strategy. Comput. Ind. Eng. 58(2), 221–230 (2010)CrossRef

Gupta, J.N., Tunc, E.A.: Schedules for a two-stage hybrid flowshop with parallel machines at the second stage. Int. J. Prod. Res. 29(7), 1489–1502 (1991)CrossRef

Heching, A., Hooker, J.N.: Scheduling home hospice care with logic-based Benders decomposition. In: Quimper, C.-G. (ed.) CPAIOR 2016. LNCS, vol. 9676, pp. 187–197. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-33954-2_14

10.

Hooker, J.N.: Job sequencing bounds from decision diagrams. In: Beck, J.C. (ed.) CP 2017. LNCS, vol. 10416, pp. 565–578. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66158-2_36CrossRef

11.

Hooker, J.N.: Logic-based methods for optimization. In: Borning, A. (ed.) PPCP 1994. LNCS, vol. 874, pp. 336–349. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-58601-6_111CrossRef

12.

Hooker, J.N.: A hybrid method for the planning and scheduling. Constraints 10(4), 385–401 (2005)MathSciNetCrossRefMATH

13.

Hooker, J.N., Ottosson, G.: Logic-based Benders decomposition. Math. Program. 96(1), 33–60 (2003)MathSciNetCrossRefMATH

14.

Ku, W.Y., Beck, J.C.: Mixed integer programming models for job shop scheduling: a computational analysis. Comput. Oper. Res. 73, 165–173 (2016)MathSciNetCrossRefMATH

15.

Manne, A.S.: On the job-shop scheduling problem. Oper. Res. 8(2), 219–223 (1960)MathSciNetCrossRef

16.

Özgüven, C., Özbakır, L., Yavuz, Y.: Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Appl. Math. Model. 34(6), 1539–1548 (2010)MathSciNetCrossRefMATH

17.

Roshanaei, V., Luong, C., Aleman, D.M., Urbach, D.R.: Collaborative operating room planning and scheduling. INFORMS J. Comput. 29(3), 558–580 (2017)MathSciNetCrossRefMATH

18.

Ruiz, R., Maroto, C.: A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. Eur. J. Oper. Res. 169(3), 781–800 (2006)MathSciNetCrossRefMATH

19.

Ruiz, R., Vázquez-Rodríguez, J.A.: The hybrid flow shop scheduling problem. Eur. J. Oper. Res. 205(1), 1–18 (2010)MathSciNetCrossRefMATH

20.

Thomalla, C.S.: Job shop scheduling with alternative process plans. Int. J. Prod. Econ. 74(1), 125–134 (2001)CrossRef

21.

Thorsteinsson, E.S.: Branch-and-check: a hybrid framework integrating mixed integer programming and constraint logic programming. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 16–30. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45578-7_2CrossRef

22.

Tran, T.T., Araujo, A., Beck, J.C.: Decomposition methods for the parallel machine scheduling problem with setups. INFORMS J. Comput. 28(1), 83–95 (2016)MathSciNetCrossRefMATH

23.

Tran, T.T., Vaquero, T., Nejat, G., Beck, J.C.: Robots in retirement homes: applying off-the-shelf planning and scheduling to a team of assistive robots. J. Artif. Intell. Res. 58, 523–590 (2017)MathSciNetMATH

Titel: Logic-Based Benders Decomposition for Two-Stage Flexible Flow Shop Scheduling with Unrelated Parallel Machines
verfasst von: Yingcong Tan
Daria Terekhov
Verlag: Springer International Publishing
Buch: Advances in Artificial Intelligence
Print ISBN: 978-3-319-89655-7

Electronic ISBN: 978-3-319-89656-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-89656-4_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"