LINEAR ORDER CONGRUENCES AND PARALLEL SHEDULING PROBLEMS WITH PRECEDENCE CONSTRAINTS

Abstract

Scheduling problems can be alternately approached by methods based on discrete
mathematical tools. One obtains a model of a given production technology by representing the
relations of the phases of production as partial ordered sets. To solve the scheduling problem in
such a case one basically needs a linear order. As an important result of the theory of partial
orders we can cite the Szpilrajn theorem, stating that each partial order can be extended to a
linear order. Studying the order congruences of partially ordered sets it became clear that the
minimal linear order congruences can be successfully applied in investigating scheduling
problems. An algorithm for finding minimal linear order congruences is introduced, and a
partition of jobs obtained which carries important information about the solution of the parallel
scheduling problem.