SCHEDULING UNIT-TIME OPEN SHOPS WITH DEADLINES

• 成果类型: Note
• 署名作者: TAUTENHAHN, T
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.42.1.189
• 发表日期: 1994
• 页码: 189-192
• 关键词: Production; Scheduling; open shop

摘要

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(n2m) 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.