00-33
Irreducible sequences on tree-like operation sets
Preprint series: 00-33, Preprints
Abstract: We consider the classical open shop problem to minimize makespan. For this problem, a semi-active schedule can easily be computed from the processing times and a sequence, i.e., a feasible combination of job orders and machine orders. A sequence is called irreducible if there exists no other sequence such that this other sequence leads to a smaller or equal makespan for any choice of processing times. The question how to decide in polynomial time wheter a given sequence is irreducible is open up to now. We answer this question in the case that the underlying operation set has tree structure. For this case in which the open shop problem itself remains unary NP-hard we can test irreducibility of a sequence in linear time. Furthermore, we consider unavoidable sequences, i.e., sequences which are uniquely optimal for some instance of processing times. Unavoidable sequences are essential for the search of minimal sequence sets with the property that for each instance of processing times this set contains an optimal sequence. We give a necessary condition for unavoidability of a sequence which is conjectured to be sufficient too.
Keywords: open shop
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.