摘要
柔性作业车间调度问题是经典作业车间调度问题的扩展,它允许工序在可选加工机器集中任意一台上加工,加工时间随加工机器不同而不同。针对柔性作业车间调度问题的特点,提出一种基于约束理论的局部搜索方法,对关键路径上的机器的负荷率进行比较,寻找瓶颈机器,以保证各机器之间的负荷平衡。为了克服传统遗传算法早熟和收敛慢的缺点,设计多种变异操作,增加种群多样性。为了更好保留每代中的优良解,设计了基于海明距离的精英解保留策略。运用提出的算法求解基准测试问题,验证了算法的可行性和有效性。
Flexible job shop scheduling problem is an extension of the classical job shop scheduling problem, which allows processes on the machine from alternative machine set, and the processing time will be different with the different processing machine. According to the characteristics of flexible job shop scheduling problem, a local search method based on the Theory Of Constraints （TOC） is presented, comparing the machines load rate on the critical path to find the bottleneck machine, keeping the workload balance among the machines. In order to overcome the disadvantage of traditional genetic algorithm precocious and slow convergence, multiple mutation operators are designed to increase the diversity of the population. For better retaining excellent solution in each generation, it designs Elite solution retention policies based on the Hamming dis- tance. Benchmark problems are solved by the proposed algorithm. Computational results show the feasibility and effective- ness of the proposed algorithm.
出处
《计算机工程与应用》
CSCD
北大核心
2015年第23期266-270,共5页
Computer Engineering and Applications
基金
国家自然科学基金(No.61203179
No.71201048)
河南省高校科技创新人才支持计划资助(No.14HASTIT006)
河南省高等学校青年骨干教师资助计划(No.2014GGJS-105)
航空科学基金(No.2014ZG55016)
关键词
柔性作业车间调度
遗传算法
约束理论
变异操作
瓶颈
flexible job shop scheduling
genetic algorithm
theory of constraints
mutation operator
bottleneck
