Supply Chain Batching Problem with Identical Orders and Lifespan

Shanlin Li, Maoqin Li, Hong Yan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

In the real world, there are a large number of supply chains that involve the short lifespan products. In this paper, we consider an integrated production and distribution batch scheduling problem on a single machine for the orders with a short lifespan, because it may be cheaper or faster to process and distribute orders in a batch than to process and distribute them individually. Assume that the orders have the identical processing time and come from the same location, and the batch setup time is a constant. The problem is to choose the number of batches and batch sizes to minimize the total delivery time without violating the order lifespan. We first give a backward dynamic programming algorithm, but it is not an actually polynomial-time algorithm. Then we propose a constant time partial dynamic programming algorithm by doing further research into the recursion formula in the algorithm. Further, using the difference characteristics of the optimal value function, a specific calculating formula to solve the problem with the setup time being integer times of the processing time is obtained.
Original languageEnglish
Article number716248
JournalMathematical Problems in Engineering
Volume2015
DOIs
Publication statusPublished - 1 Jan 2015

ASJC Scopus subject areas

  • Mathematics(all)
  • Engineering(all)

Cite this