在不同折扣方案下的工件可外包排序问题

In classical scheduling problems, the manufacturer must process all jobs in-house. However, with the expansion of production scale, processing all jobs in-house might yield many tardy jobs. Thus, the manufacturer sometimes has to outsource some jobs to the third-party outsourcer to process these jobs, which needs to pay the corresponding outsourcing cost. The current research on scheduling with outsourcing mainly focus on how to minimize the in-house production performance and the total outsourcing cost in the manufacturer's point of view. The manufacturer needs to determine which jobs should be processed in-house and a specic schedule for processing those jobs, and which should be outsourced. However, in the subcontractor's point of view, in order to encourage the manufacturer to outsource more jobs, the subcontractor may provide some attractive discount schemes. These discount schemes might be associated with the total outsoucing cost, the number of the outsourced jobs and the time of the outsourced jobs. Our objective is to consider some scheduling problems with oursoucing, different machine settings and different objecitive functions under different discount schemes. We will present some NP-hard proofs and some effecive algorithms for these problems.

在经典排序问题中，生产商必须内部加工所有的工件。然而，随着生产规模扩大，内部加工完所有的工件可能会产生大量的延误工件。因此，生产商有时不得不把一些工件外包给第三方外包商进行加工，这也需要支付相应的外包费用。当前，关于工件可外包排序的研究主要从生产商的角度出发，研究如何最小化内部生产成本和外包费用。生产商必须决定哪些工件内部加工以及如何加工，哪些工件外包给外包商进行加工。然而，从外包商的角度出发，为了获得更多外包费用，外包商可能会提供各种各样的外包折扣。这些外包折扣可能与总外包费用、外包工件个数和工件外包的时间密切相关。我们的目标就是在不同的折扣方案下，考虑一些不同机器环境、不同目标函数的工件可外包问题。我们将对这些问题给出NP困难性证明和各种有效的算法。

当前，关于工件可外包排序的研究主要从生产商的角度出发，研究如何最小化内部生产成本和外包费用。生产商必须决定哪些工件内部加工以及如何加工，哪些工件外包给外包商进行加工。然而，从外包商的角度出发，为了获得更多外包费用，外包商可能会提供各种各样的外包折扣。这些外包折扣可能与总外包费用、外包工件个数和工件外包的时间密切相关。在本项目的资助下，我们已经发表了7 篇学术论文。其中SCI 期刊论文2篇，发表在《Asia-Pacific Journal of Operational Research》上；EI 期刊论文3 篇，发表在《Lecture Notes in Computer Science》上；中文核心期刊论文1 篇，发表在《运筹学学报》上；其它英文期刊论文1篇，发表在英文期刊《Chinese Quarterly Journal of Mathematics》上。这些论文或者解决了多个文献中遗留的未解问题，或者改进了前人文献的一些结果，在技巧性和难度方面有着很多的创新。因此，在排序问题研究方面有重要的理论意义。