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

摘要

为了研究多目标柔性作业车间调度问题,基于甘特图和搭积木经验进行了分析,提出了一种组合优先规则和基于此优先规则的启发式算法.组合优先规则面向完工时间、关键机床负荷和总负荷三个指标,改变规则中各数据项的比例可调整三个指标所占的比例;算法采用随机方式调整三个指标的比例,并微调最优解对应的比例.能随机产生多个高质量调度解.算法对比测试表明,该算法求解质量高、运行速度快且稳定,可直接用于在其他调度算法中产生初始解或者用于动态调度.%To study multi-objective flexible Job-Shop scheduling problem, this paper analyzed it based on Gantt graph and experience from building block, presented a composite priority rule and heuristic algorithm based on this priority rule.This composite priority rule was for three scheduling targets including makespan, critical machine workload and total workload, changing the ratio of data items in the rule could adjust the ratio of the three scheduling targets.The algorithm randomly adjusted the ratio of this three scheduling targets, and slightly adjusted the ratio corresponding to the best solution, could randomly generate many excellent scheduling solutions.The algorithm' s comparison and test show that the result of this algorithm is more excellent, the algorithm runs rapidly and steadily, and can directly be used in generating initial solution in other scheduling algorithms or dynamic scheduling.