Incorporating preference information into multi-objective scheduling

Multi-criteria scheduling problems have typically been formulated with an objective of identifying the entire set of schedules efficient with respect to the performance measures of interest. This paper focuses on multi-objective scheduling situations where information concerning the relative importance of the criteria is available through interaction with a given decision maker. In addition to providing a means for directly determining the most-preferred schedule for that individual, this preference information can also be exploited to enhance the computational efficiency of the solution process. To demonstrate the latter advantage, three forms of managerial interaction are considered, consistent with situations where (i) no preference information is available, (ii) preferences are completely represented by an additive objective function, and (iii) no explicit objective is given, but a decision maker can precisely provide local trade-off (marginal rates of substitution) information. A general tree-based solution framework is proposed for the three cases, with dominance results and bounds obtained from the available preference information used to simplify the search for the most-preferred schedule. The computational performance of the solution approaches is then experimentally compared to determine the efficiencies that result from the incorporation of preference information.