by Braesel, H., Dhamala, T.N..

**Series:** 2001-08, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**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