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

**Series:** 2000-15, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**Abstract:**

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.

**Keywords:**

shop-scheduling problems, algebraic structures