Skip navigation

An open shop scheduling problem with a non-bottleneck machine

An open shop scheduling problem with a non-bottleneck machine

Strusevich, V.A. and Hall, L.A. (1997) An open shop scheduling problem with a non-bottleneck machine. Operations Research Letters, 21 (1). pp. 11-18. ISSN 0167-6377 (doi:10.1016/S0167-6377(97)00030-8)

Full text not available from this repository.

Abstract

This paper considers the problem of processing n jobs in a two-machine non-preemptive open shop to minimize the makespan, i.e., the maximum completion time. One of the machines is assumed to be non-bottleneck. It is shown that, unlike its flow shop counterpart, the problem is NP-hard in the ordinary sense. On the other hand, the problem is shown to be solvable by a dynamic programming algorithm that requires pseudopolynomial time. The latter algorithm can be converted into a fully polynomial approximation scheme that runs in time. An O(n log n) approximation algorithm is also designed whi finds a schedule with makespan at most 5/4 times the optimal value, and this bound is tight.

Item Type: Article
Additional Information: [1] Available online: 10 June 1998. [2] Published in print: August 1997.
Uncontrolled Keywords: open shop, complexity, dynamic programming, fully polynomial approximation scheme, worst-case analysis, approximation
Subjects: Q Science > QA Mathematics > QA76 Computer software
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 09:00
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/394

Actions (login required)

View Item View Item