在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2017, Vol. 34 ›› Issue (1): 73-86.doi: 10.3969/j.issn.1005-3085.2017.01.008

• • 上一篇    下一篇

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

林   浩,   何   程   

  1. 河南工业大学理学院，郑州  450001
  • 收稿日期:2015-12-01 接受日期:2016-07-06 出版日期:2017-02-15 发布日期:2017-04-15
  • 基金资助:
    国家自然科学基金(11201121; 11571323).

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

LIN Hao,  HE Cheng   

  1. School of Science, Henan University of Technology, Zhengzhou 450001
  • Received:2015-12-01 Accepted:2016-07-06 Online:2017-02-15 Published:2017-04-15
  • Supported by:
    The National Natural Science Foundation of China (11201121; 11571323).

PDF (PC)

185

摘要：

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

关键词: 双指标排序, 工期分配, 加权误工数, NP-困难, 多项式近似方案

Abstract:

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.

Key words: bicriteria scheduling, due date assignment, weighed number of tardy jobs, NP-hardness, polynomial time approximation scheme

中图分类号: