Drobouchevitch, Inna G. and Strusevich, Vitaly A. (1998) Heuristics for short route job shop scheduling problems. Mathematical Methods of Operations Research, 48 (3). pp. 359-375. ISSN 1432-2994 (Print), 1432-5217 (Online) (doi:10.1007/s001860050033)

Full text not available from this repository.

Abstract

We consider two “minimum”NP-hard job shop scheduling problems to minimize the makespan. In one of the problems every job has to be processed on at most two out of three available machines. In the other problem there are two machines, and a job may visit one of the machines twice. For each problem, we define a class of heuristic schedules in which certain subsets of operations are kept as blocks on the corresponding machines. We show that for each problem the value of the makespan of the best schedule in that class cannot be less than 3/2 times the optimal value, and present algorithms that guarantee a worst-case ratio of 3/2.

Item Type:	Article
Uncontrolled Keywords:	job 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/137

Actions (login required)

View Item