Scheduling with Rejection to Minimize the Total Weighted Completion Time

摘要：

In this paper, we address the scheduling problem with rejection in which we can choose a subset of jobs to process. Choosing not to process any job incurs a corresponding penalty. We consider the following problem for the first time: scheduling with rejection to minimize the total weighted completion time with the constraint of total penalties on identical parallel machines, where the number of identical parallel machines is constant. We show that it is NPhard and design a pseudo-polynomial time algorithm as well as an FPTAS through dynamic programming.

关键词： Scheduling Rejection Identical parallel machines Approzimation algorithm

作者: Shu-Xia Zhang Zhi-Gang Cao Yu-Zhong Zhang

作者单位: Department of Watercraft Command Zhenjiang Watercraft College, Zhenjiang, Jiangsu 212003, China Key Laboratory of Management Decision & Information Systems AMSS, CAS, Beijing 100190, China College of Operations Research and Management Science Qufu Normal University, Rizhao, Shandong 27682

会议类型: 国际会议

会议名称: The 8th International Symposium on Operations Research and Its Applications(第八届运筹及其应用国际专题讨论会 ISORA09)

会议地点: 张家界

会议语种:英文

页码: 111-114

在线出版日期: 2009-09-20（万方平台首次上网日期，不代表论文的发表时间）