A Multiple-Criterion Model for Machine Scheduling |
| |
Authors: | Kenneth R Baker J Cole Smith |
| |
Affiliation: | (1) Tuck School of Business, Dartmouth College, Hanover, New Hampshire, NE 03755, USA;(2) Tuck School of Business, Dartmouth College, Hanover, New Hampshire, NE 03755, USA;(3) Department of Systems and Industrial Engineering, University of Arizona, Tucson, AZ 85721, USA |
| |
Abstract: | We consider a scheduling problem involving a single processor being utilized by two or more customers. Traditionally, such scenarios are modeled by assuming that each customer has the same criterion. In practice, this assumption may not hold. Instead of using a single criterion, we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated based on their individual criteria. We examine three basic scheduling criteria: minimizing makespan, minimizing maximum lateness, and minimizing total weighted completion time. Although determining a minimum-cost schedule according to any one of these criteria is polynomially solvable, we demonstrate that when minimizing a mix of these criteria, the problem becomes NP-hard. |
| |
Keywords: | sequencing single machine multiple criteria complexity |
本文献已被 SpringerLink 等数据库收录! |
|