并行加工经济批量问题的最优算法  

An optimal algorithm to solve economic lot sizing problem in the multi-processor case

作　　者：张岩[1] 顾培亮[1] 

机构地区：[1]天津大学系统工程研究所,天津300072

出　　处：《系统工程学报》2000年第2期173-178,共6页Journal of Systems Engineering

摘　　要：考察了 n - period经济加工批量问题并给出一种复杂度 O(mnlogn )的优化算法 .对于无能力约束的动态经济加工批量问题 (Wagner- Whitin问题 ) ,最早由 Wagner和 Whitin(195 8)提出 ,并给出一个基于动态规划 ,复杂度为 O(n2 )的算法 .最近 ,有许多人重新对该问题进行了研究 ,并以多种方式给出了复杂度为 O(nlogn )的算法 .本文在以上研究的基础上 ,针对柔性加工多机并行加工情况 ,给出了一种复杂度为 O(mnlogn )的 Wagner- Whitin问题的解法 .This paper considers in the n period economic lot sizing problem with multi processor and gives an optimal algorithm in O(mn logn) time. The general Wagner Whitin problem was solved in 1958 by themselves in O(n 2) time. Recently, a lot of algorithms was given to solve the problem in O(n logn) time, especially by Wagelmans and Hoesel(1992). Based on their works, an optimal algorithm in O(mn logn) time for Wagner Whitin problem with multi processor is proposed in the paper.

关 键 词：柔性生产系统 经济加工批量问题 最优算法 

分 类 号：TH165[机械工程—机械制造及自动化]