金 亭, 赵传立

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)



带有学习效应和退化效应的可拒绝排序问题

金 亭, 赵传立

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)

讨论了具有学习效应和退化效应的多窗口的可拒绝单机排序问题。工件的实际加工时间与开始加工时间和所排位置有关。工件集分为接受工件集和拒绝工件集,对于被拒绝加工的工件而言,它的费用只与工件有关,目标是确定接受工件集的最优加工顺序和拒绝费用,从而极小化2个费用函数。考虑2个问题,第1个问题的目标函数是与提前、延误、窗口的开始时间、窗口的大小以及拒绝费用有关的函数,第2个问题的目标函数是与提前、延误工件数、窗口的开始时间、窗口的大小以及拒绝费用有关的函数,并且针对这2个问题分别给出了多项式时间算法。

单机; 排序; 学习效应; 退化效应; 拒绝

0 引 言

近年来,带有学习效应和退化效应的多窗口的可拒绝单机排序问题备受关注。Wang等[1]提出了同时带有安装时间、学习效应和退化效应的单机排序问题,目标是极小化总完工时间等。Cheng等[2]分析了具有退化效应的工件可拒绝排序问题,其目标是确定接受工件的最大完工时间和拒绝费用以及加权总完工时间和拒绝费用。Zhao等[3]等提出了具有多个工期和多窗口的可拒绝单机排序,目标是极小化提前、延误、周期和拒绝的惩罚,对不同的问题给出不同的多项式算法。Shabtay[4]提出了和拒绝有关的单机排序问题,目标是确定接受工件集的最优加工顺序,从而极小化2个费用函数。……