A FPTAS Based Scheduling of a New Hub Reentrant Shop

We study a variant of the reentrant shop problem of minimizing makespan in one hub machine M₁ and two machine centers M₂ and M₃ (each center consists of some identical machines). In the problem, each job has five operations, where the first, the third and the fifth operation must be performed on hub machine M₁, the second operation can be performed on any one machine in M₂ and the forth operation can be performed on any one machine in M₃. We show the problem is strongly NP-hard, which motivates us to design approximation algorithms. We give a fully polynomial time approximation scheme (FPTAS) for the job-machine assignment decision in M₂ and M₃. Based on the FPTAS, we then provide a mixed integer linear programming (MILP) to schedule job operations optimally.