带运输和外包服务的供应链排序问题算法研究

Scheduling is one of the most active branch in Combinational Optimization filed. With far-reaching development and promotion from both scheduling theory and its application, more and more new models are springing up. One of the most active and important topics in manufacturing research over the last 10 years has been supply chain management. Production and transportation are the two most important issues in the supply chain management, proper coordination of these two stages can achieve optimal overall system performance. Moreover, well-utilized outsourcing, which is a new and modern production system, can reduce total costs, make an organization more flexible and make a company more competitive. In view of this, our proposal will study supply chain scheduling problems with transportation consideration and an outsourcing option. For each model, we mainly analyze the computational complexity, try to design fast approximation algorithm and prove its performance ratio. The research on these two classes of supply chain scheduling problems has just started and is difficult, we will try to conduct a prospective study and work hard for obtaining some innovative results.

排序是组合最优化领域最为活跃的一个分支，随着排序理论的深入发展和来自生产实践的大力推动，排序新模型不断涌现。供应链管理是近十多年来生产制造业最为活跃和重要的研究领域之一，生产（加工）和运输做为供应链两个最重要的环节，两者的集成调度组织能有效地提高整个供应链的运作绩效。此外，新型现代化生产方式的外包生产能够降低企业生产成本和促使企业的管理运作更加灵活，从而提高企业竞争力。本项目主要研究加工与运输协同的排序问题和带外包服务的排序问题，针对每一个模型，项目的核心内容是分析问题的计算复杂性、设计多项式时间快速近似算法并从理论上证明算法的近似性能。上述两类供应链排序问题国际上的研究刚刚起步或起步不久，有一定难度，本项目将尝试对它们进行前瞻性研究，力争获得一系列创新性成果。

基于排序研究复杂作业环境的趋势，本项目重点考虑了两类典型情形（及其相关问题）：工件加工与运输协同的排序和工件带外包选择的排序，项目从问题的计算复杂性、算法设计与分析等方面对这两大类问题进行了深入研究。当具有不同物理尺寸工件需在两台机器上先加工然后经一台车辆运输至客户、目标为极小化总完工时间与运输时间总和，设计了求解该问题的具有几乎最好的最坏情况界的多项式时间算法；当集装箱需经若干台不交叉的起重机运输、目标为极小化总完工时间，基于划分思想，设计了近似比严格小于2的多项式时间算法，并给出了算法最坏情况性能分析；服务器在机器之间来回游走（运输）安装工件、目标为极小化完工时间总和，分析了经典SPT算法的最坏情况界；对工件具有外包选择、目标为极小化总完工时间与外包费用的两台机流水作业问题，分析了文献中贪婪算法的最坏情况界并提出了近似比更好的改进算法；对于工件具有外包选择、目标为极小化完工时间总和与外包费用的两台机自由作业问题，首先利用划分问题进行归约证明了其NP-困难性，接着提出了理论性能较好的求解算法并利用数值实验进行测试。此外，项目还研究了上述两个模型的相关问题包括时间约束的单机排序问题、链与环网络中的频谱分配问题与二部图中的匹配问题等，取得了许多算法和复杂性方面的理论结果。本项目的这些研究都是当前国际上排序研究相关的热点问题，通过本项目研究不仅丰富了排序理论的研究内容，而且发展了近似算法的设计方法和分析技巧，达到了项目的预期目标。