# The two-machine open shop problem: To fit or not to fit, that is the question

Akker van den, Marjan and Hoogeveen, Han and Woeginger, Gerhard J. (2003) *The two-machine open shop problem: To fit or not to fit, that is the question.* Operations Research Letters, 31 (3). pp. 219-224. ISSN 0167-6377

PDF Restricted to UT campus only: Request a copy 125Kb |

Abstract: | We consider the open shop scheduling problem with two machines. Each job consists of two operations, and it is prescribed that the first (second) operation has to be executed by the first (second) machine. The order in which the two operations are scheduled is not fixed, but their execution intervals cannot overlap. We are interested in the question whether, for two given values D1 and D2, there exists a feasible schedule such that the first and second machine process all jobs during the intervals [0,D1] and [0,D2], respectively.
We formulate four simple conditions on D1 and D2, which can be verified in linear time. These conditions are necessary and sufficient for the existence of a feasible schedule. The proof of sufficiency is algorithmical, and yields a feasible schedule in linear time. Furthermore, we show that there are at most two non-dominated points (D1,D2) for which there exists a feasible schedule. |

Item Type: | Article |

Copyright: | © 2003 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/75023 |

Official URL: | http://dx.doi.org/10.1016/S0167-6377(03)00018-X |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 213204