Minimizing makespan in no-wait job shops

• 成果类型: Article
• 署名作者: Bansal, N; Mahdian, M; Sviridenko, M
• 署名单位: International Business Machines (IBM); IBM USA; Microsoft
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1050.0155
• 发表日期: 2005
• 页码: 817-831
• 关键词: flow shops; minimization; approximability; blocking; machine

摘要

In this paper, we study polynomial time approximation schemes (PTASes) for the no-wait job shop scheduling problem with the makespan objective function. It is known that the problem is MaxSNP-hard in the case when each job is allowed to have three operations or more. We show that if each job has at most two operations, the problem admits a PTAS if the number of machines is a constant (i.e., not part of the input). If the number of machines is not a constant, we show that the problem is hard to approximate within a factor better than 5/4.