Strusevich, V.A. (1998) A greedy open shop heuristic with job priorities. Annals of Operations Research, 83. pp. 253-270. ISSN 0254-5330 (Print), 1572-9338 (Online) (doi:https://doi.org/10.1023/A:1018964131329)

Full text not available from this repository.

Abstract

The paper presents an improved version of the greedy open shop approximation algorithm with pre-ordering of jobs. It is shown that the algorithm compares favorably with the greedy algorithm with no pre-ordering by reducing either its absolute or relative error. In the case of three machines, the new algorithm creates a schedule with the makespan that is at most 3/2 times the optimal value.

Item Type:	Article
Additional Information:	[1] Please note: This revised version was published online in August 2006 with corrections to the Cover Date.
Uncontrolled Keywords:	open shop scheduling, approximation algorithm, 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 08:59
URI:	http://gala.gre.ac.uk/id/eprint/132

Actions (login required)

View Item