极小化加权总完工时间的工件可拒绝排序  

Scheduling with Rejection to Minimize the Total Weighted Completion Time

作　　者：张树霞[1] 张峰[2] 

机构地区：[1]镇江船艇学院,船艇指挥系,江苏镇江212003 [2]上海第二工业大学理学院,上海201209

出　　处：《重庆师范大学学报（自然科学版）》2012年第5期10-12,共3页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.70731160015)

摘　　要：经典的排序问题要求工件都必须进行加工,然而在实际中有时候由于一些特殊的原因可以考虑工件不加工。例如,加工时间非常大,或加工所需费用非常高,于是就不加工这一工件,而是通过支付一定的费用后送到外边"外加工"或购买更合算,这类问题称为工件可拒绝排序问题。需要研究的任务是怎样选择工件在机器上进行加工或拒绝,并且如何安排被接受加工工件的加工次序使给定的目标函数值最优。本文研究了工件可拒绝排序中,目标函数是有限的总惩罚费用(总惩罚费用约束下)极小化加权总完工时间,工件到达时间都相同的同型机问题,设计了伪多项式时间的动态规划算法,并给出了相应的FPTAS算法。In the classical scheduling models, it is always assumed that tor any JOb. We have to process It, however, m the real world; we can choose not to process a job. For example, the processing time is too long or the processing penalty is expensive. So it is worthwhile for us to send it outside to be processed or purchased by paying some money, we call the problem schedu- ling with rejection. The task we are about to research is how we choose the job to be processed or rejected, and how we arrange for the processing orders of the jobs so as to optimize the objective function value. In this paper, we consider the scheduling with rejection to minimize the total weighted completion time with the constraint of total rejection penalties on rn identical par- allel machines. We show that it is NP-hard and design a pseudo-polynomial time algorithm as well as an FPTAS through dy- namic programming.

关 键 词：可拒绝排序 动态规划 FPTAS 

分 类 号：O221.7[理学—运筹学与控制论]