多阶段可替换分组并行机调度问题的求解  

Method for multi-stage alternative grouping parallel machines scheduling problem

作　　者：苗峰[1] 谢安桓[1] 王富安 喻峰 周华[1] 

机构地区：[1]浙江大学流体动力与机电系统国家重点实验室,浙江杭州310027 [2]中国船舶重工集团第七〇七研究所九江分部,江西九江332007

出　　处：《浙江大学学报（工学版）》2015年第5期866-872,共7页Journal of Zhejiang University：Engineering Science

基　　金：国家自然科学基金创新研究群体科学基金资助项目(51221004)

摘　　要：针对一类多阶段可替换分组并行机混流生产调度问题,以最小化最大完工时间为目标建立问题的数学模型,提出一种嵌入混合启发规则的遗传算法,采用分段独立编码的染色体和改进的遗传算子.依靠遗传算法的全局搜索能力确定启发规则的最优决策变量,根据决策变量采用包含多种规则的混合规则确定各阶段调度方案;同时解决了调度问题的路径选择子问题和加工排序子问题,调度方案自动满足模型约束.算法求解速度快,求解结果具有较高的负荷平衡率.针对不同规模的算例,仿真验证了算法的有效性,仿真结果表明该算法的综合性能指标优于嵌入单一启发规则的遗传算法.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.

关 键 词：并行多机调度 启发式算法 遗传算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301.6[自动化与计算机技术—控制科学与工程]