On the complexity of bi-criteria scheduling on a single batch processing machine
On the complexity of bi-criteria scheduling on a single batch processing machine
复制标题
DOI：
10.1007/s10951-010-0180-2
复制
发表时间：
2010-12
影响因子：
2
通讯作者：
L. L. Liu-L.;C. T. Ng;T. Cheng
中科院分区：
文献类型：
--
作者：
L. L. Liu-L.;C. T. Ng;T. Cheng
研究了以完工时间为主要指标的单台批处理机上的分层双目标排序问题。我们证明了对于给定的机器能力，次目标为总完工时间的问题可以在多项式时间内求解，而次目标为延迟作业的(加权)数量的问题是(强)NP难的。
This paper considers hierarchical bi-criteria scheduling on a single batch processing machine where the primary criterion is the makespan. We show that the problem where the secondary criterion is the total completion time can be solved in polynomial time for a given machine capacity and the problem where the secondary criterion is the (weighted) number of late jobs is (strongly) NP-hard.