An effective algorithm for the capacitated single item lot size problem
| Autor: | James Flynn, Chia-Shin Chung, Chien-Hua Mike Lin |
|---|---|
| Rok vydání: | 1994 |
| Předmět: |
Mathematical optimization
Information Systems and Management General Computer Science Branch and bound Computer science Production cost Holding cost Management Science and Operations Research Industrial and Manufacturing Engineering Dynamic programming Dynamic lot-size model Modeling and Simulation Production control Production (economics) Algorithm |
| Zdroj: | European Journal of Operational Research. 75:427-440 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/0377-2217(94)90086-8 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|