摘要
针对一类多阶段可替换分组并行机混流生产调度问题,以最小化最大完工时间为目标建立问题的数学模型,提出一种嵌入混合启发规则的遗传算法,采用分段独立编码的染色体和改进的遗传算子.依靠遗传算法的全局搜索能力确定启发规则的最优决策变量,根据决策变量采用包含多种规则的混合规则确定各阶段调度方案;同时解决了调度问题的路径选择子问题和加工排序子问题,调度方案自动满足模型约束.算法求解速度快,求解结果具有较高的负荷平衡率.针对不同规模的算例,仿真验证了算法的有效性,仿真结果表明该算法的综合性能指标优于嵌入单一启发规则的遗传算法.
To solve the mixed flow scheduling problem with multi-stage alternative grouping parallel ma- chines, the mathematical model to minimize the maximum completion time was constructed and a hybrid heuristic-genetic algorithm was developed, the algorithm bases on piecewise independent coding method and modified genetic operators. The optimal decision variables of scheduling rules is determined by the global search ability of genetic algorithm. Scheduling scheme of each stage is determined by using the deci- sion variables and the hybrid heuristic rules which contains a variety of scheduling rules. The algorithm can solve path selection sub-problems and processing sorting sub-problems at the same time, and the re- sults automatically satisfy model constraints. This algorithm has following advantages： high arithmetic speed, optimum results taking into higher rates of load-balancing and etc. Simulation examples of different scales verify the effectiveness of the algorithm. The comparison indicates that the composite indicator of this algorithm is superior to that of single heuristic-genetic algorithms.
出处
《浙江大学学报（工学版）》
EI
CAS
CSCD
北大核心
2015年第5期866-872,共7页
Journal of Zhejiang University：Engineering Science
基金
国家自然科学基金创新研究群体科学基金资助项目(51221004)
关键词
并行多机调度
启发式算法
遗传算法
parallel machines scheduling
heuristic algorithm
genetic algorithm
