具有指数学习效应和恶化效应的可拒绝单机排序问题

摘要

讨论了带有工期窗口的单机排序问题.规定每个被接受的工件都有1个待定的交货期窗口,且所有工件的交货期窗口大小相同.工件的实际加工时间为与其开始时间和位置有关的指数函数.1个工件或者被拒绝,或者被接受.被拒绝就要支付拒绝的费用;被接受就会产生相应的提前、延误惩罚以及最大加工时间的惩罚.研究了2个问题,都需要确定工件的最优排序和窗口的开始时间,第1个问题的目标函数是与窗口的开始时间、窗口的大小、提前时间、延误时间、最大完工时间以及拒绝费用有关的函数.第2个问题的目标函数是与窗口的开始时间、窗口的大小、提前和延误的工件数、最大完工时间以及拒绝费用有关的函数.该问题在多项式时间可解,给出了问题的多项式时间算法.