Paper Info
Title
On-line two-machine job shop scheduling with time lags
Abstract
We consider the on-line two-machine job shop scheduling problem with time lags so as to minimize the makespan. Each job consists of no more than two operations and time lags exist between the completion time of the first and the start time of the second operation of any two-operation job. We prove that any greedy algorithm is 2-competitive. For the non-clairvoyant variant of the problem, no on-line algorithm can do better. For the clairvoyant variant, no on-line delay algorithm has a competitive ratio better than 5+12~1.618, and a greedy algorithm is still the best on-line non-delay algorithm. We also show that the same results hold for the two-machine flow shop problem with time lags.
Year
DOI
Venue
2010
10.1016/j.ipl.2010.04.002
Inf. Process. Lett.
Keywords
Field
DocType
time lag,on-line two-machine job shop,start time,on-line algorithm,completion time,greedy algorithm,on-line delay algorithm,on-line non-delay algorithm,two-machine flow shop problem,scheduling problem,job shop scheduling,competitive ratio,scheduling,competitive analysis
Information processing,Job shop scheduling,Scheduling (computing),Computer science,Job shop,Flow shop scheduling,Algorithm,Greedy algorithm,Retard,Competitive analysis
Journal
Volume
Issue
ISSN
110
12-13
0020-0190
Citations 
PageRank 
References 
4
0.44
8
Authors
2
Name
Order
Citations
PageRank
Xiandong Zhang1303.70
Steef van de Velde2213.31