On the set of solutions of the open shop problem

H. Bräsel, M. Harborth, T. Tautenhahn and P. Willenius

Annals of Operations Research, 1999, vol. 92, issue 0, 263 pages

Abstract: In the classical open shop problem, n jobs have to be processedon m machines, where both job orders and machine orders can be chosen arbitrarily.A feasible (i.e., acyclic) combination of all job orders and machine orders iscalled a (multi‐) sequence. We investigatea set of sequences which are structurally optimal in the sense that there is at least oneoptimal sequence in this set for each instance of processing times. Such sequences arecalled irreducible. Investigations about irreducible sequences are believed to provide apowerful tool to improve exact and heuristic algorithms. Furthermore, structural propertiesof sequences are important for problems with uncertain processing times.We prove necessary and sufficient conditions for the irreducibility of a sequence. Forseveral values of n and m, we give the numbers of allsequences, of the sequences satisfying each of these conditions and of the irreduciblesequences, respectively. It turns out that only a very small fraction of all sequences isirreducible. Thus, algorithms which work only on the set of irreducible sequences insteadof the set of all sequences can potentially perform much better than conventional algorithms. Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018938915709 (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:spr:annopr:v:92:y:1999:i:0:p:241-263:10.1023/a:1018938915709

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018938915709

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().