基于元启发式算法的带生产约束作业车间调度问题若干研究

发布时间：2018-06-01 14:40

本文选题：生产调度 + 作业车间　；参考：《华东理工大学》2014年博士论文

【摘要】：随着科学技术和经济的发展,市场竞争日趋激烈,企业的现代化发展是大势所趋。作为国民经济支柱的制造业,不仅需要提高生产加工技术,还需要采用先进的管理技术,寻求最佳的生产与运作管理方案,以提高企业的整体效率和核心竞争力。采用合理、有效的调度策略是提高制造企业管理水平的关键,能最大限度地发挥当前资源能力,大幅提高企业的生产能力。生产调度问题覆盖面广、种类多样,其中作业车间调度(Job Shop Scheduling Problem, JSSP)是最具代表性的的调度问题之一,同时也是最难求解的组合优化问题之一。该问题的NP-hard特性决定了,即使在小规模问题上,也不存在有限时间内能求解到最优解的多项式算法。上世纪80年代以来,通过模拟自然界中生物、物理过程和人类行为过程等发展起来的元启发式算法吸引了国内外学者的眼光。这些元启发式优化算法具有收敛速度快、效率高、对问题依赖性小等特点,给解决作业车间调度问题提供了新的思路和方向。同时由于传统JSSP I司题省略了一些约束条件,导致相应的理论研究无法应用到实际生产过程中。基于上述背景,本文结合实际生产面临的多目标性、零等待、柔性等约束,对作业车间调度问题进行一些扩展性研究。本文的主要研究成果如下： (1)针对多目标作业车间调度问题(Multi-objective Job Shop Scheduling Problem, MJSSP),提出了一种四空间遗传禁忌算法(Quad-Space Cultural Genetic Tabu Algorithm, QSCGTA)用来最小化最大完工时间和平均流水时间。在QSCGTA算法中,首先采用基于工序的编码方式和新颖的双向解码方式；接着设计了基于改进的文化算法框架下的并行搜索过程,分别进行全局搜索和局部搜索；针对搜索过程的特点和基于Pareto选择策略,设计了两种不同的信念空间以及相应的接受函数和影响函数；同时对两个搜索过程间的沟通策略也进行了设置；最后采用正交实验设计对算法的主要参数进行分析和选择。基于标准算例的仿真实验结果表明,提出的QSCGTA算法具有明显的优越性。 (2)针对零等待作业车间调度问题(No-wait Job Shop Scheduling Problem, NWJSSP),提出了一种混合带存储完全邻域搜索算法(Combined Complete Local Search with Memory, CCLM)对其进行求解。该算法基于工件排列的编码方式,设计了一种混合双向时间表分配策略将向量解转化为具体调度解；在搜索过程中,增加了存储空间里个体的距离计算,通过淘汰两个距离较近个体的较差个体来提高收敛速度；同时对阈值进行了自适应设置,保证了候选解个体与搜索进程的统一性;算法后期增加了候选解间的灾变操作,一定程度上提高算法跳出局部最优的能力。基于多种标准算例的仿真实验结果表明,CCLM算法在求解各种规模的NWJSSP问题上都具有一定的优越性。 (3)针对多目标零等待作业车间调度问题(Multi-objective No-wait Job Shop Scheduling Problem, MNWJSSP),提出了一种多目标混合带存储完全搜索算法(Multi-objective Combined Complete Local Search with Memory, MCCLM)来最小化其最大完工时间和总拖期。算法采用工件排序的编码方式,综合考虑两个目标函数的特点,提出了多目标混合两向时间表分配策略完成解码过程；初始化阶段使用了随机初始化与基于优先启发式规则(LPT、SPT、EDD)相结合的方法,一定程度上保证了初始个体的质量和多样性；采用基于Pareto支配的方法对阈值、LIVE存储空间进行全新的设置；同样保留距离计算和交叉操作,平衡算法的性能。通过进一步的参数调整和实验仿真比较,实现了算法在求解MNWJSSP问题上的优越性。 (4)针对多目标柔性作业车间调度(Multi-objective Flexible Job Shop Scheduling Problem, MFJSSP),提出了一种多目标改进生物地理学算法(Multi-objective Modified Biogeography-based Opitimization, MMBBO)最小化其最大完工时间、总机器负载和最大机器负载。算法采用基于工序顺序和机器分配的双编码方式,设计了多机器左移解码方法；初始化阶段,采用随机和逐一锦标赛方法产生初始种群；接着基于非支配排序的方法,对算法中的迁入、迁出和变异操作进行离散化设计；并针对非支配解设计了特殊的基于局部搜索的贪婪变异操作。通过在Kacem和BRdata算例上的仿真结果表明,在单目标环境和多目标环境下,MMBBO算法都能有效求解FJSSP问题,并具有一定的优越性。
[Abstract]:With the development of science and technology and economy, the market competition is becoming more and more intense, and the modernization of enterprises is the trend of the situation. As the pillar of the national economy, the manufacturing industry not only needs to improve the production and processing technology, but also needs to adopt advanced management technology to seek the best production and operation management plan, in order to improve the overall efficiency and core competition of the enterprise. A reasonable and effective scheduling strategy is the key to improve the management level of the manufacturing enterprise. It can maximize the current resource capacity and greatly improve the production capacity of the enterprise.
Job Shop Scheduling Problem (JSSP) is one of the most representative scheduling problems, and it is also one of the most difficult combinatorial optimization problems. The NP-hard characteristics of this problem are determined. Even on small scale, there is no finite time internal energy solution. Since the 80s of last century, the meta heuristic algorithm developed through the simulation of biology, physical process and human behavior process has attracted the attention of scholars both at home and abroad since the 80s of last century. These meta heuristic algorithms have the characteristics of fast convergence, high efficiency and small dependence on problems. The job shop scheduling problem provides a new idea and direction. At the same time, because the traditional JSSP I problem has omitted some constraints, the corresponding theoretical research can not be applied to the actual production process. Based on the above background, this paper combines the multi-objective, zero wait, and flexible constraints facing the actual production, and carries out a job shop scheduling problem. The main findings of this paper are as follows:
(1) aiming at the multiobjective job shop scheduling problem (Multi-objective Job Shop Scheduling Problem, MJSSP), a four space genetic taboo algorithm (Quad-Space Cultural Genetic Tabu Algorithm, QSCGTA) is used to minimize the maximum completion time and the average pipelining time. Then, the parallel search method is designed and the parallel search process based on the improved cultural algorithm is designed. The global search and local search are carried out respectively. Two different belief spaces and the reception function and influence function are designed for the characteristics of the search process and the Pareto selection strategy. At the same time, two The communication strategy between the search processes is also set up. Finally, the orthogonal experimental design is used to analyze and select the main parameters of the algorithm. The results of the simulation experiment based on the standard calculation example show that the proposed QSCGTA algorithm has obvious superiority.
(2) a hybrid band storage full neighborhood search algorithm (Combined Complete Local Search with Memory) is proposed for the zero waiting job shop scheduling problem (No-wait Job Shop Scheduling Problem, NWJSSP). The algorithm is based on the coding of the job row row, and designs a hybrid bidirectional schedule allocation policy. The vector solution is transformed into a specific scheduling solution; in the search process, the distance calculation of the individual in the storage space is added, and the convergence speed is improved by eliminating two smaller individuals from the nearest individual. At the same time, the adaptive setting of the threshold is carried out to ensure the unity of the candidate individual and the search process, and the later phase of the algorithm is increased. The catastrophic operation between the selected solutions improves the ability of the algorithm to jump out of the local optimum to a certain extent. The results of simulation experiments based on a variety of standard examples show that the CCLM algorithm has a certain superiority in solving NWJSSP problems of various sizes.
(3) aiming at the multi target zero wait job shop scheduling problem (Multi-objective No-wait Job Shop Scheduling Problem, MNWJSSP), a multi-objective mixed band storage complete search algorithm (Multi-objective Combined Complete Local Search) is proposed to minimize the maximum completion time and total tardiness. The coding method of parts sorting, taking into account the characteristics of two objective functions, proposes a multi target mixed two direction schedule allocation strategy to complete the decoding process. The initialization phase uses the method of combining random initialization with LPT, SPT and EDD based on priority heuristic rules, and ensures the quality and diversity of the initial individual to a certain degree. The method based on Pareto control is used to set up a new set of threshold and LIVE storage space, and the performance of the algorithm is balanced by distance calculation and cross operation. Through further parameter adjustment and experimental simulation, the superiority of the algorithm in solving the MNWJSSP problem is realized.
(4) for multi-objective flexible job shop scheduling (Multi-objective Flexible Job Shop Scheduling Problem, MFJSSP), a multi-objective improved biogeography algorithm (Multi-objective Modified Biogeography-based Opitimization, MMBBO) is proposed to minimize the maximum completion time, the total machine load and the maximum machine load. The method of multi machine left shift decoding based on process sequence and machine allocation is designed. Initial population is generated by random and one by one tournament method in the initialization stage. Then, based on the non dominated sorting method, the moving, moving and mutation operations in the algorithm are discrete design, and the non dominant solution is designed. The special operation of greedy mutation based on local search is carried out. The simulation results on Kacem and BRdata examples show that the MMBBO algorithm can effectively solve the FJSSP problem in a single target environment and multi target environment, and has some advantages.
【学位授予单位】：华东理工大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TB497

【参考文献】