MEAN FLOW TIME MINIMIZATION IN REENTRANT JOB SHOPS WITH A HUB

This paper considers a reentrant job shop with one hub machine which a job enters K limes. Between any two consecutive entries into the hub: the job is processed on other machines. The objective is to minimize the total Bow time. Under two key assumptions, the bottleneck assumpti on and the hereditary order (HO) assumption on the processing times of the entries, it is proved that there is an optimal schedule with the shortest processing time (SPT) job order and a dynamic programming alg orithm is derived to find such a schedule. An approximation algorithm based on the shortest path algorithm and the SPT job order is also pro posed ro solve the problem. The approximation algorithm finds an optim al clustered schedule. In clustered schedules, jobs are scheduled in d isjoint clusters; they resemble hatch processing and seem to be of pra ctical importance. Worst-case bounds for clustered schedules are prove d with the HO assumption relaxed. Two special cases with the restricti on that there are only two entries to the hub machine are further anal yzed to offer more insight into the structure of optimal solutions.