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 review. Here we focus on a flexible job shop scheduling problem of minimizing the makespan in a two-center job shop, where the first center consists of one machine and the second consists of k parallel machines. We provide an easy-to-perform approximation algorithm that solves the problem optimally when k=1. A modification of the algorithm provides an optimal solution for k=2. For k≥3, the algorithm approximates the optimal solution within an absolute worst-case error bound of k−1. Surprisingly, this error bound is independent of the number of jobs to be processed. Also and importantly, the proposed algorithm runs in polynomial time and numerical experiments show its advantages in solving two-center flexible job shop problems