Three-machine shop scheduling with partially ordered processing routes

V A Strusevich (), I G Drobouchevitch and N V Shakhlevich
Additional contact information
V A Strusevich: University of Greenwich
I G Drobouchevitch: University of Ottawa
N V Shakhlevich: University of Leeds

Journal of the Operational Research Society, 2002, vol. 53, issue 5, 574-582

Abstract: 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.

Keywords: shop scheduling; approximation algorithm; worst-case analysis (search for similar items in EconPapers)
Date: 2002
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601329 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:53:y:2002:i:5:d:10.1057_palgrave.jors.2601329

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601329

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().