关于工期分配与加权误工数的双指标排序问题（英文）

On Bicriteria Scheduling of Due Date Assignment and Weighted Number of Tardy Jobs

排序问题中工期分配的目的是处理分配费用与性能指标的利益平衡,由此提出工期分配的双目标排序问题.关于工期分配与加权误工数的单机双指标排序问题,文献中只研究了其线性组合形式.针对该问题,本文针对约束形式及Pareto优化形式进一步研究了更多的模型.主要结果包括NP-困难性、多项式可解情形以及多项式时间近似方案等结果.通过这些结果,一个多目标优化问题的特征得以完整地刻画.

The due date assignment in the scheduling problems is concerned with the benefit balance between the assignment cost and the performance criterion. This arises the bicriteria scheduling problems of due date assignment. In single machine bicriteria scheduling of due date assignment with weighted number of tardy jobs,only the linear combination version has been studied in the literature. This paper further studies more models, namely, the constraint version and the Pareto optimization version. The main contribution of this study is the related results on the NP-hardness, polynomially solvable cases, and the polynomial time approximation scheme. By using the proposed manner, the features of a multicriteria optimization problem can be effectively characterized.