Association Journal of CSIAM
Supervised by Ministry of Education of PRC
Sponsored by Xi'an Jiaotong University
ISSN 1005-3085  CN 61-1269/O1

Chinese Journal of Engineering Mathematics ›› 2017, Vol. 34 ›› Issue (1): 73-86.doi: 10.3969/j.issn.1005-3085.2017.01.008

Previous Articles     Next Articles

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).

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

CLC Number: