摘要
针对集成生产计划、调度中的一类强NP-hard问题,提出了基于状态集分解的分层混合优化算法。通过状态集分解将计划、调度一体化模型转化为一系列的最小网络流模型,上层搜索通过建立可行性必要条件和启发式规则,迅速排除劣解或不可行解,缩小搜索范围。底层搜索主要依靠网络流算法及对偶再优化算法,辅以启发式策略,做小范围的局部精确寻优。数据仿真说明了算法的有效性。
A novel hybrid algorithm based on states decomposition with hierarchical search was proposed to address the simultaneously planning and scheduling problem arising in industry which was proven to be strong NP-hard. The problem was first transformed into a series of network flow models by states decomposition. The top level inferior or infeasible solutions were precluded quickly through feasibility checking and problem-specific strategies which greatly reduced the searching area. The network flow algorithm and the dual re-optimization algorithm incorporated with local search methods were employed to resolve the remaining problem at the lower level. The computational experiments demonstrate the efficiency of the proposed algorithm.
出处
《系统仿真学报》
CAS
CSCD
北大核心
2009年第8期2314-2320,共7页
Journal of System Simulation
基金
国家自然科学基金资助项目(60574063)
关键词
状态集分解
批量计划调度
网络流模型
分层搜索
states decomposition
lot-sizing and scheduling problem
network flow model
hierarchical search