自由作业环境下的供应链排序问题

Supply Chain Scheduling with Open-shop Problem

本文研究自由作业环境下的供应链排序问题,研究供应链的上游如何安排工件在自由作业机器上加工,把加工完毕的工件分批发送给下游,使得生产排序费用和发送费用总和最少.这里,生产排序费用是用工件送到时间的函数来表示;发送费用是由发送的固定费用和与运输路径有关的变化费用所组成.本文研究以工件最大送到时间为生产排序费用的自由作业供应链排序问题,在指出问题的NP困难性后,用动态规划算法构造多项式时间近似算法,并分析算法的性能比.本文最后还对特殊情形进行了讨论.

In this paper, we study an integrated scheduling model of production and distribution operations. In this model, a set of jobs （i.e., customer orders） are first processed in the processing facility of open-shop machine and then delivered to the manufacturers di- rectly without intermediate inventory. The problem is to find a joint schedule of production and distribution such that an objective function that takes into account both production cost and distribution cost is optimized, where production cost is measured by the maximum delivery time and the distribution cost of a delivery shipment consists of a fixed charge and a variable cost proportional to the total distance of the route taken by the shipment. For the problem under this integrated scheduling model, we use dynamic programming to provide a heuristic algorithm with worst-case performance analysis. Finally some special cases are also introduced.