Multiple Criteria Scheduling on a Single Machine: A Review and a General Approach

Scheduling problems have been treated as single criterion problems until recently. Many of these problems are computationally hard to solve even as single criterion problems. However, there is a need to consider multiple criteria in a real life scheduling problem in general. In recent years, many articles considering bicriteria scheduling problems, and some articles considering more than two criteria started to appear in the literature. We briefly review various categories of approaches on multiple criteria scheduling on a single machine. We then present a general approach to find the most preferred schedule in a bicriteria environment for any given nondecreasing composite function of the criteria.