摘要
在工业生产过程中,由于一些特殊的原因,工件可以被拒绝加工但要付出相应的费用,即拒绝惩罚。为了节约处理成本,加工时间长的工件或者加工所需的费用高的工件,可以支付一定的费用来进行外加工或购买。将退化和拒绝结合起来考虑,讨论带有退化工件和拒绝的不同类型机排序问题。在这一模型中,工件的实际加工时间是其开始加工时间的线性递增函数,其中工件的退化率只与机器有关,与工件本身无关。目标函数是极小化接受工件的排序指标与拒绝工件总惩罚之和。排序指标分别为总时间表长和总完工时间。目的是找到拒绝工件集和接受工件集,并安排接受工件的加工顺序,使所求问题的目标函数值最小。通过将2个问题的目标函数转化为指派问题,证明了他们都是多项式可解的。
In the industrial production process, due to some special reasons, the jobs can be rejected but have to pay the appropriate fees that is rejection penalty. In order to save processing costs, the jobs which have a long processing time and high costs can pay fees to process outside or purchase. This paper considers the unrelated parallel machine scheduling with deteriorating jobs and rejection which combine the concepts of deterioration and rejection. In this model, a job＇s actual processing time is an increasing simple linear function of its starting time. The deterioration rate of the job is only related with the machine and regardless of the job itself. The objective is to minimize the sum of the scheduling criterion of the accepted jobs and the total penalty of the rejected jobs. The scheduling criterions are the total load and the total completion time respectively. The purpose is to find the set of rejected jobs, and the non-rejected jobs, and arrange the non-rejected jobs sequence to minimize the objective costs. The objective function of two problems can be transformed into assignment problem, thus proved that the two problems are solvable in polynomial time.
出处
《沈阳师范大学学报（自然科学版）》
CAS
2014年第4期461-465,共5页
Journal of Shenyang Normal University:Natural Science Edition
基金
辽宁省教育厅科学技术研究项目(L2014433)
关键词
排序
不同类型机
退化工件
拒绝
总完工时间
scheduling
unrelated parallel machine
deteriorating jobs
rejection
total completion time
