基于多制造商、多客户生产和配送的供应链排序问题研究

供应链管理无疑是一个有重要现实意义的研究领域，尤其是近年来在国民经济的生产、制造、运输等各部门发挥着越来越大的作用。本项目试图用最优化和运筹学中的一个重要分支－－排序的理论与方法来解决供应链管理中的重要问题。.主要研究供应链管理中的生产配送的协和排序问题，也就是考虑生产完成后并将货物用交通工具从若干个供应点按要求送至"顾客"，使总的费用最小，或者总的"效果最好"。主要利用排序的理论与方法研究三个问题：1.制造的生产管理2.最佳配载和配送3.生产和配送的协调(coordination)。对其中一些重要问题或者提出多项式时间算法；或者判定其难度，譬如证明其NP-完备性，对NP-完备问题设计出有效的近似算法, 并分析算法的精确程度和复杂性。我们首先利用最优化方法把以上三个方面的问题转化成排序问题、流水车间排序问题或其它与之相关的问题。然后利用排序的理论与算法加以解决。

对供应链的生产与配送之费用极小化问题和生产与配送之均衡问题进行研究,其中几个重要问题的研究已进入国际先进之列，尤其对于生产制造中的分批调度问题以及调度决策的研究有突破性进展，具体的讲，主要成果如下：.1、对于供应链的生产与配送问题中工件制造后需要运输到客户的供应链排序问题进行了研究。同一客户的工件可以分批进行加工,当相邻的工件属于不同客户时则需要相应的准备时间。以生产和运输总费用最小为目标函数,建立了集成排序模型,采用动态规划的技巧给出了最优算法,并分析算法复杂性。对于多供应商、单制造商的装配制造系统问题进行研究。目标函数为工件加权延误，首次证明了该问题的强 NP-困难性，这是国际著名优化专家 Zhi-long Chen 教授提出的一复杂性方面的 公开问题；同时建立了目标函数为元件加权延迟和的供应链排序模型，并提出了近似有效算法。.2、在生产制造中，有这样一种调度问题，随着工序的进程，机器的生产速度是变化的，这是供应链排序中的新模型。我们证明就是在有2个到达时间，许多问题是 NP-困难的，证明EDD（earliest due date）在一定情况下是最优排序。对于极小化最大完工时间和极小化总完工时间问题，在加工时间依赖开工位置的情形,给出极小化最大完工时间和极小化总完工时间的最优序。.3、供应链中有易变质产品的二级供应链库存问题。由于产品运输给分销商时需要花费时间与成本,在开始一段时间内分销商的订单得不到及时补充,只有当制造商的库存量达到最大时,才将产品运输给分销商。目标就是确定最优订购策略使得整个系统的总成本最小。我们证明了二种特殊情形下最优解的存在及唯一性。最后通过算例验证了最优策略的有效性。.4、在供应链管理的多准则决策问题中，准则间存在优先级别关系。Yager对这一问题进行了研究，提出了优先平均算子和优先OWA算子。我们课题组对同一优先级别下有多个准则的情形，建立了一个平均算子，并研究了其性质，当同一优先级别下只有一个属性时，该算子退化为Yager的PA算子和POWA算子。该算子在集结过程中具有更广泛的实用性，还提出了基于二元语义的优先集结算子，拓广了Yager等人的成果。对于可拒绝的分批调度问题，就是允许工件可以不加工的情形（当然有损失）， 目标是极小化有权重的完工时间和与不加工工件的损失之和，先证明其为NP-完全的。最后提出伪多项式时间精确算法。