English

运筹学学报（中英文） ›› 2026, Vol. 30 ›› Issue (1): 171-178.doi: 10.15960/j.cnki.issn.1007-6093.2026.01.011

• • 上一篇    

单机供应链排序问题动态规划算法

陈荣军1,†, 刘永财1, 黄河2, 唐国春3   

  1. 1. 常州工学院理学院, 江苏常州 213032;
    2. 上海理工大学管理学院, 上海 200093;
    3. 上海第二工业大学管理工程研究所, 上海 201209
  • 收稿日期:2024-01-04 发布日期:2026-03-16
  • 通讯作者: 陈荣军 E-mail:chenrjecust@163.com
  • 基金资助:
    国家自然科学基金 (No. 71371120), 教育部人文社会科学研究项目 (No. 23YJC790046)

Dynamic programming algorithms for single machine supply chain scheduling

CHEN Rongjun1,†, LIU Yongcai1, HUANG He2, TANG Guochun3   

  1. 1. College of Sciences, Changzhou Institute of Technology, Changzhou 213032, Jiangsu, China;
    2. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China;
    3. Institute of Management Engineering, Shanghai Second Polytechnic University, Shanghai 201209, China
  • Received:2024-01-04 Published:2026-03-16

PDF

2

摘要： 本文研究单机供应链排序问题,即研究供应链的上游如何安排工件在一台机器上加工,并把加工后的工件分批发送给下游客户,使得生产排序费用和发送费用总和最少,其中,生产排序费用是用工件送到时间的函数来表示;发送费用是由固定费用和与运输路径有关的可变费用组成。本文分别研究以工件带权送达时间与工件延迟为生产排序费用的单机供应链排序问题,对于前者,证明了一般情形的强NP困难性,并对长度和权重有一致性约束的特殊情形给出了动态规划算法;对于后者,分析了问题NP困难性,并设计动态规划算法。

关键词: 供应链排序, 供应商问题, 单台机器, 动态规划

Abstract: 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.

Key words: supply chain scheduling, supplier's problem, single machine, dynamic program

中图分类号: