Scheduling Unit-Time Open Shops with Deadlines

We consider open shop problems with unit processing times and due dates, 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 work on automobiles. In an earlier paper, C. Y. Liu and R. L. Bulfin gave an O(n²m) algorithm to minimize total tardiness and the number of tardy jobs. We will give a polynomial algorithm to minimize the completion time of all jobs where a deadline is imposed for each job. The complexity of this problem is still open. Then we apply this solution to give improved algorithms to minimize the number of tardy jobs and the maximum lateness.