Skip to main content
Top
Published in: Journal of Scheduling 3/2021

01-06-2021

A hybrid evolutionary approach to job-shop scheduling with generic time lags

Authors: Madiha Harrabi, Olfa Belkahla Driss, Khaled Ghedira

Published in: Journal of Scheduling | Issue 3/2021

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper addresses the job shop scheduling problem including time lag constraints. This is an extension of the job shop scheduling problem with many applications in real production environments, where extra (minimum and maximum) delays can be introduced between operations. It belongs to a category of problems known as NP-hard problems due to the large solution space. Biogeography-based optimization (BBO) is an evolutionary algorithm which is inspired by the migration of species between habitats, recently proposed by Simon (IEEE Trans Evol Comput 12:702–713, 2008) to optimize hard combinatorial optimization problems. BBO has successfully solved optimization problems in many different domains and has demonstrated excellent performance. We propose a hybrid biogeography-based optimization (HBBO) algorithm for solving the job shop scheduling problem with additional time lag constraints while minimizing total completion time. In the proposed HBBO, an effective greedy constructive heuristic is adapted to generate the initial habitat population. A local search metaheuristic is investigated in the mutation step in order to improve the solution quality and enhance the diversity of the population. To assess the performance of the HBBO, a series of experiments are performed on well-known benchmark instances for job shop scheduling problems with time lag constraints. The results prove the efficiency of the proposed algorithm in comparison with various other algorithms.

Dont have a licence yet? Then find out more about our products and how to get one now:

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 "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!

Literature
go back to reference Afsar, H. M., Lacomme, P., Ren, L., Prodhon, C. & Vigo, D. (2016). Resolution of a job-shop problem with transportation constraints: A master/slave approach. In IFAC conference on manufacturing modelling, management and control. Afsar, H. M., Lacomme, P., Ren, L., Prodhon, C. & Vigo, D. (2016). Resolution of a job-shop problem with transportation constraints: A master/slave approach. In IFAC conference on manufacturing modelling, management and control.
go back to reference Al-Roomi, A., & El-Hawary, M. (2016). Metropolis biogeography-based optimization. Information Sciences, 360, 73–95. Al-Roomi, A., & El-Hawary, M. (2016). Metropolis biogeography-based optimization. Information Sciences, 360, 73–95.
go back to reference Artigues, C., Huguet, M., & Lopez, P. (2011). Generalized disjunctive constraint propagation for solving the job shop problem with time lags. Engineering Applications of Artificial Intelligence, 24, 220–231. Artigues, C., Huguet, M., & Lopez, P. (2011). Generalized disjunctive constraint propagation for solving the job shop problem with time lags. Engineering Applications of Artificial Intelligence, 24, 220–231.
go back to reference Bartusch, M., Mohring, R. H., & Rademacher, F. J. (1988). Scheduling project networks with resource constraints and time windows. Annals of Operations Research, 16, 201–240. Bartusch, M., Mohring, R. H., & Rademacher, F. J. (1988). Scheduling project networks with resource constraints and time windows. Annals of Operations Research, 16, 201–240.
go back to reference Bhattacharya, A., & Chattopadhyay, P. (2010). Hybrid differential evolution with biogeography-based optimization for solution of economic load dispatch. IEEE Transactions on Power Systems, 25(4), 1955–1964. Bhattacharya, A., & Chattopadhyay, P. (2010). Hybrid differential evolution with biogeography-based optimization for solution of economic load dispatch. IEEE Transactions on Power Systems, 25(4), 1955–1964.
go back to reference Bhattacharya, A., & Chattopadhyay, P. (2011). Hybrid differential evolution with biogeography-based optimization algorithm for solution of economic emission load dispatch problems. Expert Systems With Applications, 38(11), 14001–14010. Bhattacharya, A., & Chattopadhyay, P. (2011). Hybrid differential evolution with biogeography-based optimization algorithm for solution of economic emission load dispatch problems. Expert Systems With Applications, 38(11), 14001–14010.
go back to reference Botta-Genoulaz, V. (2000). Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness. International Journal of Production Economics, 64, 101–111. Botta-Genoulaz, V. (2000). Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness. International Journal of Production Economics, 64, 101–111.
go back to reference Boussaïd, I., Chatterjee, A., & Siarry, P. (2011). Hybridizing biogeography-based optimization with differential evolution for optimal power allocation in wireless sensor networks. IEEE Transactions on Vehicular Technology, 60(5), 2347–2353. Boussaïd, I., Chatterjee, A., & Siarry, P. (2011). Hybridizing biogeography-based optimization with differential evolution for optimal power allocation in wireless sensor networks. IEEE Transactions on Vehicular Technology, 60(5), 2347–2353.
go back to reference Brinkmann, K., & Neumann, K. (1996). Heuristic procedures for resource-constrained project scheduling with minimal and maximal time lags: The minimum project-duration and resource-levelling problems. Journal of Decision Systems, 5, 129–156. Brinkmann, K., & Neumann, K. (1996). Heuristic procedures for resource-constrained project scheduling with minimal and maximal time lags: The minimum project-duration and resource-levelling problems. Journal of Decision Systems, 5, 129–156.
go back to reference Brucker, P., Hilbig, T., & Hurink, J. (1999). A branch and bound algorithm for a single machine scheduling with positive and negative time-lags. Discrete Applied Mathematics, 120, 77–99. Brucker, P., Hilbig, T., & Hurink, J. (1999). A branch and bound algorithm for a single machine scheduling with positive and negative time-lags. Discrete Applied Mathematics, 120, 77–99.
go back to reference Carlier, J. (1978). Ordonnancements á contraintes disjunctives. RAIRO Recherche operationelle, 12, 333–351. Carlier, J. (1978). Ordonnancements á contraintes disjunctives. RAIRO Recherche operationelle, 12, 333–351.
go back to reference Caumond A. A., Lacomme, P. & Tchernev, N. (2005a). Proposition of genetic algorithm for job-shop with time-lags. ROADEF’05 (pp. 183–200). Caumond A. A., Lacomme, P. & Tchernev, N. (2005a). Proposition of genetic algorithm for job-shop with time-lags. ROADEF’05 (pp. 183–200).
go back to reference Caumond, A., Gourgand, M., Lacomme, P., & Tchernev, N. (2004). Metaheuristics for job-shop with time lags. In Proceedings of the conference Mosim’s 04 (pp. 939–946). Nantes, France. Caumond, A., Gourgand, M., Lacomme, P., & Tchernev, N. (2004). Metaheuristics for job-shop with time lags. In Proceedings of the conference Mosim’s 04 (pp. 939–946). Nantes, France.
go back to reference Caumond, A., Lacomme, P., & Tchernev, N. (2005b). Feasible schedule generation with extension of the Giffler and Thompson’s heuristic for the job shop problem with time lags. In International conference of industrial engineering and systems management (pp. 489–499). Caumond, A., Lacomme, P., & Tchernev, N. (2005b). Feasible schedule generation with extension of the Giffler and Thompson’s heuristic for the job shop problem with time lags. In International conference of industrial engineering and systems management (pp. 489–499).
go back to reference Caumond, A., Lacomme, P., & Tchernev, N. (2008). A memetic algorithm for the job-shop with time-lags. Computers & Operations Research, 35, 2331–2356. Caumond, A., Lacomme, P., & Tchernev, N. (2008). A memetic algorithm for the job-shop with time-lags. Computers & Operations Research, 35, 2331–2356.
go back to reference Chu, C., & Proth, J. M. (1996). Single machine scheduling with chain structured precedence constraints and separation time windows. IEEE Transactions on Robotics and Automation, 12, 835–843. Chu, C., & Proth, J. M. (1996). Single machine scheduling with chain structured precedence constraints and separation time windows. IEEE Transactions on Robotics and Automation, 12, 835–843.
go back to reference Deppner, F. (2004). Ordonnancement d’atelier avec contraintes temporelles entre opérations. Ph.D. thesis, Institut National Polytechnique de Lorraine. Deppner, F. (2004). Ordonnancement d’atelier avec contraintes temporelles entre opérations. Ph.D. thesis, Institut National Polytechnique de Lorraine.
go back to reference Deroussi, L., Gourgand, M., & Norre, S. (2006). New effective neighborhoods for the permutation flow shop problem. Deroussi, L., Gourgand, M., & Norre, S. (2006). New effective neighborhoods for the permutation flow shop problem.
go back to reference Dhouib, E., Teghem, J., & Loukil, T. (2013). Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints. International Transactions in Operational Research, 20(2), 213–232. Dhouib, E., Teghem, J., & Loukil, T. (2013). Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints. International Transactions in Operational Research, 20(2), 213–232.
go back to reference Du, D., Simon, D., & Ergezer, M. (2009). Biogeography-based optimization combined with evolutionary strategy and immigration refusal. In Proceedings of IEEE international conference on systems, man and cybernetics, San Antonio (pp. 997–1002). Du, D., Simon, D., & Ergezer, M. (2009). Biogeography-based optimization combined with evolutionary strategy and immigration refusal. In Proceedings of IEEE international conference on systems, man and cybernetics, San Antonio (pp. 997–1002).
go back to reference Feng, S.-L. Yang, Z.-Q. Huang, M.-X. (2017). Hybridizing adaptive biogeography-based optimization with differential evolution for multi-objective optimization problems. Information, 8, 83. Feng, S.-L. Yang, Z.-Q. Huang, M.-X. (2017). Hybridizing adaptive biogeography-based optimization with differential evolution for multi-objective optimization problems. Information, 8, 83.
go back to reference Fisher, H., & Thompson, G. L. (1963). Probabilistic learning combination of local job shop scheduling rules. Industrial scheduling (pp. 225–251). Upper Saddle River: Prentice Hall. Fisher, H., & Thompson, G. L. (1963). Probabilistic learning combination of local job shop scheduling rules. Industrial scheduling (pp. 225–251). Upper Saddle River: Prentice Hall.
go back to reference Fondrevelle, J., Oulamaraa, A., & Portmann, M.-C. (2006). Permutation flowshop scheduling problems with maximal and minimal time lags. Computers & Operations Research, 33, 1540–1556. Fondrevelle, J., Oulamaraa, A., & Portmann, M.-C. (2006). Permutation flowshop scheduling problems with maximal and minimal time lags. Computers & Operations Research, 33, 1540–1556.
go back to reference Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533–549. Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533–549.
go back to reference González, M. A., Oddi, A., Rasconi, R., & Varela, R. (2015). Scatter search with path relinking for the job shop with time lags and set up times. Computer & Operation Research, 60, 37–54. González, M. A., Oddi, A., Rasconi, R., & Varela, R. (2015). Scatter search with path relinking for the job shop with time lags and set up times. Computer & Operation Research, 60, 37–54.
go back to reference Guo, W., Li, W., Zhang, Q., Wang, L., & Wu, Q. (2013). Biogeography-based particle swarm optimization with fuzzy elitism and its applications to constrained engineering problems. Engineering Optimization, 46(11), 1–20. Guo, W., Li, W., Zhang, Q., Wang, L., & Wu, Q. (2013). Biogeography-based particle swarm optimization with fuzzy elitism and its applications to constrained engineering problems. Engineering Optimization, 46(11), 1–20.
go back to reference Habib, S., Rahmati, A., & Zandieh, M. (2011). A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 58(9), 1115–1129. Habib, S., Rahmati, A., & Zandieh, M. (2011). A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 58(9), 1115–1129.
go back to reference Hamdi, I., & Loukil, T. (2011). Minimizing the makespan in the permutation flowshop problem with maximal and minimal time lags. In Communications, computing and control applications (CCCA) (pp. 1–6). Hamdi, I., & Loukil, T. (2011). Minimizing the makespan in the permutation flowshop problem with maximal and minimal time lags. In Communications, computing and control applications (CCCA) (pp. 1–6).
go back to reference Harrabi, M., & Belkahla Driss, O. (2015). MATS-JSTL: A multi-agent model based on Tabu search for the job shop problem with time lags. In International computational collective intelligence technologies and applications ICCCI (pp. 39–46). Harrabi, M., & Belkahla Driss, O. (2015). MATS-JSTL: A multi-agent model based on Tabu search for the job shop problem with time lags. In International computational collective intelligence technologies and applications ICCCI (pp. 39–46).
go back to reference Harrabi, M., & Belkahla Driss, O. (2016). Tabu Search metaheuristic for job shop scheduling problem with generic time lags. In International conference on decision aid sciences and applications DASA. Harrabi, M., & Belkahla Driss, O. (2016). Tabu Search metaheuristic for job shop scheduling problem with generic time lags. In International conference on decision aid sciences and applications DASA.
go back to reference Harrabi, M., Belkahla Driss, O., & Ghedira, K. (2017a). Competitive agents implementing parallel Tabu searches for job shop scheduling problem with time lags. In IASTED international conference on modelling, identification and control (pp. 848–052). Harrabi, M., Belkahla Driss, O., & Ghedira, K. (2017a). Competitive agents implementing parallel Tabu searches for job shop scheduling problem with time lags. In IASTED international conference on modelling, identification and control (pp. 848–052).
go back to reference Harrabi, M., Belkahla Driss, O., & Ghedira, K. (2017b). Combining genetic algorithm and Tabu search for job shop scheduling problem with time lags. In IEEE international conference on engineering & MIS. Harrabi, M., Belkahla Driss, O., & Ghedira, K. (2017b). Combining genetic algorithm and Tabu search for job shop scheduling problem with time lags. In IEEE international conference on engineering & MIS.
go back to reference Harrabi, M., Belkahla Driss, O., & Ghedira, K. (2017c). A multi-agent model based on hybrid genetic algorithm for job shop scheduling problem with generic time lags. In ACS/IEEE international conference on computer systems and applications AICCSA. Harrabi, M., Belkahla Driss, O., & Ghedira, K. (2017c). A multi-agent model based on hybrid genetic algorithm for job shop scheduling problem with generic time lags. In ACS/IEEE international conference on computer systems and applications AICCSA.
go back to reference Harrabi, M., Belkahla Driss, O., & Ghedira, K. (2018). A greedy biogeography-based optimization algorithm for job shop scheduling problem with time lags. In M. Graña, et al. (Eds.), International joint conference SOCO’18-CISIS’18-ICEUTE’18. SOCO’18-CISIS’18-ICEUTE’18. Advances in intelligent systems and computing (Vol. 771). Springer. Harrabi, M., Belkahla Driss, O., & Ghedira, K. (2018). A greedy biogeography-based optimization algorithm for job shop scheduling problem with time lags. In M. Graña, et al. (Eds.), International joint conference SOCO’18-CISIS’18-ICEUTE’18. SOCO’18-CISIS’18-ICEUTE’18. Advances in intelligent systems and computing (Vol. 771). Springer.
go back to reference Harrabi, M., Belkahla Driss, O., & Ghedira, K. (2020). A modified biogeography-based optimization algorithm with improved mutation operator for job shop scheduling problem with time lags. Logic Journal of the IGPL, jzaa037. Harrabi, M., Belkahla Driss, O., & Ghedira, K. (2020). A modified biogeography-based optimization algorithm with improved mutation operator for job shop scheduling problem with time lags. Logic Journal of the IGPL, jzaa037.
go back to reference Heilmann, R. (2003). A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags. European Journal of Operational Research, 144(144), 348–365. Heilmann, R. (2003). A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags. European Journal of Operational Research, 144(144), 348–365.
go back to reference Hodson, A., Muhlemann, P., & Price, D. H. R. (1985). A microcomputer based solution to a practical scheduling problem. Journal of the Operational Research Society, 36(10), 903–914. Hodson, A., Muhlemann, P., & Price, D. H. R. (1985). A microcomputer based solution to a practical scheduling problem. Journal of the Operational Research Society, 36(10), 903–914.
go back to reference Hurink, J., & Keuchel, J. (2001). Local search algorithms for a single machine scheduling problem with positive and negative time-lags. Discrete Applied Mathematics, 112, 179–197. Hurink, J., & Keuchel, J. (2001). Local search algorithms for a single machine scheduling problem with positive and negative time-lags. Discrete Applied Mathematics, 112, 179–197.
go back to reference Johnson, S. M. (1954). Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics, 1, 61–68. Johnson, S. M. (1954). Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics, 1, 61–68.
go back to reference Karoui, W., Huguet, M. J., Lopez, P., & Haouari, M. (2010). Méthode de recherche a divergence limitée pour les \(probl\grave{e}mes\) d’ordonnancement avec contraintes de délais. In Conférence Internationale de Modélisation et Simulation (Vol. 8, pp. 10–12). Karoui, W., Huguet, M. J., Lopez, P., & Haouari, M. (2010). Méthode de recherche a divergence limitée pour les \(probl\grave{e}mes\) d’ordonnancement avec contraintes de délais. In Conférence Internationale de Modélisation et Simulation (Vol. 8, pp. 10–12).
go back to reference Kim, Y. D., Lim, H. G., & Park, M. W. (1996). Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process. European Journal of Operational Research, 91, 124–143. Kim, Y. D., Lim, H. G., & Park, M. W. (1996). Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process. European Journal of Operational Research, 91, 124–143.
go back to reference Lacomme, P., Huguet, MJ., & Tchernev, N. (2011). Dedicated constraint propagation for job-shop problem with generic time-lags. In 16th IEEE conference on emerging technologies and factory automation IEEE catalog number: CFP11ETF-USB. Lacomme, P., Huguet, MJ., & Tchernev, N. (2011). Dedicated constraint propagation for job-shop problem with generic time-lags. In 16th IEEE conference on emerging technologies and factory automation IEEE catalog number: CFP11ETF-USB.
go back to reference Lacomme, P., & Tchernev, N. (2012). Job-shop with generic time lags: A heuristic based approach. In 9th international conference of modeling, optimization and simulation—MOSIM. Lacomme, P., & Tchernev, N. (2012). Job-shop with generic time lags: A heuristic based approach. In 9th international conference of modeling, optimization and simulation—MOSIM.
go back to reference Lawrence, S. (1984). Supplement to resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques. Pittsburgh: Graduate School of Industrial Administration, Carnegie Mellon University. Lawrence, S. (1984). Supplement to resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques. Pittsburgh: Graduate School of Industrial Administration, Carnegie Mellon University.
go back to reference Lin, J. (2016). A hybrid discrete biogeography-based optimization for the permutation flow shop scheduling problem. International Journal of Production Research, 54(16), 1–10. Lin, J. (2016). A hybrid discrete biogeography-based optimization for the permutation flow shop scheduling problem. International Journal of Production Research, 54(16), 1–10.
go back to reference Lu, X., Du, Y., Yang, X., & Zheng, Y. (2018). A biogeography-based memetic algorithm for job-shop scheduling. In International conference on bio-inspired computing: theories and applications (pp. 273–284). Lu, X., Du, Y., Yang, X., & Zheng, Y. (2018). A biogeography-based memetic algorithm for job-shop scheduling. In International conference on bio-inspired computing: theories and applications (pp. 273–284).
go back to reference Ma, H., Su, S., Simon, D., & Fei, M. (2015). Ensemble multi-objective biogeography-based optimization with application to automated warehouse scheduling. Engineering Applications of Artificial Intelligence, 44, 79–90. Ma, H., Su, S., Simon, D., & Fei, M. (2015). Ensemble multi-objective biogeography-based optimization with application to automated warehouse scheduling. Engineering Applications of Artificial Intelligence, 44, 79–90.
go back to reference Ma, H., & Simon, D. (2017). Biogeography-based optimization: A 10-year review. IEEE Transactions on Emerging Topics in Computational Intelligence, 1(5), 391–407. Ma, H., & Simon, D. (2017). Biogeography-based optimization: A 10-year review. IEEE Transactions on Emerging Topics in Computational Intelligence, 1(5), 391–407.
go back to reference MacArthur, R., & Wilson, E. (1967). The theory of biogeography. Princeton, NJ: Princeton University Press. MacArthur, R., & Wilson, E. (1967). The theory of biogeography. Princeton, NJ: Princeton University Press.
go back to reference Manier, M. A., & Bloch, C. (2003). A classification of hoist scheduling problems. International Journal of Flexible Manufacturing Systems, 15(1), 37–55. Manier, M. A., & Bloch, C. (2003). A classification of hoist scheduling problems. International Journal of Flexible Manufacturing Systems, 15(1), 37–55.
go back to reference Manne, S. (1960). On the job-shop scheduling problem. Operations Research, 8, 219–223. Manne, S. (1960). On the job-shop scheduling problem. Operations Research, 8, 219–223.
go back to reference Mitten, L. G. (1958). Sequencing n jobs on two machines with arbitrary time lags. Management Science, 5(3), 293–298. Mitten, L. G. (1958). Sequencing n jobs on two machines with arbitrary time lags. Management Science, 5(3), 293–298.
go back to reference Nawaz, M., Enscore, J. E. E., & Ham, I. (1983). A heuristic algorithm for the n-job, m machine sequencing problem. Management Science, 16/B, 630–637. Nawaz, M., Enscore, J. E. E., & Ham, I. (1983). A heuristic algorithm for the n-job, m machine sequencing problem. Management Science, 16/B, 630–637.
go back to reference Neumann, K., Schwindt, C., & Zimmermann, J. (2002). Project scheduling with time windows and scarce resources. Berlin: Springer. Neumann, K., Schwindt, C., & Zimmermann, J. (2002). Project scheduling with time windows and scarce resources. Berlin: Springer.
go back to reference Nikbakhsh, J. P., Mohammad, F. M., & Mohammad, K. (2012). An immune algorithm for hybrid flow shop scheduling problem with time lags and sequence dependent setup times. International Journal of Advanced Manufacturing Technology, 63(1–4), 337–348. Nikbakhsh, J. P., Mohammad, F. M., & Mohammad, K. (2012). An immune algorithm for hybrid flow shop scheduling problem with time lags and sequence dependent setup times. International Journal of Advanced Manufacturing Technology, 63(1–4), 337–348.
go back to reference Nowicki, E., & Smutnicki, C. (2005). An advanced Tabu search algorithm for the job shop problem. Journal of Scheduling, 8, 145–159. Nowicki, E., & Smutnicki, C. (2005). An advanced Tabu search algorithm for the job shop problem. Journal of Scheduling, 8, 145–159.
go back to reference Rabiee, M., Jolai, F., Asefi, H., & Fattahi, P. (2016). A biogeography-based optimization algorithm for a realistic no-wait hybrid flow shop with unrelated parallel machines to minimize mean tardiness. International Journal of Computer Integrated Manufacturing, 29, 1007–1024. Rabiee, M., Jolai, F., Asefi, H., & Fattahi, P. (2016). A biogeography-based optimization algorithm for a realistic no-wait hybrid flow shop with unrelated parallel machines to minimize mean tardiness. International Journal of Computer Integrated Manufacturing, 29, 1007–1024.
go back to reference Rifai, A. P., Nguyen, H., Aoyama, H., Dawal, S. Z., & Masruroh, N. A. (2018). Non-dominated sorting biogeography-based optimization for bi-objective reentrant flexible manufacturing system scheduling. Applied Soft Computing, 62, 187–202. Rifai, A. P., Nguyen, H., Aoyama, H., Dawal, S. Z., & Masruroh, N. A. (2018). Non-dominated sorting biogeography-based optimization for bi-objective reentrant flexible manufacturing system scheduling. Applied Soft Computing, 62, 187–202.
go back to reference Rajendran, C. (1994). A no-wait flow shop scheduling heuristic to minimize makespan. The Journal of the Operational Research Society, 45, 472–478. Rajendran, C. (1994). A no-wait flow shop scheduling heuristic to minimize makespan. The Journal of the Operational Research Society, 45, 472–478.
go back to reference Roy, B., & Sussmann, B. (1964). Les problèmes d’ordonnancement avec contraintes disjonctives. SEMA: Technical report. Roy, B., & Sussmann, B. (1964). Les problèmes d’ordonnancement avec contraintes disjonctives. SEMA: Technical report.
go back to reference Sheikh, S. (2013). Multi-objective flexible flow lines with due window, time lag and job rejection. International Journal of Advanced Manufacturing Technology, 64(9–12), 1423–1433. Sheikh, S. (2013). Multi-objective flexible flow lines with due window, time lag and job rejection. International Journal of Advanced Manufacturing Technology, 64(9–12), 1423–1433.
go back to reference Simon, D. (2008). Biogeography-based optimization. IEEE Transactions on Evolutionary Computation, 12, 702–713. Simon, D. (2008). Biogeography-based optimization. IEEE Transactions on Evolutionary Computation, 12, 702–713.
go back to reference Sinha, S., Bhola, A., Panchal, V., Singhal, S., & Abraham, A. (2012). Resolving mixed pixels by hybridization of biogeography based optimization and ant colony optimization. In IIEEE Congress on Evolutionary Computation, Brisbane, QLD (pp. 1–6). Sinha, S., Bhola, A., Panchal, V., Singhal, S., & Abraham, A. (2012). Resolving mixed pixels by hybridization of biogeography based optimization and ant colony optimization. In IIEEE Congress on Evolutionary Computation, Brisbane, QLD (pp. 1–6).
go back to reference Soukhal, A., Oulamara, A., & Martineau, P. (2005). Complexity of flow shop scheduling problems with transportation constraints. European Journal of Operational Research, 161, 32–41. Soukhal, A., Oulamara, A., & Martineau, P. (2005). Complexity of flow shop scheduling problems with transportation constraints. European Journal of Operational Research, 161, 32–41.
go back to reference Talbi, E. G. (2009). Metaheuristics: From design to implementation. Hoboken, NJ: Wiley. Talbi, E. G. (2009). Metaheuristics: From design to implementation. Hoboken, NJ: Wiley.
go back to reference Wang, X., & Duan, H. (2014). A hybrid biogeography-based optimization algorithm for job shop scheduling problem. Computers & Industrial Engineering, 73, 96–114. Wang, X., & Duan, H. (2014). A hybrid biogeography-based optimization algorithm for job shop scheduling problem. Computers & Industrial Engineering, 73, 96–114.
go back to reference Wikum, E. D., Llewellyin, D. C., & Nemhauser, G. L. (1994). One-machine generalized precedence constrained scheduling problem. Operations Research Letters, 16, 87–99. Wikum, E. D., Llewellyin, D. C., & Nemhauser, G. L. (1994). One-machine generalized precedence constrained scheduling problem. Operations Research Letters, 16, 87–99.
go back to reference Wismer, A. D. (1972). Solution of the flow shop scheduling problem with no intermediate queues. Operations Research, 20, 689–697. Wismer, A. D. (1972). Solution of the flow shop scheduling problem with no intermediate queues. Operations Research, 20, 689–697.
go back to reference Wu, J., Wu, X., Lu, X., Lu, X., Du, Y., & Zhang, M. (2019). Water wave optimization for flow-shop scheduling (Vol. 771–783). Wu, J., Wu, X., Lu, X., Lu, X., Du, Y., & Zhang, M. (2019). Water wave optimization for flow-shop scheduling (Vol. 771–783).
go back to reference Yang, Y. (2015). A modified biogeography-based optimization for the flexible job shop scheduling problem. In Mathematical problems in engineering. Yang, Y. (2015). A modified biogeography-based optimization for the flexible job shop scheduling problem. In Mathematical problems in engineering.
go back to reference Ye, S., Zhao, N., Li, K., & Lei, C. (2017). Efficient heuristic for solving non-permutation flow-shop scheduling problems with maximal and minimal time lags. Computers & Industrial Engineering, 113, 160–184. Ye, S., Zhao, N., Li, K., & Lei, C. (2017). Efficient heuristic for solving non-permutation flow-shop scheduling problems with maximal and minimal time lags. Computers & Industrial Engineering, 113, 160–184.
go back to reference Zhang, X. (2010). Scheduling with time lags. Ph.D. Thesis, Erasmus Research Institute of Management. Zhang, X. (2010). Scheduling with time lags. Ph.D. Thesis, Erasmus Research Institute of Management.
go back to reference Zhao, F., Qin, S., & Zhang, Y. (2019). A hybrid biogeography-based optimization with variable neighborhood search mechanism for no-wait flow shop scheduling problem. Expert Systems with Applications, 126, 321–339. Zhao, F., Qin, S., & Zhang, Y. (2019). A hybrid biogeography-based optimization with variable neighborhood search mechanism for no-wait flow shop scheduling problem. Expert Systems with Applications, 126, 321–339.
go back to reference Zhao, N., Ye, S., Li, K., & Chen, S. (2017). Effective iterated greedy algorithm for flow-shop scheduling problems with time lags. Chinese Journal of Mechanical Engineering, 30, 652–662. Zhao, N., Ye, S., Li, K., & Chen, S. (2017). Effective iterated greedy algorithm for flow-shop scheduling problems with time lags. Chinese Journal of Mechanical Engineering, 30, 652–662.
go back to reference Zheng, Y., Ling, H., Shi, H., & Chen, H. (2014a). Emergency railway wagon scheduling by hybrid biogeography-based optimization. Computers & Operations Research, 43(1), 1–8. Zheng, Y., Ling, H., Shi, H., & Chen, H. (2014a). Emergency railway wagon scheduling by hybrid biogeography-based optimization. Computers & Operations Research, 43(1), 1–8.
go back to reference Zheng, Y., Ling, H., & Xue, J. (2014b). Ecogeography-based optimization: Enhancing biogeography-based optimization with ecogeographic barriers and differentiations. Computers & Operations Research, 50, 115–127. Zheng, Y., Ling, H., & Xue, J. (2014b). Ecogeography-based optimization: Enhancing biogeography-based optimization with ecogeographic barriers and differentiations. Computers & Operations Research, 50, 115–127.
Metadata
Title
A hybrid evolutionary approach to job-shop scheduling with generic time lags
Authors
Madiha Harrabi
Olfa Belkahla Driss
Khaled Ghedira
Publication date
01-06-2021
Publisher
Springer US
Published in
Journal of Scheduling / Issue 3/2021
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-021-00683-w

Other articles of this Issue 3/2021

Journal of Scheduling 3/2021 Go to the issue