Efficient algorithms for flexible job shop scheduling with parallel machines

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 .