求解置换Flow shop调度问题的一种启发式算法  

A Heuristic Algorithm for Flow Shop Scheduling Problem

作　　者：王磊[1] 黄文奇[1] 

机构地区：[1]华中科技大学计算机科学与技术学院计算机科学理论研究所,武汉430074

出　　处：《计算机工程与应用》2004年第19期31-32,共2页Computer Engineering and Applications

基　　金：国家973重点基础研究发展规划项目(编号:G1998030600)

摘　　要：提出了一种新的求解置换flowshop调度问题的启发式算法。问题的目标是:在满足约束条件的前提下使得调度的makespan尽可能地小。定义了一种新的邻域结构。给出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向。计算了一组著名的问题实例。计算结果表明,算法的优度高于一种改进的遗传算法。A new heuristic algorithm,which is based on local se arch framework,for solving permutation flow shop schedul-ing is presented.A n ew concept of neighborhood structure is proposed.A jumping strategy is propose d to jump from local optimal solution and guide the search in promising directi ons.This approach,in a reasonable amount of computer time ,finds the optimum solutions to a set of standard problem instances.This algorithm yields better solutions than an efficient genetic algorithm discussed in the literature.

关 键 词：组合优化 NP难度问题 流水作业调度 邻域搜索 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]