作业车间调度问题的一种启发式算法  

A Heuristic Algorithm for Job Shop Scheduling

作　　者：黄志[1] 黄文奇[1] 

机构地区：[1]华中科技大学计算机学院,武汉430074

出　　处：《计算机工程与应用》2004年第26期25-27,40,共4页Computer Engineering and Applications

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

摘　　要：论文描述了解决作业车间调度最短完工时间问题的一种快速有效的启发式算法。该算法基于一种优先指派规则,并利用了往前看的思想。从对一组问题标准实例的实验计算结果看,该算法在很短的计算时间内,对多个实例得到最优解或近优解。In this paper,a heuristic al gorithm for solving the minimum makespan problem of job shop scheduling is prese nted.The algorithm is based on priority dispatching rule,and makes use of look-ahead strategy.Computational ex-periments on a standard set of problem insta nces show that,the approach,in reasonable amount of computer time ,yields op timal solutions or near optimal solutions for several ones.

关 键 词：作业车间调度 NP难 启发式 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]