基于DE和EDA的智能算法求解复杂车间调度问题

发布时间：2018-03-17 06:04

本文选题：差分进化算法　切入点：分布估计算法　出处：《昆明理工大学》2014年硕士论文　论文类型：学位论文

【摘要】：车间调度问题通常存在非线性、强约束、多目标、不确定等复杂性,而且规模庞大、建模困难。开发适合于复杂生产车间调度问题的智能优化算法,已经成为生产调度领域的研究热点。差分进化算法(DE)是一种新兴的群智能进化算法,可用于求解复杂的优化问题。分布估计算法(EDA)是一种基于优势个体概率模型的进化算法,可从较为宏观的角度实现对问题解空间的搜索。本文将DE和EDA应用于复杂车间调度问题上。主要工作如下： (1)针对实际生产环境中广泛存在的带有序相关设置时间(SDSTs)和工件释放时间(RDs)的零等待流水线调度问题(NFSSP),设计了一种用于最小化总延迟时间的混合差分进化算法(HDE)。 (2)为了有效求解最大完工时间(makespan)指标下的m台机器可重入置换流水线调度问题(MRPFSSP),提出了三种基于EDA的算法。首先,提出了一种基于Insert的变异方法和Interchange的局部搜索策略的混合EDA算法(HEDA);其次,提出了一种能够自适应调整学习速率的混合EDA算法(SHEDA), SHEDA有效融合了基于关键路径和块结构的局部搜索策略；最后,在对MRPFSSP的问题结构性质进行深入研究的基础上,提出了一种基于Copula理论和关键路径局部搜索策略的混合分布估计算法(CHEDA)。 (3)针对单目标和多目标下的三类复杂并行机调度问题(PMSP),设计了相应的基于EDA的算法进行求解。首先,提出了一种求解并行多机间歇调度问题的自适应EDA算法(AEDA),优化目标为makespan;其次,提出了一种改进EDA算法(NED A),用于求解makespan指标下的带工件加工约束和序相关设置时间的异构并行机调度问题(HPMSP_JPCSST);第三,提出了一种遗传-分布估计算法(GA-EDA),用于求解部分产品需多工序加工,同时不同产品间带序相关设置时间的异构并行机调度问题(HPMSP_MOSST),优化目标为makespan;最后,提出了一种基于Copula理论的多目标分布估计算法(CMEDA),由于求解nakespan和总转换费用下的多目标HPMSP MOSST。仿真实验和算法比较对所提算法的有效性和鲁棒性进行了验证。
[Abstract]:Shop scheduling problem is usually nonlinear, strong constraint, multi-objective, uncertainty and complexity, large scale, difficult to model. Intelligent optimization algorithm is developed for complex production scheduling, production scheduling has become a hot research field. The differential evolution algorithm (DE) is a new kind of swarm intelligent algorithm that can be used to solve complex optimization problems. The estimation of distribution algorithm (EDA) is an evolutionary algorithm based on probabilistic model of individual advantage, can realize to search the solution space from a macro perspective.
In this paper, DE and EDA are applied to the problem of complex shop scheduling. The main work is as follows:
(1) aiming at the widely occurring zero wait pipeline scheduling problem (NFSSP) with real time set time (SDSTs) and job release time (RDs) in real production environment, a hybrid differential evolution algorithm (HDE) for minimizing total delay time is designed.
(2) in order to solve the problem of the maximum completion time (makespan) re entrant permutation flow shop scheduling index under m machine (MRPFSSP), put forward three kinds of algorithm based on EDA. Firstly, we propose a hybrid EDA algorithm with local search strategy variation method and Interchange based on Insert (HEDA); second and put forward a hybrid EDA algorithm with adaptive learning rate (SHEDA), SHEDA effective integration of the local search strategy based on the critical path and block structure; finally, based on an in-depth study of the problems on the structural properties of MRPFSSP, proposed a theory based on critical path and Copula hybrid local search strategy estimation of distribution algorithm (CHEDA).
(3) for the three types of single and multi objectives under the complicated parallel machine scheduling problem (PMSP), designed the EDA based algorithm is used to solve the problem. Firstly, we propose the adaptive EDA algorithm for multi machine batch scheduling for solving the problem of parallel (AEDA), the optimization goal is makespan; secondly, put forward a an improved EDA algorithm (NED A), is used for machine scheduling for makespan index with workpiece processing constraints and sequence dependent setup time of heterogeneous parallel problem (HPMSP_JPCSST); third, proposed a genetic - Estimation of distribution algorithm (GA-EDA), for solving some products need processing, machine scheduling and different products with sequence dependent setup time of heterogeneous parallel problem (HPMSP_MOSST), the optimization goal is makespan; finally, this paper puts forward an algorithm of multi-objective estimation of distribution based on the theory of Copula (CMEDA), the multi objective HPMS to solve nakespan and total conversion cost down P MOSST.
The effectiveness and robustness of the proposed algorithm are verified by simulation experiment and algorithm comparison.

【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TB497;TP18

【参考文献】