机器带有不可用区间的可拒绝平行机排序问题（英文）  

Parallel Machines Scheduling with Rejection and Availability Constraints

作　　者：池晶晶[1] 

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

出　　处：《曲阜师范大学学报（自然科学版）》2016年第3期42-48,共7页Journal of Qufu Normal University(Natural Science)

基　　金：supported by the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant(20123705110003);the Key Project of Natural Science Foundation of Shandong Province under Grant(ZR2015GZ009)

摘　　要：主要研究了机器带有拒绝和不可用区间的可拒绝排序问题.针对这一问题的两种情形进行研究.一方面,考虑了每台机器有一个不可用区间,且目标函数是极小化总完工时间与拒绝费用之和的平行机排序问题.另一方面,考虑了工件的实际加工时间是开始时间的按比例函数的平行机排序问题,并且每台机器在一段特定的区间内不可用.当然,可以通过支付拒绝惩罚费用而拒绝加工工件,这一问题的目标是极小化总加权完工时间与拒绝费用之和.对于以上两个问题,分别给出了时间复杂性为O（nm（∏i=1^mSi）（P_n）^m）和O（n∏i=1^m（S_i-t_0）∏i=1^mT_i（A_n）^m）的伪多项式时间动态规划算法.The identical parallel machine scheduling problem that considers both rejection and availability constraints is sludied.Two scenarios of the problem are studied.On the one hand, we consider the above prob- lem with rejection and a planned maintenance period on each machine to minimize the total completion time plus the penalties of the rejected jobs.On the other band, we address the above problem in which the actual pro- cessing time of the job is a proportional function of its starting time,and each machine is not available in a specified time period. Of course,the jobs can be rejected by paying penalties. The objective of the second prob- lem is to minimize the total weighted completion time plus the penalties of the rejected jobs. For the above two problems,we present a pseudo-polynomial dynamic programming algorithm for each one to solve the problem optimally,which runs in time O（nm（∏i=1^mSi）（P_n）^m）and O（n∏i=1^m（S_i-t_0）∏i=1^mT_i（A_n）^m）, respectively.

关 键 词：排序 拒绝 不可用区间 退化效应 

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