Abstract:
This paper is concerned with the makespan problem of scheduling groups of jobs in two machine open shop. The problem is known as NP hard no matter whether group sub lotting is admissible or not. We obtain an approximation algorithm which generates a GT schedule (in which no group is split) with the worst case performance ratio 5/4, even when the GT schedule is used as a solution to the group sub lotting case. Besides, we give a polynomial algorithm to solve the one group case to optimality.