×

Incorporating preference information into multi-objective scheduling. (English) Zbl 0809.90077

Summary: Multicriteria 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.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bagchi, U., Simultaneous minimization of mean and variation of flow and waiting time in single machine systems, Operations Research, 37, 118-125 (1989) · Zbl 0661.90046
[2] Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York
[3] Boyd, D. W., A methodology for analyzing decision problems involving complex preference assessments, (Ph.D. Dissertation (1970), Stanford University)
[4] Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500
[5] Daniels, R. L., A multi-objective approach to resource allocation in single machine scheduling, European Journal of Operational Research, 48, 226-241 (1990) · Zbl 0825.90535
[6] Daniels, R. L.; Chambers, R. J., Multi-objective flow shop scheduling, Naval Research Logistics, 37, 981-995 (1990) · Zbl 0825.90551
[7] Daniels, R. L.; Sarin, R. K., Single machine scheduling with controllable processing times and number of jobs tardy, Operations Research, 37, 981-984 (1989) · Zbl 0686.90023
[8] Debreu, G., Representation of a preference ordering by a numerical function, (Thrall, R.; Coombs, C.; Davis, R., Decision Processes (1954), Wiley: Wiley New York) · Zbl 0058.13803
[9] Geoffrion, A. M.; Dyer, J. S.; Feinberg, A., An interactive approach for multi-criterion optimization, with an application to the operations of an academic department, Management Science, 19, 357-368 (1972) · Zbl 0247.90069
[10] Jackson, J. R., Scheduling a production line to minimize maximum tardiness, (Research Report 43, Management Sciences Research Project (1955), UCLA)
[11] Lenstra, J. K., Sequencing by enumerative methods (1979), Mathematisch Centrum: Mathematisch Centrum Amsterdam · Zbl 0407.90025
[12] Lin, K. S., Hybrid algorithm for sequencing with bicriteria, Journal of Optimization Theory and Applications, 39, 105-124 (1983) · Zbl 0479.90051
[13] Moore, J. M., An \(n\) job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15, 102-109 (1968) · Zbl 0164.20002
[14] Nelson, R. T.; Sarin, R. K.; Daniels, R. L., Scheduling with multiple performance measures; the one-machine case, Management Science, 32, 464-479 (1986) · Zbl 0603.90070
[15] Sen, T.; Raizaheh, F. M.E.; Dileepan, P., A branch and bound approach to the bicriterion scheduling problem involving total flowtime and range of lateness, Management Science, 34, 254-260 (1988) · Zbl 0638.90056
[16] Shiraishi, N., An interactive procedure for designing an inventory system, (Master’s Thesis (1982), University of California: University of California Los Angeles, CA)
[17] Smith, W. E., Various optimizers of single stage production, Naval Research Logistics Quarterly, 3, 59-66 (1956)
[18] Srinivasan, V., A hybrid algorithm for the one-machine problem to minimize total tardiness, Naval Research Logistics, 18, 317-327 (1971) · Zbl 0229.90029
[19] Van Wassenhove, L. N.; Baker, K. R., A bicriterion approach to time/cost trade-offs in sequencing, European Journal of Operational Research, 11, 48-54 (1982) · Zbl 0482.90043
[20] Van Wassenhove, L. N.; Gelders, L. F., Solving a bicriterion scheduling problem, European Journal of Operational Research, 4, 42-48 (1980) · Zbl 0418.90054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.