Optimal Permutation and Non-permutation Scheduling for a Two-machine Robotic Unit with an Intermediate Station

摘要

In this paper we consider the scheduling problem of minimizing the maximum completion time (i.e., the makespan) for a two-machine robotic unit of flowshop type, in which each of n jobs is processed on machine one and later on machine two. There is an intermediate station between the two machines for intermediate operations such as washing, chip disposal, cooling, drying and/or quenching. If only permutation schedules are allowed (i.e., the sequences of jobs on the two machines have to be the same), the scheduling problem is referred to as the permutation version. In this paper, we show that the permutation version of the problem can be solved in polynomial time, although the non-permutation problem (i.e., the original problem) is NP-hard in the strong sense. Moreover, we show that, if the optimal permutation schedule is used as an approximate solution for the non-permutation problem, it gives a maximum completion time within twice of the exact minimum.