本文研究单机供应链排序问题,即研究供应链的上游如何安排工件在一台机器上加工,并把加工后的工件分批发送给下游客户,使得生产排序费用和发送费用总和最少,其中,生产排序费用是用工件送到时间的函数来表示;发送费用是由固定费用和与运输路径有关的可变费用组成。本文分别研究以工件带权送达时间与工件延迟为生产排序费用的单机供应链排序问题,对于前者,证明了一般情形的强NP困难性,并对长度和权重有一致性约束的特殊情形给出了动态规划算法;对于后者,分析了问题NP困难性,并设计动态规划算法。
In this paper, an integrated scheduling model of production and distribution operations is studied. In this model, a set of jobs (i.e., customer orders) are first processed on single machine and then delivered in batches to the downstream customers in different regions. 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. Production cost is measured by a function of delivery times, namely, the times when the jobs are delivered to the customers. 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. This paper considers different production costs. For the model with the sum of weighted delivery times as production costs, the strong NP-Hardness has been proven and a dynamic programming algorithm is developed for consistency constraints on jobs' processing time and weight. For the model with production costs related to the due date, the NP-Hardness is analyzed and two dynamic programming algorithms are designed.
[1] Hall N G, Potts C N. Supply chain scheduling: Batching and delivery [J]. Operations Research, 2003, 51(4): 566-584.
[2] Morteza R B, Hejazi S R, Mazdeh M M. A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs [J]. Applied Mathematical Modelling, 2013, 37(7): 4924-4937.
[3] Pei J, Pardalos P M, Liu X B, et al. Coordination of production and transportation in supply chain scheduling [J]. Journal of Industrial & Management Optimization, 2015, 11(2): 399-419.
[4] Cheng B Y, Yang Y Y, Hu X X. Supply chain scheduling with batching, production and distribution [J]. International Journal of Computer Integrated Manufacturing, 2016, 29(3): 251-262.
[5] 张新功，陈娟，两阶段供应链下极小化最大完工时间的单机系列批排序[J].重庆师范大学学报（自然科学版)，2019，36(4):1-6.
[6] Chen Y, Zhang A, Tan Z Y, et al. A (32+ ")-approximation algorithm for scheduling on two parallel machines with job delivery coordination [J]. Journal of the Operational Research Society, 2021, 72(9): 1929-1942.
[7] Ying K C, Pourhejazy P, Cheng C Y, et al. Supply chain-oriented permutation flowshop scheduling considering flexible assembly and setup times [J]. International Journal of Production Research, 2023, 61(1): 258-281.
[8] Chen Z L. Integrated production and outbound distribution scheduling: Review and extensions [J]. Operations Research, 2010, 58(1): 130-148.
