登录

  • 登录
  • 忘记密码?点击找回

注册

  • 获取手机验证码 60
  • 注册

找回密码

  • 获取手机验证码60
  • 找回
毕业论文网 > 毕业论文 > 机械机电类 > 机械工程及自动化 > 正文

基于数据驱动的混合学习算法求解大规模并行机调度问题毕业论文

 2021-11-07 09:11  

摘 要

调度任务是根据生产目标和约束,为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。随着车间生产规模日益增大,利用传统优化算法求解车间调度问题具有耗时长、不稳定等问题,不适合日益加快的车间生产节奏。因此,本文针对单工序并行机调度问题,提出了一种面向工业大数据的混合学习算法进行求解。首先,采用基于TLBO 选择框架的遗传算法进行离线学习,选择最优的方案存储并建立调度方案库,随后,提出了基于改进k-means算法对方案库进行聚类;最后,选择方案库中距离目标方案最近的聚类中心,并混合邻域搜索求得最优的调度方案。实验对比其他算法,结果表明,该混合学习算法具有更快速、更精确、更稳定的性能。

关键词:并行机调度,TLBO选择框架,k-means算法,离线学习

ABSTRACT

Scheduling task is to determine the specific processing route, time, machine and operation for each processing object according to the production goals and constraints. A good scheduling strategy has a great effect on improving the optimality of the production system and improving economic efficiency. With the increasing production scale of workshops, the use of traditional optimization algorithms to solve workshop scheduling problems has the problems of time-consuming and unstable, which is not suitable for the increasingly accelerated workshop production rhythm. Therefore, this paper proposes a hybrid learning algorithm for industrial big data to solve the single-process parallel machine scheduling problem. First, the genetic algorithm based on the TLBO selection framework is used for offline learning, the optimal solution storage is selected and the scheduling solution library is established. Then, a clustering solution library based on the improved k7-means algorithm is proposed; finally, the distance in the solution library The nearest clustering center of the target solution, and mixed neighborhood search to find the optimal scheduling solution. Experimental results show that the hybrid learning algorithm has faster, more accurate and more stable performance.

Key Words: parallel machine scheduling, TLBO selection framework, k-means algorithm, offline learning

目录

摘 要 I

ABSTRACT II

第1章 绪论 1

1.1 研究背景及意义 1

1.2 国内外现状分析 1

1.3 本文主要工作与结构 3

第2章 车间调度模型介绍 5

2.1 架构分析 5

2.2 问题描述 6

2.3 假设条件 6

2.4 本章小结 6

第3章 调度决策系统 7

3.1 离线学习模块 7

3.1.1 遗传算法简介 7

3.1.2染色体编码与适应度函数设计 8

3.1.3 交叉操作 8

3.1.4 变异操作 9

3.1.5 选择操作——TLBO框架 10

3.2 在线调度模块 11

3.2.1贪心选择思想 12

3.2.2 K-means聚类算法 12

3.2.3 剔除原则 12

3.2.4 增添原则 13

3.2.5邻域搜索 14

3.3 本章小结 14

第4章 实验结果与比较 16

4.1 实验设计 16

4.2 数据分析 16

4.3 本章小结 23

第5章 总结与展望 24

5.1 全文总结 24

5.2 研究展望 24

参考文献 25

附录 27

致谢 33

  1. 绪论

1.1 研究背景及意义

随着德国"工业4.0"的进一步提出,被国际媒体称为当今世界"制造中心"的中国在此基础上将要在德国开始一场世界上规模空前的工业革命—"中国制造2025"。"中国制造2025"目的主要在于进一步提高智能装备制造业的现代智能化制造水平,向无人工厂、智能装备制造等新模式的转型。中国智能装备制造的发展是传统制造业与现代信息电子技术进行深度融合的一条必经之路,是其建立智能装备制造业核心竞争优势的关键手段和措施,而在中国智能装备制造的行业大趋势与德国工业4.0、中国制造2025的国家战略导向下产生了工业生产数据与工业生产管理相结合的需求。当今车间生产规模日益增大,企业间的竞争越来越激烈,企业要想寻求生存和发展的机会,就必须使生产车间具备对,环境改变的快速的、柔性的适应能力,即企业将会逐渐转型为大规模个性化(柔性)制造模式。然而大多数传统调度理论和方法由于其计算时间复杂度大和调度模型的约束趋于理想化使其不能很好应对在日益复杂多变的生产环境下动态的作业调度需求。企业的这类制造模式对调度算法提出了更高的需求,如何在面对复杂多变的大规模问题的时候,开发精确、稳定、速度调度模型和算法非常重要。研究新环境下混合流形式的生产调度问题具有重要意义。

1.2 国内外现状分析

如今制造企业的信息化建设已广泛开展,各类生产信息管理与控制系统得到普遍应用,像绝大多数制造企业使用了企业资源计划(Enterprise Resource Planing,ERP)等生产信息系统,持续产生并存储着各类生产数据,这些生产数据中隐含着有关生产调度的重要特征信息和有价值的调度模式[1]。一种新的研究思路便是通过挖掘生产数据中的调度知识,进而构建出生产数据驱动的调度策略决策系统,用于指导动态作业车间的排产调度。其中纪志成等针对模具制造车间的调度特点,提出基于实时生产数据采集的调度方法,具体在静态调度的基础上,对生产现场动态干扰事件所产生的数据进行实时收集,用于对原调度结果作调整,进而提供符合实际生产环境的调度方案[2]。吴秀丽等人针对于智能制造环境下的混合流水车间实时调度问题, 提出了基于BP神经网络的数据驱动的实时调度措施, 数值试验表明所提措施优于固定单一调度规则, 在不同的调度性能指标下其均呈现稳定且良好的结果[3]。吴启迪等人研究了一种基于数据驱动的半导体生产线调度框架。通过该框架模型,可以对半导体生产线根据其当前的生产状况实时确定接近最优的调度策略。结果表明,数据驱动的动态调度方法不但能优于单一的调度规则,同时也能满足生产线调度的实时性要求[4]。王家海等人设立了基于本体的调度知识关系模型和知识表示,将支持向量机和cart决策树学习算法相结合,实现了数据驱动的调度规则获取,剖析了调度知识挖掘框架下调度规则的挖掘进程[5]。Azadeh等使用作业车间调度仿真得到的部分调度样本数据集来训练人工神经网络,再利用训练好的人工神经网络模型在完整的候选调度规则集中进行搜索,寻找能使当前车间生产任务的完工时间最小化的一个作业机器的调度规则组合[6]

当调度规模和任务动态性提高了之后,可能会存在稳定性、求解速度的问题,特别当数据规模变大了之后,另有学者通过改进传统算法来解决并行机调度问题,如Ye Xun, Ling Wang等人提出了一种有效的基于教学学习的优化算法(TLBO),比较结果证明了所提出的TLBO算法的有效性和高效率性[7]。何敬东等人在遗传算法设计的基础上,提出了一种新的染色体合成方法,可以更好地表示解空间,提高求解效率[8]。史烨等提出了一种局部优化的模拟退火算法。实验结果表明,该算法能在有限的时间内获得满意的大规模问题解[9]。张清勇等人针对异构工厂中的分布式并行机调度问题,提出了一种新的帝国竞争算法。结果表明,该算法在求解分布式并行机调度问题时具有较强的搜索优势和良好的稳定性[10]。裴小兵等人针对无等待约束的流水车间调度问题,提出了一种新的混合改良遗传算法。通过对比实验,验证了新遗传算法的有效性[11]。 Nguyena 等人针对混合作业车间调度问题的特点,提出了一种改进的遗传算法来最小化混合作业车间计划工期的调度问题[12]。Hang ZHAO等人为了克服遗传算法早期收敛的缺点,解决搜索过程中的局部最小化问题,针对混合流水车间调度问题,提出了一种改进的循环搜索遗传算法,实验结果表明,改进算法能很好地避免局部极小值的紧急情况,收敛速度快,验证了算法的有效性[13]。Rui Zhang等人为了解决多目标调度问题,提出了一种结合了局部搜索模块的基于Pareto的遗传算法,该算法利用了为每个目标函数专门开发的邻域属性。在现实世界和随机生成的调度实例上的计算实验均证明了该方法的有效性[14]。孙志峻本文研究了基于遗传算法的多工艺路径车间生产智能调度,在兼并考虑加工计划和生产调度的前提下,提出了将遗传算法和调度规则相结合的算法,实验结果表明,该算法具有可行性,与传统的静态优化调度相比具有明显的优势[15]。Xu Bing等人提出了一种新的遗传染色体编码方法——非完整编码,用于解决车间作业调度问题。实验结果表明,该方法能够在合理的时间内得到临近最优解,通过剔除高冗余和很少无意义地基因,可以使遗传更有效[16]。ZHAO Shi-kui等人针对以makespan为目标的车间调度优化问题,提出了一种基于空闲时间的邻域搜索遗传算法,通过典型实例测试,验证了所提算法地其有效性[17]。Qi C等人针对HFSP问题的NP-hard特征,提出了一种可变邻域搜索的改进遗传算法,建立了HFSP的优化模型,并给出了算法的流程图。通过实验对比,表明了所设计的算法能高效率地求解HFSP问题[18]

您需要先支付 80元 才能查看全部内容!立即支付

企业微信

Copyright © 2010-2022 毕业论文网 站点地图