Zurück zu den Preprints des Jahres 2001


On Algebraic Properties in Shop Scheduling Problems

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

Series: 2001-08, Preprints

90B35 Scheduling theory, deterministic

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.

shop scheduling problems, Hamming graph, groups, latin rectangles