Breit, Joachim, Schmidt, Günter and Strusevich, Vitaly A. (2001) Two-machine open shop scheduling with an availability constraint. Operations Research Letters, 29 (2). pp. 65-77. ISSN 0167-6377 (doi:10.1016/S0167-6377(01)00079-7)

Full text not available from this repository.

Abstract

We study a two-machine open shop scheduling problem, in which one machine is not available for processing during a given time interval. The objective is to minimize the makespan. We show that the problem is NP-hard and present an approximation algorithm with a worst-case ratio of 4/3.

Item Type:	Article
Uncontrolled Keywords:	open shop scheduling, availability constraints, worst-case analysis
Subjects:	Q Science > QA Mathematics
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:	Publisher
Last Modified:	14 Oct 2016 09:01
URI:	http://gala.gre.ac.uk/id/eprint/579

Actions (login required)

View Item