Zurück zu den Preprints des Jahres 2000


On Algebraic Structures in Shop-Scheduling Problems: The Super-Sequence Group

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

Series: 2000-15, Preprints

90B35 Scheduling theory, deterministic

In a shop-scheduling problem a set of n jobs has to be
processed on a set of m machines. The order of machines of a
job i is called machine-order of job i and the order of jobs
which are processed on machine j is called job-order on
machine j. In each shop-scheduling problem we have to determine
a sequence, i.e. a feasible combination of all machine-orders and all
job-orders, which is optimal with respect to a given objective
function. May be, the set of sequences is more restricted by
additional constraints.
It is well-known, that the machine-orders can be described by a
matrix of order n x m, each row is a permutation of the integers
1 to m. Each matrix with n rows and m columns can be interpreted
as matrix of job-orders if each column is a permutation of
1,...,n. Therefore, we introduce row-latin and column-latin
rectangles and obtain groups by defining an operation on both
sets. The direct product of both groups is called super-sequence group
because it contains a subset which represents all sequences.
We start the algebraic investigations of this group and
interprete the results within the framework of scheduling.

shop-scheduling problems, algebraic structures