量子寄生遗传算法求解Flow Shop及两阶段配送的集成调度问题

A Quantum Bio-parasitic Genetic Algorithm for Solving a Hybrid Scheduling Problem of Flow Shop and Two-Stage Transportation

针对Flow Shop及两阶段配送的集成调度问题,考虑各种约束条件,以交货时间最短为目标构建混合整数规划模型。该模型中,第1阶段配送是工件原材料从仓库由吊车搬运到生产车间的加工机器上,第2阶段配送是工件完工后由一辆卡车运送至顾客。根据该集成调度问题特点,提出了基于量子理论和寄生理论的量子寄生遗传算法(Quantum Bio-parasitic Genetic Algorithm,QBGA)。该算法设计了能够同时带有工件的运输批次和生产排序信息的编码,该编码保证了每个个体都是充分协调生产能力和运输能力的可行解,同时构建了两个种群——宿主群和寄生群,执行寄生机制与反寄生机制从而增加基因多样性和加快算法收敛速度,最后通过仿真实验验证了QBGA算法的有效性。

In order to solve an integration scheduling problem of flow shop and two-stage transportation,we consider various constraints involving production and distribution,and build a mixed integer programming model.In this model,the production operation is flow shop scheduling,while the distribution operation consists two stages.In the first stage,the jobs are conveyed from the warehouse to the workshop by a crane,and in the second stage,the finished goods are transported to the customers by the carriers.According to the features of the above integrated scheduling problem,we propose a quantum bio-parasitic genetic algorithm（QBGA）based on quantum theory and parasitic theory.Firstly,a coding method with transport batches and production order is designed to ensure that each individual is the feasible solution of fully coordinating both production capacity and transportation capacity.At the same time,two populations,the host and the parasitic,are built to perform the mechanisms of both parasitic and the anti-parasitic so as to increase the genetic diversity and accelerate the algorithm convergence speed. Finally,simulation experiments illustrate the efficiency of QBGA in this work.