00-15
On Algebraic Structures in Shop-Scheduling Problems: The Super-Sequence Group
Preprint series: 00-15, Preprints
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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.