工件可拒绝或可外包的折衷排序、在线排序和博弈排序研究

Due to the limited resources, the manufacture and service provider have to reject some orders or subcontract these orders to the third-party machines for processing. Rejection and outsourcing have been the common practices for many companies. We mainly focus on the studies on scheduling problems with rejection or outsourcing, specially on the relevant trade-off scheduling problems, online scheduling problems and game scheduling problems. These problems have many profound practical backgrounds and broad prospects. However, due to the difficulty of these problems, the studies on these problems are till on a preliminary phase. To solve these problems, we must provide some new methods and skills to design some optimal algorithms, approximation algorithms and on-line algorithms.

由于资源的有限性，生产商和服务商有时候不得不拒绝一些订单或者把这些订单外包给第三方进行加工。拒绝和外包已经成为众多企业的一种普遍行为。本项目主要集中研究工件可拒绝或者可外包的排序问题，以及与之相关的折衷排序、在线排序和博弈排序问题。这类问题在实际中有着深刻的应用背景和广泛的应用前景。然而，由于这些问题研究起来非常困难，还有大量的问题模型有待提出和研究。为了解决这一类问题，我们必须提出一些新的方法和技巧，并设计一些创新性的最优算法、近似算法和在线算法。

工件可拒绝（或者可外包）排序是近10多年来排序理论研究的热点问题之一。为了降低生产费用，增加利润和顾客满意度，生产商经常不得不拒绝一部分工件或者把一部分工件外包给第三方生产商进行加工。本项目对工件可拒绝（或者可外包）排序进行了深入的研究。受本项目资助共发表SCI期刊学术论文8篇，EI期刊论文2篇。代表性成果如下：（1）对目标函数为最大完工时间、多台平行机上的工件可拒绝排序问题，我们分别给出了拟多项式时间最优算法，2-近似算法和全多项式时间近似方案，该论文发表在SCI期刊《4OR-A Quarterly Journal of Operations Research》上。（2）对目标函数为最大提前量的单机工件可拒绝排序问题，我们证明了该问题在一般意义下是NP-困难的，并给出了有效的最优算法或者近似算法。该论文发表在SCI期刊《Journal of Combinatorial Optimization》上。（3）对具有不同折扣方案的工件可外包排序问题，我们系统分析了问题的复杂性并给出了有效的近似算法或者近似方案。该论文已经被SCI期刊《Annals of Operations Research》接收。