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

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

针对复杂制造环境下双资源约束作业车间调度问题,提出基于时窗调度策略的继承式遗传算法。该算法基于时窗交集充分利用数控设备加工时工人的时窗空隙;以信息素为载体传承父辈染色体种群的进化经验,并采用基于流量的改进伪随机比例转移规则和自适应云调整参数,生成分支种群;仿照动物的种群组织模式提出多种群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.