论文部分内容阅读
近年来,有关学习效应的一系列单机排序问题受到人们的广泛关注,并将相关排序模型广泛地应用到各种排序问题之中。另外,商家在生产加工中会拒绝加工一些工件,因为它能够提高生产效率,从而越来越多的国内外研究人员也将拒绝考虑到排序问题之中。本文讨论了两类工件可拒绝的单机排序问题,具体如下: 首先,第一章介绍本文所要研究排序问题的相关知识、研究的现状以及主要的研究内容。其次,第二章针对带有学习效应和退化效应的多窗口的有关可拒绝单机排序问题进行了研究。对两个问题进行讨论,第一个问题的目标函数是极小化提前、延误、窗口的开始时间、窗口的大小以及拒绝费用。第二个问题的目标函数是极小化提前、延误工件数、窗口的开始时间、窗口的大小以及拒绝费用,并且针对这两个问题分别给出了多项式算法。再次,第三章将问题与机器有一固定的不可用区间相结合进行了研究,针对带有DeJong学习效应和不可用区间的单机排序问题进行了研究。在这一问题中,工件的实际加工时间是所排位置的递减函数,并且机器具有固定的不可用区间,工件的加工具有中断-重复性质。目标是极小化最大完工时间。这一问题是NP-难的。并给出了一个全多项式近似策略。另外,将得到的结论推广到了工件可拒绝的情况。