带有恶化率的可拒绝单机排序及批配送  

Scheduling Linear Deteriorating Jobs with Rejection on a Single Machine and Batch Delivery

作　　者：李文洁[1] 

机构地区：[1]曲阜师范大学管理学院,山东省日照市276826

出　　处：《曲阜师范大学学报（自然科学版）》2014年第1期15-20,共6页Journal of Qufu Normal University(Natural Science)

基　　金：教育部高等学校博士学科点专项基金(20123705110003);国家自然科学基金(11071142);山东省自然科学基金(ZR2010AM034)

摘　　要：首次考虑了加工时间带有线性恶化率的可拒绝单机排序及其批配送的问题.如果工件被拒绝,则要付出一定的拒绝费用;如果工件被接受,则要安排加工并配送.目标函数是极小化接受工件的加权总完工时间或最大延误时间,配送费用与拒绝工件的拒绝费用这三部分的和,我们不仅证明了这些问题都是NP-hard的,而且还提出了基于动态规划的伪多项式时间算法.In this paper,the problem of scheduling linear deteriorating jobs with rejection on a single machine and batch delivery is considered.A job is either rejected,in which case a rejection penalty has to be paid,or accepted and processed on the machine.The objective is to minimize the sum of the total weighted completion time（or the maximum lateness） of the accepted jobs,the transportation costs,and the total re-jection penalty of the rejected jobs. These problems are proved to be NP-hard in the ordinary sense, and pseudo-polynomial-time dynamic programming algorithms is proposed.

关 键 词：排序 恶化率 可拒绝 批配送 动态规划 

分 类 号：O226[理学—运筹学与控制论]