SIA OpenIR  > 工业控制网络与系统研究室
面向作业车间调度问题的静动态调度方法研究
Alternative TitleResearch on Static and dynamic Scheduling Methods for Job Shop Scheduling Problems
薛玲玲
Department工业控制网络与系统研究室
Thesis Advisor于海斌
Keyword作业车间调度 遗传算法 邻域结构 动态调度 本体建模
Pages118页
Degree Discipline控制理论与控制工程
Degree Name博士
2021-05-21
Degree Grantor中国科学院沈阳自动化研究所
Place of Conferral沈阳
Abstract作业车间调度(Job Shop Scheduling, JSP),是在满足工件加工约束的前提下,对工件的加工路线进行优化,指导生产顺利而有序的进行,从而达到提高车间生产效率、降低加工成本和满足用户需求等实用价值。作业车间调度问题作为一类典型的组合优化问题,当数据规模较小时,可以采用线性规划法、分支定界法等精确法找出最优解。但由于其NP难的特性,当数据规模增加时,会造成解空间中个体的组合爆炸,采用精确法很难在可接受的时间内找到合适的解。而以智能优化算法为代表的近似方法,以其求解速度快,求解质量高等优点,成为了求解作业车间调度问题首要采用的方法。作为一个搜索速度快、能够实现隐形并行搜索的群搜索智能优化算法,遗传算法及其改进算法被广泛用于求解作业车间调度问题。本文主要从作业车间调度问题的静态研究和动态扰动发生时的动态响应两个方面进行研究。针对静态车间调度,从单目标和多目标两种不同优化指标出发,采用不同的改进遗传算法进行求解,找到满足优化指标的最优解集。针对以最小化最大完工时间为优化指标的单目标车间调度问题,提出了一种以遗传算法为基本框架,嵌入块结构邻域搜索算法作为局部搜索的优化算法。在构建邻域结构时,将基于工序的编码方式与基于关键工序块的邻域生成方法相结合,以块首工序或块尾工序为中心,通过对中心工序与块内工序及其紧前、紧后工序在工序序列中位置的分析,判断以工序交换、前移和后移生成的邻域个体方案中是否存在与原个体相同的方案或生成的邻域个体之间是否存在相同方案,达到减少冗余邻域个体的目的。仿真实验结果验证了算法的有效性。与单目标优化不同,多目标作业车间调度问题考虑多个目标的同时优化。因此,多目标调度的结果一般不是一个最优解,而是符合Pareto最优概念的一组解。本文采用非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm Ⅱ, NSGA Ⅱ)作为求解算法。为加快算法中非支配排序过程,提出了一种基于位置信息的非支配排序算法,将改进后的非支配排序过程加入到NSGA Ⅱ中。在相同测试数据集下,算法得到的非支配集与其他算法比较,对算法的有效性进行验证。针对生产过程中动态扰动,导致生产不可行或生产性能下降的问题,本文提出了一种具有鲁棒性初始值的动态调度策略。考虑到生产的动态性,为提高初始调度方案的鲁棒性,在生成初始调度方案时提出了一个两级优化算法,第一级优化采用静态调度提出的优化算法,第二级优化时采用与调度鲁棒性强相关的替代测度作为优化指标,对第一级生成的初始调度方案进一步优化。在扰动事件发生时,不但考虑重调度后的生产效率,同时考虑重调度的稳定性,采用调度修复与完全重调度两种调度策略实现重调度过程。最后,采用模块化建模的思想,构建了作业车间综合本体库,实现用户订单信息的采集,将采集到的车间生产信息和设备状态传递给调度算法,为调度算法的实现提供了基础的知识支撑,并同时实现生产过程中信息的实时更新与查询。
Other AbstractJob shop scheduling problem (JSP), which is used to optimize the processing route under the technical constraints of workpieces, can ensure a safe and orderly production. A reasonable scheduling plan can help to improve production efficiency, reduce processing cost or meet the needs of customers, and so on. As a typical combination optimization problem, the accurate methods such as the linear programming method, the branch and bound method can be used to obtain optimal solutions as the scale of JSP is small. However, due to its NP-hard characteristic, it is difficult to find satisfactory solutions within an acceptable time using the accurate methods while the scale of JSP is very large. The approximation method, typified by intelligent optimization algorithms, has become the preferred method for solving the JSP problem, as it can obtain optimal or near-optimal solutions with fast solution speed. Genetic algorithm, a typical swarm intelligence optimization algorithm, is widely used to solve the JSP, as it has the merits of quick search speed and invisible parallel search. This paper conducts researches from two aspect: the static scheduling problem and the dynamic scheduling when the dynamic disturbance occurs. This paper mainly researches the static job-shop scheduling problem from single and multiple performance indicators. Different improvement methods are used to get optimal solutions or solution set based on the genetic algorithm. Aim to minimize the maximum completion time, a hybrid genetic algorithm is proposed to solve the single-objective scheduling problem. The proposed algorithm, grounded on the framework of genetic algorithm, a block structure neighborhood search algorithm is embedded, to strength the local search capability. The operation-based encoding method is combined with the critical operation block-based neighborhood generation method to constructing the neighborhood structure. Utilizing the first operation or the end operation as the center of the block. Then analyzing the position relations between the central operation with intra-block operation and their predecessor and successor operations in the operation sequence to determine whether the exchange or move processes produce the same schedules or anyone same as the original individual. which can reduce redundant neighborhood individuals. The effectiveness of the proposed algorithm is proved by several simulation experiments on typical examples. Different with single optimization, the multi-objective scheduling problem need to consider multiple objectives at the same time. Therefore, the result is a set of non-dominated solutions instead of an optimal one. The non-dominated set is also called the Pareto set. An improved non-dominated sorting genetic algorithm Ⅱ (NSGA Ⅱ) is used to solve the multi-objective job shop scheduling problems. A set-based non-dominated sorting algorithm (SETNDS) is proposed to accurate the non-dominated sorting process. And the proposed algorithm—SETNDS is added to the NSGA Ⅱ replaced the traditional fast non-dominated sorting algorithm. The effectiveness of the proposed algorithm is verified by comparing the Pareto set obtained with other algorithms under the same testing dataset. Dynamic disturbances, happened during the production process, can decrease the production performance or lead the initial scheduling plan infeasible. A dynamic reschedule approach with robust initial schedule is adopted to solve these problems. Consider the dynamic nature of the production process, a two-level optimization algorithm is proposed to improve the robustness of the initial scheduling plan. The first level optimization process utilizes the optimization algorithm abovementioned to generate a scheduling plan related to the basic job shop performances. The second level process adopts the surrogate measures, which is strong correlation to the scheduling robustness, to further optimize the initial scheduling plan generated at the first level. Not the production efficiency will be considered, but also the stability of rescheduling will be considered when the rescheduling strategies are introduced to handle the disturbances. The schedule repair and complete rescheduling methods are adopted to process the disturbance events. Finally, a comprehensive ontology of the job shop is constructed based on the modular modeling. This ontology can help to collect the information of user orders, and transfer process information to the scheduling algorithms. The real-time update and query of information in the production process can be obtained.
Language中文
Contribution Rank1
Document Type学位论文
Identifierhttp://ir.sia.cn/handle/173321/29013
Collection工业控制网络与系统研究室
Affiliation中国科学院沈阳自动化研究所
Recommended Citation
GB/T 7714
薛玲玲. 面向作业车间调度问题的静动态调度方法研究[D]. 沈阳. 中国科学院沈阳自动化研究所,2021.
Files in This Item:
File Name/Size DocType Version Access License
面向作业车间调度问题的静动态调度方法研究(4811KB)学位论文 开放获取CC BY-NC-SAApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[薛玲玲]'s Articles
Baidu academic
Similar articles in Baidu academic
[薛玲玲]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[薛玲玲]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.