LINEAR ORDER CONGRUENCES AND PARALLEL SHEDULING PROBLEMS WITH PRECEDENCE CONSTRAINTS.

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. [ABSTRACT FROM AUTHOR]