加工与运输协同供应链排序的复杂性与算法研究

Supply chain scheduling is a new research field with integrated problems of processing and delivery. It is an important research direction motivated by practical problems in combinatorial optimization. The supply chain scheduling not only considers optimal problems of processing machine resources, but also studies optimal problems about traffic vehicle resources at the same time. Furthermore, we need to research optimal routing about vehicles. This project studies multi-agent supply chain scheduling, supply chain scheduling with due window, supply chain scheduling with machine availability, shop supply chain scheduling and network supply chain scheduling. We aim at studying the model characteristics of these supply chain scheduling problems, analyzing the structure properties about optimal schedule, finding the new ideas of designing algorithms and developing new research methods.We focus on solvability, NP-hard and approximability, designing approximation algorithms and optimal algorithms, analyzing performance ratio for offline algorithms and competitive ratio for online algorithms about supply chain scheduling problems. We hope to establish basic theory and efficient algorithms. It is greatly expected to get a series of creative research results for supply chain scheduling problems.

供应链排序是排序与供应链交叉的新型研究领域，是问题驱动的组合最优化领域的一个重要研究方向。供应链排序不仅要研究加工机器的资源优化，而且要优化运输产品的车辆资源，甚至还需要优化车辆的运输路线。本项目研究代理供应链排序、带有交货时间窗的供应链排序、机器有使用约束的供应链排序、车间作业供应链排序、网络供应链排序问题。目的是研究这些新问题的模型特征，刻画最优解的结构性质，挖掘算法设计思想，发展新的研究方法。研究这些供应链排序问题的可解性、NP困难性与可近似性，设计问题的近似算法或者最优算法，分析算法的性能比或者竞争比，建立有关供应链排序问题的基本理论和有效计算方法，争取取得系列具有创新性的研究成果。

本项目针对加工与运输协同的供应链排序问题进行了研究，分别对多代理加工与运输协同的供应链排序问题、机器有可用时间加工与运输协同的供应链排序问题、带拒绝的多代理排序与供应链排序问题、在线供应链排序问题等进行了较为深入系统研究。对这些问题，研究了其复杂性，设计了较为高效或者最优的算法，分析了算法的近似比或者竞争比。对多代理供应链排序问题、机器有可用时间限制的加工与运输协同供应链排序问题 和在线供应链排序问题的研究，取得了较为丰富的研究成果，提出并解决了一些新型的排序问题，拓广了多代理排序和机器有可用时间限制的排序及在线排序与在线供应链排序问题的研究内容，不仅得到了一些有价值的理论结果，也解决了两个生产实际问题。本项目基本完成了项目的预期目标，取得了一些有突破性的研究成果，在国内外主要学术期刊上发表论文20篇，其中SCI学术期刊论文19篇，项目标注论文19篇。同时在项目的支持下，培养了博士毕业生6名，硕士毕业生6名，出站博士后3名。