On the set of solutions of the open shop problem

On the set of solutions of the open shop problem

0.00 Avg rating0 Votes
Article ID: iaor20013884
Country: Netherlands
Volume: 92
Start Page Number: 241
End Page Number: 263
Publication Date: Nov 1999
Journal: Annals of Operations Research
Authors: , , ,
Abstract:

In the classical open shop problem, n jobs have to be processed on 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 is called a (multi-) sequence. We investigate a set of sequences which are structurally optimal in the sense that there is at least one optimal sequence in this set for each instance of processing times. Such sequences are called irreducible. Investigations about irreducible sequences are believed to provide a powerful tool to improve exact and heuristic algorithms. Furthermore, structural properties of sequences are important for problems with uncertain processing times. We prove necessary and sufficient conditions for the irreducibility of a sequence. For several values of n and m, we give the numbers of all sequences, of the sequences satisfying each of these conditions and of the irreducible sequences, respectively. It turns out that only a very small fraction of all sequences is irreducible. Thus, algorithms which work only on the set of irreducible sequences instead of the set of all sequences can potentially perform much better than conventional algorithms.

Reviews

Required fields are marked *. Your email address will not be published.