Simulated Annealing Heuristic for Lot-Sizing Problem
-
摘要: 多品种、有能力约束的批量问题是多品种批量生产中生产计划的关键性问题.这一问题就是要确定:在每一期生产多少产品以使得所用费用最少且满足已知的每一期的需求量.本文设计了一种模拟退火算法的实现形式,通过大量的算例分析表明,该算法具有良好的寻优特性与运算效率.Abstract: The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. An approximation algorithm is described, which is based on simulated annealing algorithm. The method incorporates a primal partitioning scheme— with a network flow subproblem—to obtain good feasible solutions.
-
Key words:
- lot size /
- heuristic approach /
- network flows /
- multi-item /
- simulated annealing /
- production planning
-
1 Eppen G D,Martin R K. Solving multi-item capacitated lot-sizing problems using variable redefinition. Operations Research,1987,35(6):832~848 2. Hindi K S. Solving the CLSP by a tabu search heuristic. J Opl Res Soc, 1996, 47(1):151~161 3. Eisenhut P S. A dynamic lot sizing algorithm with capacity constraints. AIIE Transactions,1975, 7(2):170~176 4. Bertsekas D P, Tseng P. Relaxation methods for minimum cost ordinary and generalized network flow problems. Operations Research, 1988, 36(1):93~114 5. Glove F,Laguna M. Modern heuristic techniques for combinatorial problems.Oxford:Blackwell Scientific Publishing, 1993 6. 刘 勇,康立山,陈毓屏.非数值并行算法——模拟退火算法.北京:科学出版社,1995 7. Lambrecht M R, Vanderveken H. Heuristic procedures for the single operation, multi-item loading problem. AIIE Transactions, 1979, 11(4):319~326 -
点击查看大图
计量
- 文章访问数: 2477
- HTML全文浏览量: 165
- PDF下载量: 455
- 被引次数: 0
下载:
