AN IMPROVED APPROXIMATION ALGORITHM FOR THE TWO-MACHINE FLOW SHOP SCHEDULING PROBLEM WITH AN INTERSTAGE TRANSPORTER

Autor:	Vitaly A. Strusevich, Alan Soper
Rok vydání:	2007
Předmět:	Mathematical optimization Schedule Linear programming Strongly polynomial Heuristic (computer science) Computer science Small number Computer Science (miscellaneous) Approximation algorithm Flow shop scheduling Algorithm Integer (computer science)
Zdroj:	International Journal of Foundations of Computer Science. 18:565-591
ISSN:	1793-6373 0129-0541
DOI:	10.1142/s012905410700484x
Popis:	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 [Formula: see text]–approximation algorithm that outputs a two-shipment schedule. We design a [Formula: see text]–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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::7e9520a32c217bae1d8326943d2f3d44 https://doi.org/10.1142/s012905410700484x Zobrazit plný text záznamu