工件可拒绝排序问题综述

作者：张玉忠^*

来源：运筹学学报, 2020, 24(02): 111-130.

DOI：10.15960/j.cnki.issn.1007-6093.2020.02.009

• 可拒绝排序
• 在线排序
• 离线排序
• 近似算法
• 复杂性
• 竞争比
• NP-难
• PTAS
• FPTAS

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

• 单位
  曲阜师范大学