基于时窗的双资源约束车间调度研究  

Research on Dual Resource Constrained Job Shop Scheduling Based on Time Window

作　　者：李兢尧[1] 孙树栋[1] 黄媛[2] 牛刚刚[1] 

机构地区：[1]西北工业大学现代设计与集成制造教育部重点实验室,西安710072 [2]西北工业大学机电学院,西安710072

出　　处：《机械工程学报》2011年第16期150-159,共10页Journal of Mechanical Engineering

基　　金：国家高技术研究发展计划(863计划;2007AA04Z187);国家自然科学基金(50705076;50705077)资助项目

摘　　要：针对复杂制造环境下双资源约束作业车间调度问题,提出基于时窗调度策略的继承式遗传算法。该算法基于时窗交集充分利用数控设备加工时工人的时窗空隙;以信息素为载体传承父辈染色体种群的进化经验,并采用基于流量的改进伪随机比例转移规则和自适应云调整参数,生成分支种群;仿照动物的种群组织模式提出多种群King交叉进化模式,并针对双资源约束特点引入资源进化算子;基于被支配域的概念提出扇形分割的轮盘赌选择算子,以较小的计算复杂度选择非劣解集和较优个体。在采用马尔科夫链知识对整个算法的全局收敛性进行理论分析后,通过对随机算例仿真运算结果的统计分析,表明该算法虽然解分布均匀程度不甚理想,但算法搜索性能和收敛性较优。An inherited genetic algorithm based on time window scheduling is proposed to solve the dual resource constrained job shop scheduling problem with complex manufacturing environment.This algorithm makes full use of the time window of workers during the process of numerical control machines based on the intersection of time windows to actualize positive scheduling.Then the evolutionary experience of parent chromosomes is inherited with pheromone as carrier and the branch population is generated with improved pseudo-random probability transfer rule and adaptive adjusting parameters based on cloud theory.The King crossover operator is proposed on the basis of imitating animal population organization mode and some resource evolutionary operators are introduced in response to the features of dual resource constrained.At last,an efficient roulette selection operator with sector partition is used to select Pareto-optimal solutions and better chromosomes.After the theoretical analysis of the global convergence via Markov chain,the statistical analysis on the simulation results of random benchmarks shows that this algorithm has strong search ability and good convergence performance.

关 键 词：时窗调度 继承式遗传算法 扇形分割 马尔科夫链 

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