Paper Info
Title
An Improved Approximation Algorithm For The Two-Machine Flow Shop Scheduling Problem With An Interstage Transporter
Abstract
We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a 3/2-approximation algorithm that outputs a two-shipment schedule. We design a 4/3-approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.
Year
DOI
Venue
2007
10.1142/S012905410700484X
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
Field
DocType
flow shop scheduling, scheduling with transportation, approximation algorithm, linear relaxation
Integer,Small number,Approximation algorithm,Heuristic,Mathematical optimization,Computer science,Flow shop scheduling,Algorithm,Strongly polynomial,Schedule,Linear programming
Journal
Volume
Issue
ISSN
18
3
0129-0541
Citations 
PageRank 
References 
3
0.46
3
Authors
2
Name
Order
Citations
PageRank
ALAN J. SOPER1254.48
Vitaly A. Strusevich271661.09