A multiple-criterion model for machine scheduling
A multiple-criterion model for machine scheduling
复制标题
DOI：
10.1023/a:1022231419049
复制
发表时间：
2003-01-01
影响因子：
2
通讯作者：
Smith, JC
中科院分区：
文献类型：
--
作者：
Baker, KR;Smith, JC
我们考虑一个调度问题，涉及一个单一的处理器被两个或两个以上的客户使用。传统上，这样的场景是通过假设每个客户具有相同的标准来建模的。在实践中，这一假设可能不成立。而不是使用一个单一的标准，我们研究的影响最小化的聚合调度目标函数，属于不同的客户的工作进行评估的基础上，他们的个人标准。我们研究了三个基本的调度标准：最小化最大完工时间，最小化最大延迟，最小化总加权完成时间。虽然根据这些标准中的任何一个确定一个最小成本的时间表是多项式可解的，我们证明，当最小化这些标准的组合，问题变得NP-难。
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.