Premium
Efficient algorithms for flexible job shop scheduling with parallel machines
Author(s) -
Kubiak Wieslaw,
Feng Yanling,
Li Guo,
Sethi Suresh P.,
Sriskandarajah Chelliah
Publication year - 2020
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21901
Subject(s) - job shop scheduling , computer science , scheduling (production processes) , schedule , upper and lower bounds , mathematical optimization , algorithm , flow shop scheduling , mathematics , mathematical analysis , operating system
Abstract Job shop scheduling with a bank of machines in parallel is important from both theoretical and practical points of view. Herein we focus on the scheduling problem of minimizing the makespan in a flexible two‐center job shop. The first center consists of one machine and the second has k parallel machines. An easy‐to‐perform approximate algorithm for minimizing the makespan with one‐unit‐time operations in the first center and k ‐unit‐time operations in the second center is proposed. The algorithm has the absolute worst‐case error bound of k − 1 , and thus for k = 1 it is optimal. Importantly, it runs in linear time and its error bound is independent of the number of jobs to be processed. Moreover, the algorithm can be modified to give an optimal schedule for k = 2 .