An approximation algorithm for the two-machine flow shop with a single transporter
Tools
Tools
Soper, Alan
ORCID: 0000-0002-0901-9803
and Strusevich, Vitaly A.
(2007)
An approximation algorithm for the two-machine flow shop with a single transporter.
International Journal of Foundations of Computer Science (ijfcs), 18 (3).
pp. 565-591.
ISSN 0129-0541
(doi:https://doi.org/10.1142/S012905410700484X)
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 –approximation algorithm that outputs a two-shipment schedule. We design a –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.
| Item Type: | Article |
|---|---|
| Additional Information: | This paper forms part of the published proceedings from 8th Workshop on Models and Algorithms for Planning and Scheduling (MAPSP 2007), Istanbul, Turkey, July 2-6, 2007 |
| Uncontrolled Keywords: | flow shop scheduling, scheduling with transportation, approximation algorithm, linear relaxation, |
| Subjects: | Q Science > QA Mathematics |
| Pre-2014 Departments: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Computer & Computational Science Research Group School of Computing & Mathematical Sciences > Department of Computer Science School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |
| Related URLs: | |
| Last Modified: | 30 Sep 2019 15:04 |
| URI: | http://gala.gre.ac.uk/id/eprint/1168 |
Actions (login required)
 |
View Item |