|
Abstract : |
Abstract. 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 unittime operations such that the machines have to process them by turn begining with a given machine; nd a schedule minimizing the maximum job completion time. Formerly, only pseudopolynomial-time algorithms have been proposed for this problem. Key words and phrases. Job-shop scheduling, unit-time operations, release dates, due dates, schedule length, maximum lateness, polynomial-time algorithm., |
