Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness
Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness
复制标题
DOI：
10.1016/j.ejor.2005.06.067
复制
发表时间：
2007-02
期刊：
影响因子：
--
通讯作者：
Yumei Huo;J. Leung;Hairong Zhao
中科院分区：
文献类型：
--
作者：
Yumei Huo;J. Leung;Hairong Zhao
考虑一台机器和一组n个作业，它们在时间0时可供处理。作业j具有处理时间pj、到期日dj和权重wj。考虑了带最大加权拖期和拖期工件个数的双目标排序问题。当两个准则中的一个是主要准则，另一个是次要准则时，我们给出了排序问题的NP-困难证明。这些结果回答了Lee和Vairaktarakis在1993年提出的两个公开问题。我们考虑各种问题之间的复杂性关系，给出多项式时间算法的一些特殊情况下，并提出快速算法的一般情况下。通过实证研究，对该策略的有效性进行了衡量。我们的研究结果表明，一个启发式执行非常好的最佳解决方案相比。
Consider a single machine and a set of n jobs that are available for processing at time 0. Job j has a processing time pj, a due date djand a weight wj. We consider bi-criteria scheduling problems involving the maximum weighted tardiness and the number of tardy jobs. We give NP-hardness proofs for the scheduling problems when either one of the two criteria is the primary criterion and the other one is the secondary criterion. These results answer two open questions posed by Lee and Vairaktarakis in 1993. We consider complexity relationships between the various problems, give polynomial-time algorithms for some special cases, and propose fast heuristics for the general case. The effectiveness of the heuristics is measured by empirical study. Our results show that one heuristic performs extremely well compared to optimal solutions.