SINGLE MACHINE SCHEDULING WITH SERIES-PARALLEL PRECEDENCE CONSTRAINTS.

Abstract

Consideration is given to a set of tasks to be sequenced for processing on a single machine. The possible sequences may be restricted by given precedence constraints. Fot each feasible sequence we have an additive cost function (e. g. tardiness or weighted tardiness) and the objective is to find a feasible sequence with minimal total cost. An efficient algorithm is presented for the case when the set of precedence constraints can be represented by a series-parallel graph. The algorithm is based on the earlier known dynamic programming approach, its main new achievement is the use of a compact labeling scheme for series-parallel graphs which is the best possible in a certain sense. Show more