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:https://doi.org/10.1023/A:1018927407164)

Full text not available from this repository.

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:	Publisher
Last Modified:	14 Oct 2016 08:59
URI:	http://gala.gre.ac.uk/id/eprint/148

Actions (login required)

View Item