复杂系统供应链中在线生产与配送的优化调度

Supply Chain Scheduling is increasingly important in the field of management science. It plays an increasingly large role in production, munufacture, transportation, and so on. The target of the project is to solve some important problems in Supply Chain Mangement using the scheduling theory and other theory and algorithms of combinatorial optimization. Distribution and transportation are the main parts of supply chain, we will study the problems how to dilever the products to the customers by the "best" way. We will study 3 kinds of the problems in supply chain by the theory and algorithms of combinatorial optimization: 1. On-line scheduling in manafacturing. 2. Searching the sequence and the route of the distribation with the minimal cost. 3. Globally optimizing the whole process of manufacturing and distribution. We mainly focus on the on-line versions of the problems, where any information of jobs can not be known in advance until they arrive. We firstly analyze the complexity of the problems, then provide some effective on-line algorithms and analyze the validities of these algorithms,and analyze the competitive ratio.For some representative hard problems we will prove their NP-hardess,and provide some dynamic programming algorithms.

供应链管理在国民经济中的生产、制造、运输等各部门发挥着越来越大的作用。而调度贯穿供应链管理的全过程，本项目旨在利用最优化的一个重要分支－－排序的理论与方法来解决供应链管理中的重要问题。 配送和运输是供应链管理的两大主题，我们首先研究生产管理中的在线调度问题，然后研究利用交通工具把产品"最有效的"送至顾客，使效果最好，费用最小。主要研究三类问题：1、生产管理中的在线调度问题；2、确定最优配送顺序和最佳配送路线；3、生产与配送全过程的整体最优。我们主要集中在在线情形，所谓在线是指在生产与配送中许多信息预先不知道的情形。对其中一些重要的问题提出在线的多项式时间算法；并分析在线算法的目标值值与离线的最优值，比较其精确程度，也就是研究竞争比。对于一些有代表性的离线的难问题证明其NP-难性，并利用动态规划提出伪多项式时间算法加以解决。

本项目主要研究供应链上生产与配送的博弈（Game Schedule）排序问题。每个制造商作为局中人，在问题中看作“工件”，可根据自己的利益选择策略；有若干服务者，叫作“机器”。我们相当于执行者，可在考虑社会的费用的情况下，如何进行排序，让整体费用达到最小。配送商掌握交通资源，要将生产出的产品送到顾客，再考虑社会成本与交通费用（包括交通工具、路费），设计出机制，使整体的费用最小。.本项目所研究的问题，大都是困难的，将这些问题分成一些子问题，有的证明了是NP-难的，提出了近似算法，并分析其近似程度。针对有的现有问题提出来比现有更好的算法。对一些问题，分析了其纳什均衡，强纳什均衡策略，分析了PoA与PoS之上、下界。在供应链调度过程中，客户分布在不同的区域，机器根据订单要求加工各客户的工件。有时制造商可以拒绝加工任一工件，但要支付一定的拒绝费用。对于多个目标函数进行了研究，提出了有效算法；对于工件有不同达到时间，证明了问题是NP-困难的，并给出了好的近似算法。其中“Strong stability of Nash equilibria in load balancing games”、“serial batch scheduling on uniform parallel machines to minimize total completion time”见附页所标。成果发表在《Science China》《Theoretical Computer Science》《Information Processing Letters》等国内外主要刊物上。