00-14
How Many Sequences Solve an Open Shop Problem?
by Tautenhahn, T.; Willenius, P.
Preprint series: 00-14, Preprints
Abstract: We consider the classical open shop problem to minimize makespan. For this problem, a feasible combination of all job ordes and machine orders is called a sequence. Structural investigations lead to a dominance relation between sequences in the sense that if a sequence A dominates a sequence B then the makespan of A is smaller than or equal to the makespan of B independently of the given processing times. In this paper we generalize this concept by examination a dominance relation between sets of sequences. We give several necessary and sufficient conditions for a sequence to be dominated by a set of other sequences. Moreover, we show that this relation can be formulated as a mixed integer program. Using these results, for some small formats we are able to compute a minimal set of sequences with the property that for any choise of processing times this set contains at least one optimal sequence.
Keywords: open shop
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.