A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem

✍ Scribed by Vadim G. Timkovsky

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 1014 KB
• Volume: 77
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00106-0

✦ Synopsis

We consider a polynomial-time algorithm for the following scheduling problem: Given two machines, where each machine can process at most one job at a time; a set of jobs, where each job can start on or after its release date and consists of a chain of unit-time operations such that the machines have to process them by turn begining with a given machine; find a schedule minimizing the maximum job completion time. Formerly, only pseudopolynomial-time algorithms have been proposed for this problem.