Skip navigation

Approximation results for flow shop scheduling problems with machine availability constraints

Approximation results for flow shop scheduling problems with machine availability constraints

Kubzin, Mikhail A., Potts, Chris N. and Strusevich, Vitaly A. (2009) Approximation results for flow shop scheduling problems with machine availability constraints. Computers & Operations Research, 36 (2). pp. 379-390. ISSN 0305-0548 (doi:10.1016/j.cor.2007.10.013)

Full text not available from this repository.

Abstract

This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed.

Item Type: Article
Additional Information: Available online 11 October 2007.
Uncontrolled Keywords: flow shop scheduling, machine non-availability, approximation algorithm
Subjects: T Technology > T Technology (General)
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
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:03
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/1301

Actions (login required)

View Item View Item