Strusevich, V.A., Drobouchevitch, I.G. and Shakhlevich, N.V. (2002) Three-machine shop scheduling with partially ordered processing routes. Journal of the Operational Research Society, 53 (5). pp. 574-582. ISSN 0160-5682 (Print), 1476-9360 (Online) (doi:https://doi.org/10.1057/palgrave.jors.2601329)

Full text not available from this repository.

Abstract

This paper considers the problem of sequencing n jobs in a three-machine shop with the objective of minimising the maximum completion time. The shop consists of three machines, M1,M2 and M_{3}. A job is first processed on M1 and then is assigned either the route (M2,M_{3}) or the route (M_{3},M2). Thus, for our model the processing route is given by a partial order of machines, as opposed to the linear order of machines for a job shop, or to an arbitrary sequence of machines for an open shop. The main result is on O(nlog n) time heuristic, which generates a schedule with the makespan that is at most 5/3 times the optimum value.

Item Type:	Article
Uncontrolled Keywords:	shop scheduling, approximation algorithm, worst-case analysis
Subjects:	Q Science > QA Mathematics > QA76 Computer software
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 Publisher Organisation
Last Modified:	14 Oct 2016 09:01
URI:	http://gala.gre.ac.uk/id/eprint/582

Actions (login required)

View Item