工件可拒绝排序问题综述

A survey on job scheduling with rejection

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.

Scheduling with rejection is a representative and applied scheduling that emerged around 2000.It is one of the generalizations of the classical scheduling problems.In classical scheduling problems,it is assumed that all jobs have to be processed.However,in practice,for some special reasons,policy makers will reject the processing of some jobs.That is what we called job scheduling with rejection.It is noteworthy that the problem has a certain application background and great application value,and also has important significance in theory.The problem is gaining more and more attention recently and new results are welling up.In this paper,we give a comprehensive introduction to online and offline scheduling with job rejection.We also give abundant references,including many existing research results and new research directions.It's designed to help the interested readers rapidly to the research frontier.