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

摘要

讨论了具有学习效应和退化效应的多窗口的可拒绝单机排序问题。工件的实际加工时间与开始加工时间和所排位置有关。工件集分为接受工件集和拒绝工件集，对于被拒绝加工的工件而言，它的费用只与工件有关，目标是确定接受工件集的最优加工顺序和拒绝费用，从而极小化2个费用函数。考虑2个问题，第1个问题的目标函数是与提前、延误、窗口的开始时间、窗口的大小以及拒绝费用有关的函数，第2个问题的目标函数是与提前、延误工件数、窗口的开始时间、窗口的大小以及拒绝费用有关的函数，并且针对这2个问题分别给出了多项式时间算法。%We discuss single machine scheduling with both learning and deterioration effects and rej ection,in which the jobs have multiple due windows.The actual processing time of accepted jobs is a function of its starting time and position in a sequence.We solve the problem by partitioning the jobs into a set of accepted and a set of rejected jobs.The objective is to determine the optimal sequence of accepted jobs and the cost of the rejected jobs,so as to minimize the total costs. We consider two versions of the problem.For the first version,the total cost includes earliness,tardiness,the starting time of due windows,the size of due windows and rej ection cost.For the second version,it includes earliness,the number of tardy jobs,the starting time of due windows,the size of due windows and rejection cost.We present polynomial algorithms for two versions,respectively.