# 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)

## 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 |

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 |

Related URLs: | |

Last Modified: | 09 Oct 2012 17:00 |

URI: | http://gala.gre.ac.uk/id/eprint/1301 |

### Actions (login required)

View Item |