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

AbstractWe 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