中文

Operations Research Transactions >

2026 , Vol. 30 >Issue 1: 171 - 178

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2026.01.011

Dynamic programming algorithms for single machine supply chain scheduling

  • CHEN Rongjun ,
  • LIU Yongcai ,
  • HUANG He ,
  • TANG Guochun
Expand
  • 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 date: 2024-01-04

  Online published: 2026-03-16

Fold

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

Cite this article

CHEN Rongjun , LIU Yongcai , HUANG He , TANG Guochun . Dynamic programming algorithms for single machine supply chain scheduling[J]. Operations Research Transactions, 2026 , 30(1) : 171 -178 . DOI: 10.15960/j.cnki.issn.1007-6093.2026.01.011

References

[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.
Options
Outlines

/

〈 〉