Skip navigation

A greedy open shop heuristic with job priorities

A greedy open shop heuristic with job priorities

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: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:
Last Modified: 14 Oct 2016 08:59
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/132

Actions (login required)

View Item View Item