Skip to main content
Erschienen in: Journal of Intelligent Manufacturing 2/2021

09.05.2020

A discrete differential evolution algorithm for flow shop group scheduling problem with sequence-dependent setup and transportation times

verfasst von: Shuaipeng Yuan, Tieke Li, Bailin Wang

Erschienen in: Journal of Intelligent Manufacturing | Ausgabe 2/2021

Einloggen

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

search-config
loading …

Abstract

This study investigates a flow shop group scheduling problem where both sequence-dependent setup time between groups and round-trip transportation time between machines are considered. The objective is to minimize makespan. To solve the problem, we first develop a mixed integer linear programming model and then propose an efficient co-evolutionary discrete differential evolution algorithm (CDDEA). In the CDDEA, several problem-specific heuristic rules are generated to construct initial population. A novel discrete differential evolution mechanism and a cooperative-oriented optimization strategy are proposed to synergistically evolve both the sequence of jobs in each group and the sequence of groups. In addition, two lower bounds are developed to evaluate the solution quality of CDDEA. Extensive computational experiments are carried out. The results show that the proposed CDDEA is effective in solving the studied problem.

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!

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!

Literatur
Zurück zum Zitat Cheng, H.-M., & Ying, K.-C. (2011). Minimizing makespan in a flow-line manufacturing cell with sequence dependent family setup times. Expert Systems with Applications, 38(12), 15517–15522.CrossRef Cheng, H.-M., & Ying, K.-C. (2011). Minimizing makespan in a flow-line manufacturing cell with sequence dependent family setup times. Expert Systems with Applications, 38(12), 15517–15522.CrossRef
Zurück zum Zitat Costa, A., Cappadonna, F. A., & Fichera, S. (2017). A hybrid genetic algorithm for minimizing makespan in a flow-shop sequence-dependent group scheduling problem. Journal of Intelligent Manufacturing, 28(6), 1269–1283.CrossRef Costa, A., Cappadonna, F. A., & Fichera, S. (2017). A hybrid genetic algorithm for minimizing makespan in a flow-shop sequence-dependent group scheduling problem. Journal of Intelligent Manufacturing, 28(6), 1269–1283.CrossRef
Zurück zum Zitat Costa, A., Cappadonna, F., & Fichera, S. (2020). Minimizing makespan in a flow shop sequence dependent group scheduling problem with blocking constraint. Engineering Applications of Artificial Intelligence, 89, 103413.CrossRef Costa, A., Cappadonna, F., & Fichera, S. (2020). Minimizing makespan in a flow shop sequence dependent group scheduling problem with blocking constraint. Engineering Applications of Artificial Intelligence, 89, 103413.CrossRef
Zurück zum Zitat Dechampai, D., Tanwanichkul, L., Sethanan, K., & Pitakaso, R. (2017). A differential evolution algorithm for the capacitated VRP with flexibility of mixing pickup and delivery services and the maximum duration of a route in poultry industry. Journal of Intelligent Manufacturing, 28(6), 1357–1376.CrossRef Dechampai, D., Tanwanichkul, L., Sethanan, K., & Pitakaso, R. (2017). A differential evolution algorithm for the capacitated VRP with flexibility of mixing pickup and delivery services and the maximum duration of a route in poultry industry. Journal of Intelligent Manufacturing, 28(6), 1357–1376.CrossRef
Zurück zum Zitat Feng, H., Xi, L., Xiao, L., Xia, T., & Pan, E. (2018). Imperfect preventive maintenance optimization for flexible flowshop manufacturing cells considering sequence-dependent group scheduling. Reliability Engineering and System Safety, 176, 218–229.CrossRef Feng, H., Xi, L., Xiao, L., Xia, T., & Pan, E. (2018). Imperfect preventive maintenance optimization for flexible flowshop manufacturing cells considering sequence-dependent group scheduling. Reliability Engineering and System Safety, 176, 218–229.CrossRef
Zurück zum Zitat França, P. M., Gupta, J. N., Mendes, A. S., Moscato, P., & Veltink, K. J. (2005). Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups. Computers and Industrial Engineering, 48(3), 491–506.CrossRef França, P. M., Gupta, J. N., Mendes, A. S., Moscato, P., & Veltink, K. J. (2005). Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups. Computers and Industrial Engineering, 48(3), 491–506.CrossRef
Zurück zum Zitat Gnanavel Babu, A., Jerald, J., Noorul Haq, A., Muthu Luxmi, V., & Vigneswaralu, T. (2010). Scheduling of machines and automated guided vehicles in FMS using differential evolution. International Journal of Production Research, 48(16), 4683–4699.CrossRef Gnanavel Babu, A., Jerald, J., Noorul Haq, A., Muthu Luxmi, V., & Vigneswaralu, T. (2010). Scheduling of machines and automated guided vehicles in FMS using differential evolution. International Journal of Production Research, 48(16), 4683–4699.CrossRef
Zurück zum Zitat Lin, S.-W., & Ying, K.-C. (2019). Makespan optimization in a no-wait flowline manufacturing cell with sequence-dependent family setup times. Computers and Industrial Engineering, 128, 1–7.CrossRef Lin, S.-W., & Ying, K.-C. (2019). Makespan optimization in a no-wait flowline manufacturing cell with sequence-dependent family setup times. Computers and Industrial Engineering, 128, 1–7.CrossRef
Zurück zum Zitat Liou, C. D., & Hsieh, Y. C. (2015). A hybrid algorithm for the multi-stage flow shop group scheduling with sequence-dependent setup and transportation times. International Journal of Production Economics, 170, 258–267.CrossRef Liou, C. D., & Hsieh, Y. C. (2015). A hybrid algorithm for the multi-stage flow shop group scheduling with sequence-dependent setup and transportation times. International Journal of Production Economics, 170, 258–267.CrossRef
Zurück zum Zitat Liou, C.-D., Hsieh, Y.-C., & Chen, Y.-Y. (2013). A new encoding scheme-based hybrid algorithm for minimising two-machine flow-shop group scheduling problem. International Journal of Systems Science, 44(1), 77–93.CrossRef Liou, C.-D., Hsieh, Y.-C., & Chen, Y.-Y. (2013). A new encoding scheme-based hybrid algorithm for minimising two-machine flow-shop group scheduling problem. International Journal of Systems Science, 44(1), 77–93.CrossRef
Zurück zum Zitat Liu, Y., Yin, M., & Gu, W. (2014). An effective differential evolution algorithm for permutation flow shop scheduling problem. Applied Mathematics and Computation, 248, 143–159.CrossRef Liu, Y., Yin, M., & Gu, W. (2014). An effective differential evolution algorithm for permutation flow shop scheduling problem. Applied Mathematics and Computation, 248, 143–159.CrossRef
Zurück zum Zitat Logendran, R., Salmasi, N., & Sriskandarajah, C. (2006). Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups. Computers and Operations Research, 33(1), 158–180.CrossRef Logendran, R., Salmasi, N., & Sriskandarajah, C. (2006). Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups. Computers and Operations Research, 33(1), 158–180.CrossRef
Zurück zum Zitat Marimuthu, S., & Sait, A. N. (2013). Performance evaluation of proposed differential evolution and particle swarm optimization algorithms for scheduling m-machine flow shops with lot streaming. Journal of Intelligent Manufacturing, 24(1), 175–191.CrossRef Marimuthu, S., & Sait, A. N. (2013). Performance evaluation of proposed differential evolution and particle swarm optimization algorithms for scheduling m-machine flow shops with lot streaming. Journal of Intelligent Manufacturing, 24(1), 175–191.CrossRef
Zurück zum Zitat Pan, Q.-K. (2016). An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling. European Journal of Operational Research, 250(3), 702–714.CrossRef Pan, Q.-K. (2016). An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling. European Journal of Operational Research, 250(3), 702–714.CrossRef
Zurück zum Zitat Qin, H., Zhang, Z.-H., & Bai, D. (2016). Permutation flowshop group scheduling with position-based learning effect. Computers and Industrial Engineering, 92, 1–15.CrossRef Qin, H., Zhang, Z.-H., & Bai, D. (2016). Permutation flowshop group scheduling with position-based learning effect. Computers and Industrial Engineering, 92, 1–15.CrossRef
Zurück zum Zitat Ruiz, R., & Maroto, C. (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 169(3), 781–800.CrossRef Ruiz, R., & Maroto, C. (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 169(3), 781–800.CrossRef
Zurück zum Zitat Salmasi, N., Logendran, R., & Skandari, M. R. (2010). Total flow time minimization in a flowshop sequence-dependent group scheduling problem. Computers and Operations Research, 37(1), 199–212.CrossRef Salmasi, N., Logendran, R., & Skandari, M. R. (2010). Total flow time minimization in a flowshop sequence-dependent group scheduling problem. Computers and Operations Research, 37(1), 199–212.CrossRef
Zurück zum Zitat Schaller, J. E., Gupta, J. N., & Vakharia, A. J. (2000). Scheduling a flowline manufacturing cell with sequence dependent family setup times. European Journal of Operational Research, 125(2), 324–339.CrossRef Schaller, J. E., Gupta, J. N., & Vakharia, A. J. (2000). Scheduling a flowline manufacturing cell with sequence dependent family setup times. European Journal of Operational Research, 125(2), 324–339.CrossRef
Zurück zum Zitat Solimanpur, M., Vrat, P., & Shankar, R. (2004). A heuristic to minimize makespan of cell scheduling problem. International Journal of Production Economics, 88(3), 231–241.CrossRef Solimanpur, M., Vrat, P., & Shankar, R. (2004). A heuristic to minimize makespan of cell scheduling problem. International Journal of Production Economics, 88(3), 231–241.CrossRef
Zurück zum Zitat Storn, R., & Price, K. (1997). Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341–359.CrossRef Storn, R., & Price, K. (1997). Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341–359.CrossRef
Zurück zum Zitat Tasgetiren, M. F., Pan, Q. K., Suganthan, P. N., & Chua, T. J. (2011). A differential evolution algorithm for the no-idle flowshop scheduling problem with total tardiness criterion. International Journal of Production Research, 49(16), 5033–5050.CrossRef Tasgetiren, M. F., Pan, Q. K., Suganthan, P. N., & Chua, T. J. (2011). A differential evolution algorithm for the no-idle flowshop scheduling problem with total tardiness criterion. International Journal of Production Research, 49(16), 5033–5050.CrossRef
Zurück zum Zitat Vincent, L. W. H., Ponnambalam, S., & Kanagaraj, G. (2014). Differential evolution variants to schedule flexible assembly lines. Journal of Intelligent Manufacturing, 25(4), 739–753.CrossRef Vincent, L. W. H., Ponnambalam, S., & Kanagaraj, G. (2014). Differential evolution variants to schedule flexible assembly lines. Journal of Intelligent Manufacturing, 25(4), 739–753.CrossRef
Zurück zum Zitat Wang, B., Huang, K., & Li, T. (2018). Permutation flowshop scheduling with time lag constraints and makespan criterion. Computers and Industrial Engineering, 120, 1–14.CrossRef Wang, B., Huang, K., & Li, T. (2018). Permutation flowshop scheduling with time lag constraints and makespan criterion. Computers and Industrial Engineering, 120, 1–14.CrossRef
Zurück zum Zitat Zandieh, M., & Karimi, N. (2011). An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times. Journal of Intelligent Manufacturing, 22(6), 979–989.CrossRef Zandieh, M., & Karimi, N. (2011). An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times. Journal of Intelligent Manufacturing, 22(6), 979–989.CrossRef
Zurück zum Zitat Zhou, S., Li, X., Du, N., Pang, Y., & Chen, H. (2018). A multi-objective differential evolution algorithm for parallel batch processing machine scheduling considering electricity consumption cost. Computers and Operations Research, 96, 55–68.CrossRef Zhou, S., Li, X., Du, N., Pang, Y., & Chen, H. (2018). A multi-objective differential evolution algorithm for parallel batch processing machine scheduling considering electricity consumption cost. Computers and Operations Research, 96, 55–68.CrossRef
Metadaten
Titel
A discrete differential evolution algorithm for flow shop group scheduling problem with sequence-dependent setup and transportation times
verfasst von
Shuaipeng Yuan
Tieke Li
Bailin Wang
Publikationsdatum
09.05.2020
Verlag
Springer US
Erschienen in
Journal of Intelligent Manufacturing / Ausgabe 2/2021
Print ISSN: 0956-5515
Elektronische ISSN: 1572-8145
DOI
https://doi.org/10.1007/s10845-020-01580-3

Weitere Artikel der Ausgabe 2/2021

Journal of Intelligent Manufacturing 2/2021 Zur Ausgabe

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.