An effective algorithm for the capacitated single item lot size problem

An effective algorithm for the capacitated single item lot size problem

0.00 Avg rating0 Votes
Article ID: iaor1998141
Country: Netherlands
Volume: 75
Issue: 2
Start Page Number: 427
End Page Number: 440
Publication Date: Jun 1994
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: dynamic
Abstract:

This paper studies a deterministic, single product capacitated dynamic lot size model with linear production and holding costs where the setup costs, unit production costs, and capacities are arbitrary functions of the period, and the unit production costs satisfy the growth constraint: the unit production cost in any period can never exceed the sum of the unit production cost and the unit holding cost in the previous period. Our main result is an algorithm which combines dynamic programming with branch and bound. Although the problem considered here is known to be NP-hard, this algorithm handles many reasonable sized problems. A number of tests covering a fairly wide range of parameter values are run to evaluate its effectiveness. The average CPU time required to find an optimal solution to our 96 period test problems on a VAX 11/750 minicomputer is 13.3 seconds.

Reviews

Required fields are marked *. Your email address will not be published.