Solving precedence constrained parallel scheduling problems by greedy algorithms generated order congruences

Abstract

Scheduling problems can be alternately approached by methods based on discrete mathematicaltools. Studying the order congruences of partially ordered sets it became clear that the minimal linear order congruences can be successfully applied in solving scheduling problems. This technique can be used in the single machine case and it can be extended to multimachine environment where machines work parallelly. In this paper we discuss scheduling problems given by precedence constraints and show algorithms yielding optimal or quasi optimal solutions in the form of minimal linear congruences.