A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assignable due dates
A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assignable due dates
复制标题
DOI：
10.1007/s10951-010-0208-7
复制
发表时间：
2011-10
影响因子：
2
通讯作者：
D. Shabtay;G. Steiner
中科院分区：
文献类型：
--
作者：
D. Shabtay;G. Steiner
我们研究了一个灵活的框架中的单机调度问题，其中作业处理时间和交货期都是由调度器决定的决策变量。该模型也可以应用于报价交货时间时，某些部分的工作可能会外包。我们分析了两种交货期分配方法和凸资源消耗函数的问题。对于每一种交货期分配方法，我们提供了一个双准则分析，其中第一个标准是最小化总加权数的误工作业加上交货期分配成本，第二个标准是最小化总加权资源消耗。我们考虑四种不同的模型来处理这两个标准。虽然最小化一个单一的综合目标函数的问题可以在多项式时间内解决，我们证明了这三个双准则模型是困难的两种交货期分配方法。我们还提出了特殊的情况下，这在实践中经常发生，并在所有四个模型多项式可解。
We study a single-machine scheduling problem in a flexible framework where both job processing times and due dates are decision variables to be determined by the scheduler. The model can also be applied for quoting delivery times when some parts of the jobs may be outsourced. We analyze the problem for two due date assignment methods and a convex resource consumption function. For each due date assignment method, we provide a bicriteria analysis where the first criterion is to minimize the total weighted number of tardy jobs plus due date assignment cost, and the second criterion is to minimize total weighted resource consumption. We consider four different models for treating the two criteria. Although the problem of minimizing a single integrated objective function can be solved in polynomial time, we prove that the three bicriteria models are-hard for both due date assignment methods. We also present special cases, which frequently occur in practice, and in which all four models are polynomially solvable.