SequencingnJobs on Two Machines with Arbitrary Time Lags

Abstract

Each of n jobs must be run first on machine I and then on machine I . Running times for each job on each machine are given. Also specified are arbitrary time lags which prescribe that a job may not be started (completed) on machine II until at least a certain time has elapsed since starting (completing) the job on machine I . A rule is given for determining the sequence in which jobs are to be run on the machines—using the same sequence for both machines—in order to minimize the time between the start of production of the first job on machine I and the completion of production of the last job on machine II .