SCHEDULING UNIT-TIME OPEN SHOPS WITH DEADLINES

We consider open shop problems with unit processing times and due date s, where n jobs have to be processed on m machines. The order in which a given job is processed on the machines is not fixed. Such problems occur in testing components of an electronic system or doing repair wo rk on automobiles. In an earlier paper, C. Y. Liu and R. L. Bulfin gav e an O(n2m) algorithm to minimize total tardiness and the number of ta rdy jobs. We will give a polynomial algorithm to minimize the completi on time of all jobs where a deadline is imposed for each job. The comp lexity of this problem is still open, Then we apply this solution to g ive improved algorithms to minimize the number of tardy jobs and the m aximum lateness.