Job shop scheduling with unit processing times

• 成果类型: Article
• 署名作者: Bansal, Nikhil; Kimbrel, Tracy; Sviridenko, Maxim
• 署名单位: International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1060.0189
• 发表日期: 2006
• 页码: 381-389
• 关键词: makespan minimization; bounds

摘要

We consider randomized algorithms for the preemptive job shop problem, or equivalently, the case in which all operations have unit length. We give an a-approximation for the case of two machines where alpha < 1.45, an improved approximation ratio of O(log m/log log m) for an arbitrary number m of machines, and the first (2 + epsilon) -approximation for a constant number of machines. The first result is via an approximation algorithm for a string matching problem that is of independent interest.