# A heuristic algorithm for two-machine re-entrant shop scheduling

Drobouchevitch, I. G. and Strusevich, V. A.
(1999)
*A heuristic algorithm for two-machine re-entrant shop scheduling.*
Annals of Operations Research, 86.
pp. 417-439.
ISSN 0254-5330 (Print), 1572-9338 (Online)
(doi:10.1023/A:1018927407164)

## Abstract

This paper considers the problem of sequencing n jobs in a two‐machine re‐entrant shopwith the objective of minimizing the maximum completion time. The shop consists of twomachines, M1 and M2 , and each job has the processing route (M1 , M2 , M1 ). An O(n log n)time heuristic is presented which generates a schedule with length at most 4/3 times that ofan optimal schedule, thereby improving the best previously available worst‐case performanceratio of 3/2.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | re-entrant shop scheduling, approximation algorithm, worst-case analysis, |

Subjects: | Q Science > QA Mathematics |

Pre-2014 Departments: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |

Related URLs: | |

Last Modified: | 14 Oct 2016 08:59 |

URI: | http://gala.gre.ac.uk/id/eprint/148 |

### Actions (login required)

View Item |