Skip navigation

A new heuristic for three-machine flow shop scheduling

A new heuristic for three-machine flow shop scheduling

Chen, Bo, Glass, Celia A., Potts, Chris N. and Strusevich, Vitaly A. (1996) A new heuristic for three-machine flow shop scheduling. Operations Research, 44 (6). pp. 891-898. ISSN 0030-364X (Print), 1526-5463 (Online) (doi:10.1287/opre.44.6.891)

Full text not available from this repository.

Abstract

This paper considers the problem of sequencing n jobs in a three-machine flow shop with the objective of minimizing the makespan, which is the completion time of the last job. An O(n log n) time heuristic that is based on Johnson's algorithm is presented. It is shown to generate a schedule with length at most 5/3 times that of an optimal schedule, thereby reducing the previous best available worst-case performance ratio of 2. An application to the general flow shop is also discussed.

Item Type: Article
Uncontrolled Keywords: production/scheduling, flow shop, approximations/heuristic, 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/23

Actions (login required)

View Item View Item