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

Madiha Harrabi (), Olfa Belkahla Driss and Khaled Ghedira
Additional contact information
Madiha Harrabi: Université de Manouba
Olfa Belkahla Driss: Université de Manouba
Khaled Ghedira: Université Centrale de Tunis, Honoris United Universities

Journal of Scheduling, 2021, vol. 24, issue 3, No 5, 329-346

Abstract: 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.

Keywords: BBO; Job shop; Scheduling; Optimization; Time lag (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-021-00683-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:24:y:2021:i:3:d:10.1007_s10951-021-00683-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-021-00683-w

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().