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-0548Full text not available from this repository.
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.
|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
|School / Department / Research Groups:||School of Computing & Mathematical Sciences|
School of Computing & Mathematical Sciences > Department of Mathematical Sciences
School of Computing & Mathematical Sciences > Statistics & Operational Research Group
|Last Modified:||09 Oct 2012 17:00|
Actions (login required)