Single machine sequencing with nonlinear multicriteria cost functions: An application of generalized dynamic programming

A task frequently encountered in operations management is the scheduling of tasks or jobs where the attractiveness of the schedule is evaluated relative to multiple performance measures. If there exists a linear multicriteria cost (or penalty) function of these performance measures, then dynamic programming (DP) may be used to find an optimal schedule. However, in the more general case of a nonlinear multicriteria cost function, conventional DP may fail to produce an optimal schedule due to the potential violation of monotonicity. Furthermore, the alternative of first generating the entire efficient set (over which the multicriteria cost function can subsequently be minimized) often requires a prohibitive computational effort. The authors present an alternative generalized DP approach to this class of problems that guarantees optimality, notwithstanding the nonlinearity of the cost function. An example demonstrates that the present approach can represent a significant computational improvement over first generating the entire efficient set, and is only slightly more expensive computationally than applying conventional DP, which in this case is only a heuristic.