Single-machine scheduling with mixed precedence constraints

The paper deals with a single machine scheduling problem involving a general precedence structure that permits both ordinary and fuzzy precedence constraints. Feasible schedules are evaluated not only by their cost but also by the degree of satisfaction with their precedence structure. An O(mlogn + max(n², kn²))-time algorithm is proposed for finding nondominated solutions of the resulting bi-criteria scheduling problem where n is the number of jobs, k is the number of fuzzy constraints, and m is the total number of precedence constraints.