Skip navigation

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

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)

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:
Last Modified: 14 Oct 2016 08:59
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/148

Actions (login required)

View Item View Item