一种新的求解Flow Shop问题的启发式算法  

Heuristic Algorithms for Flow Shop Scheduling Problem

作　　者：韦有双[1] 杨湘龙[1] 冯允成[1] 

机构地区：[1]北京航空航天大学管理学院,北京100083

出　　处：《系统工程理论与实践》2000年第9期41-47,共7页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金!( 794 30 0 2 2 ) ;航空基础科研基金资助!( 98J510 94 )

摘　　要：同顺序 Flow Shop问题是一个著名的 NP难题 ,至今尚未找到有效算法 .总体来讲 ,求解该问题的启发式算法主要可分为规则式算法和迭代式算法两种 .对该问题有很多求解目标 ,如最小加工周期 ( min makespan) ,工件的最小平均在系统的停留时间 ( min mean flow tim e)等 .本文以求解最小加工周期为目标 ,基于目前已知的性能最好的算法 NEH算法的基本思想 ,提出了一种新的启发式算法 -组合指标算法 .大量的数据实验表明 ,新的算法具有很好的计算结果 ,而且这种算法可以说是给出了求解 FlowFlow shop scheduling problem is a well\|known NP\|hard problem. In this paper we first summarize the exist heuristic algorithms for flow shop problem which the objective is minimize makespan and then on the basis of NEH algorithm, we propose a new heuristic algorithm for flow shop to minimize the makespan. The numerical experiments show that the proposed algorithm has very good performance.

关 键 词：最优化算法 FlowShop问题 启发式算法 

分 类 号：O224[理学—运筹学与控制论]