Single Machine Scheduling with Series-Parallel Precedence Constraints

This paper considers a set of tasks to be sequenced for processing on a single machine. The possible sequences may be restricted by given precedence constraints. For 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.