01-08
On Algebraic Properties in Shop Scheduling Problems
Preprint series: 01-08, Preprints
Abstract: In this paper investigations in graph theory, algebra and scheduling theory are combined to develop new properties of the super sequence group (SSG). The SSG contains all pairs (MO,JO) where MO and JO are the matrices of all machine orders (row-latin rectangles) and all job orders (column-latin rectangles) in an n x m open shop problem, respectively. To each (MO,JO) a transitive shop graph G(MO,JO) is one-to-one assigned, where G(MO,JO) can be also interpreted as orientation of the Hamming graph Kn x Km. Each acyclic orientation yields to a sequence, i.e., a feasible solution in the open shop. First we develop a linear time algorithm for recognizing a digraph as transitive shop graph and calculate the order of elements in the SSG. By a new concept of so-called fundamental cycles and dicycles using the Hamming graph Kn x Km, the problem of feasibility of (MO,JO) is reduced to the existence of fundamental dicycles in G(MO,JO). Therefore, a linear time algorithm can be given to determine one fundamental dicycle in any cyclic G(MO,JO). Moreover, we are able to solve some counting problems in this area, for instance, the number of pairs (MO,JO) where G(MO,JO) contains at least one fixed fundamental dicycle. Finally, we investigate subgroups of the SSG with respect to the set of irreducible sequences and develop interesting connections between both fields.
Keywords: shop scheduling problems, Hamming graph, groups, latin rectangles
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.