A Dynamic Programming Solution to the Dynamic, Multi-Item, Single-Machine Scheduling Problem

André Gascon and Robert C. Leachman
Additional contact information
André Gascon: Université Laval, Québec, Canada
Robert C. Leachman: University of California, Berkeley, California

Operations Research, 1988, vol. 36, issue 1, 50-56

Abstract: This article presents a dynamic programming algorithm for scheduling, on a single machine, production of multiple items with time-varying deterministic demands. We formulate the scheduling problem with the objective of minimizing the sum of changeover and inventory holding costs. The formulation is appealing in that it represents changeover costs directly instead of by the familiar approximate technique of including setup costs in the objective. Our algorithm, which we developed using an approach similar to C. R. Glassey's that minimizes the total number of changeovers, casts the optimal schedule as a shortest path through a network embedded in a state space. It generates optimal schedules under two assumptions. First, we assume that in each time period within the planning horizon, the machine must either be shut down or be producing some one item for the entire time period. Second, we assume that inventory holding costs are representable as a nondecreasing function of aggregate inventory. We provide a number of numerical examples that we solved using the algorithm.

Keywords: 112 lot scheduling by dynamic programming; 333 economic lots for time-varying demands; 581 multi-item production scheduling (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.36.1.50 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:36:y:1988:i:1:p:50-56

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().