A multistart biased random key genetic algorithm for the flexible job shop scheduling problem with transportation

• Published in: International transactions in operational research 2023-03, Vol.30 (2), p.688-716
• Main Authors: Homayouni, S. Mahdi, Fontes, Dalila B. M. M., Gonçalves, José F.
• Format: Article
• Language: English
• Subjects: BRKGA; flexible job shop scheduling; genetic algorithm; Genetic algorithms; Greedy algorithms; Job shop scheduling; Job shops; joint scheduling; Modular structures; Operations research; Scheduling; Transportation; transportation scheduling
• ISSN: 0969-6016; 1475-3995
• DOI: 10.1111/itor.12878

This work addresses the flexible job shop scheduling problem with transportation (FJSPT), which can be seen as an extension of both the flexible job shop scheduling problem (FJSP) and the job shop scheduling problem with transportation (JSPT). Regarding the former case, the FJSPT additionally considers that the jobs need to be transported to the machines on which they are processed on, while in the latter, the specific machine processing each operation also needs to be decided. The FJSPT is NP‐hard since it extends NP‐hard problems. Good‐quality solutions are efficiently found by an operation‐based multistart biased random key genetic algorithm (BRKGA) coupled with greedy heuristics to select the machine processing each operation and the vehicles transporting the jobs to operations. The proposed approach outperforms state‐of‐the‐art solution approaches since it finds very good quality solutions in a short time. Such solutions are optimal for most problem instances. In addition, the approach is robust, which is a very important characteristic in practical applications. Finally, due to its modular structure, the multistart BRKGA can be easily adapted to solve other similar scheduling problems, as shown in the computational experiments reported in this paper.