【作者】 杨玉珍；

【导师】 顾幸生；

【作者基本信息】 华东理工大学 ， 控制科学与工程， 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 increasing competition in the market and the development of science technology and economy, the tread of enterprise modernization is irreversible. As the pillar industries of the national economy, Manufacturing needs not only the improvement of production and processing technology, but also advanced management technique and the best production and operation management plan, to improve enterprise’s overall productivity and the core competitiveness. Reasonable and efficient scheduling strategy is the key point of improving an enterprise’s management skills to make full use of current resource and greatly increase the enterprise’s productivity.Generally, production scheduling problem has various features with different domains and applications. Job Shop Scheduling Problem (JSSP) is one of the most characteristic scheduling problems and the most difficult combination optimization problems. The NP-hard feature of the problem determines that there exists no polynomial algorithm can obtain the optimal solution in limited time. Since the1980s, metaheuristic algorithms, which originated from an imitation of biological, physical processes and human behavior, attracted the attention of many international and domestic scholars. The metaheuristic algorithms have the characteristic of fast convergence rate, high efficiency, low dependence to the problem, which offer new ideas and orientation to solve JSSP. But because of the omission of constraints, the theory research on JSSP is hard to be used in practical production. Based on the background above, the article makes extending study of JSSP, combined with multi-object, no-wait and flexibility. The main research achievements and innovation point are as follows:(1) For the multi-objective job shop scheduling problem (MJSSP), a quad-space cultural genetic tabu algorithm (QSCGTA) is proposed to minimize the average flow time and makespan. In the proposed QSCGTA, a novel bi-directional shifting for the decoding process is incorporated with the operation-based representation to fulfill the calculation of objectives; moreover, a novel cultural structure in containing double brief spaces and population spaces is presented, and these spaces deal with different levels of populations globally and locally by applying genetic and tabu search separately and exchanges information regularly to make the process more effectively towards promising areas, along with modified multi-objective domination and transform functions; in addition, an orthogonal experiment design is employed to provide a receipt for turning the adjustable parameters of the QSCGTA. The computational results presented significantly prove the effectiveness and efficiency of the cultural-based genetic tabu algorithm for multi-objective job shop scheduling problem.(2) Considering the widely existence of no-wait constraints in many production processes and few relevant literatures, a combined complete local search with memory (CCLM) is proposed to deal with no-wait job shop scheduling problem (NWJSSP). The problem is decomposed into two sub-problems, the sequencing and timetabling problem; a new efficient combined non-order timetabling method, coordinated with objective of total tardiness, is proposed for the timetabling problems; as for the sequencing one, we have presented a modified complete local search with memory combined by catastrophe operator and distance counting. The entire algorithm was tested on well-known benchmark problems and compared with several best existing algorithms. Computational experiments show that our proposed algorithm performs both effectively and efficiently.(3) Based on the above research, a multi-objective combined complete local search with memory (MCCLM) is presented for the multi-objective no-wait job shop scheduling problem to minimize makespan and total tardiness, an initialization based on the LPT, SPT, EDD heuristics is incorporated into the random initialization to generate an initial solution with certain quality and diversity; meawhile a multi-object combined bi-direction timetabling strategy is designed by taking the two objectives into consideration; moreover, some special strategies based on Pareto seletion are proposed; and reasonable parameters of CCLM were determined by performing experiments to identify the tradeoff between effectiveness and efficiency. Various experiments on benchmark problems proved the feasibility and effectiveness of the proposed algorithm.(4) A multi-objective modified biogeography-based optimization (MMBBO) is brought up for the multi-objective flexible job shop scheduling problem (MFJSSP) to minimize makespan, total workload of machines and maximal machine workload. The MMBBO algorithm applies a double coding scheme with operation-based and machine-based vector; a special multi-machine shifting strategy is proposed to decoding the vectors to scheduling solutions; several discrete operators in BBO, such as emigration, immigration and mutation are designed based on non-dominated sorting and a special operator based on local search, instead of mutation, is applied to non-dominated solutions. Comparisons on Kacem and BRdata instances, under both single objective and multi-objective context, indicate the superiority of the proposed MMBBO algorithm in terms of effectiveness and efficiency.更多还原