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

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

作　　者：谷金蔚[1] 顾满占[2] 顾幸生[3] 

机构地区：[1]上海电力学院经济与管理学院,上海200090 [2]上海财经大学应用数学系,上海200433 [3]华东理工大学自动化研究所,上海200237

出　　处：《华东理工大学学报（自然科学版）》2014年第2期235-243,共9页Journal of East China University of Science and Technology

基　　金：国家自然科学基金(11201282;61304209;61174040;61104178);上海市教委科研创新一般项目(14YZ127);教育部人文社会科学青年基金(10YJCZH032);上海电力学院引进人才启动基金项目;085重点学科能源经济服务科学研究开放项目

摘　　要：针对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.

关 键 词：流水作业生产 两阶段配送 量子 遗传算法 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]