POLYNOMIAL-TIME ALGORITHMS FOR SPECIAL OPEN SHOP PROBLEMS WITH PRECEDENCE CONSTRAINTS AND UNIT PROCESSING TIMES

In this paper we consider different open shop problems with unit proce ssing times. For the problem with two machines and arbitrary precedenc e constraints among the jobs, we give a polynomial time algorithm for the minimization of the makespan with a better worst case complexity t han a previous algorithm known from the literature if the number of ar cs is of linear order. The complexity of the the open shop problem wit h unit processing times and intree constraints among the jobs was open up to now if the mim of completion times of the jobs has to be minimi zed. By means of the first result we give a polynomial time algorithm for this problem with two machines.