利用工序迁移时间的多车间综合调度问题研究

发布时间：2016-08-04 09:47

第1章 绪论 

1.1  课题研究背景 
计算机技术的快速发展给其他领域的研究带来了技术革新，各行各业纷纷将计算机技术应用到实际研究中，如生产制造业，已从传统的机械制造，转向现代化生产管理，从制造到生产，以及整个过程的管理均采用现代计算机技术进行了技术革新。其中，备受学者关注的生产调度也成为技术革新的重要环节，多年来调度管理早已与现代计算机技术、数据管理技术相结合。如何提高生产效率成为主要研究课题。 生产效率关系着产品完工时间、产品完工质量，对现代制造业有实际的研究意义。调度研究已经成为一个发展久远的研究体系，调度也随着技术革新，随之赋予新的含义：根据调度环境特点，结合现代计算机技术合理安排调度策略，达到尽早完工、提高制造效率、降低设备损耗、节约制造材料、节约能源、减轻运输压力等目标，这个生产制造过程称之为完整的调度过程。 调度问题由于其发展的特殊性，也成为著名的 NP-hard 问题，备受各界学者的广泛关注。早期的调度研究被提出后，各种优化方法纷纷涌现，成果丰富，为机械制造过程、海陆运输、物资调度、通信传输等带来了进步。近代，随着大数据时代的到来，调度研究不局限于机械制造，调度过程也不局限于工业问题，所以调度环境、调度目的成为实际生产调度的前提，这种复杂的调度过程具有实际的研究意义。 细数传统优化方案，著名的调度算法有：免疫调度算法[1]、遗传算法[2]和微分进化法[3]等，再如针对小批量复杂化产品的免疫进化算法[4,5]、蚁族优化算法[6]、粒子群算法[7,8]、基于神经网络的作业车间调度算法[9]，此外，还有解决设备固定瓶颈的静态调度算法[10]，通过随机序列策略解决柔性调度的算法[11,12]，启发式算法与动态组合优化的混合算法研究[13]，还有结合离散数学建立解决数控机床的调度算法[14]等。
........

1.2  国内外研究现状及分析 
国内外调度问题的研究由来已久，从传统的手工制造、机械制造，到现代应用计算机技术的调度研究，最初学者们明确了生产中的两个方向性问题：加工问题和组合问题。加工过程考虑工件加工之间的关系，如何排序成为复杂的多项式组合问题；而组合问题，在生产中体现在装配、运输、调配物资等方面，如何组合成为运筹学的研究课题[22]。 很多经典的调度优化算法研究加工问题，如图 1-1 所示，考虑工序之间的加工关系；而研究组合问题，如图 1-2 所示，考虑工序生产过程的组合装配问题，这需要将产品加工细化为很多工件的加工，工件之间需要进行装配或运输处理，针对这个部分做组合优化研究[23]。但有些学者发现，将两个关联性很强的部分独立研究，造成了研究的瓶颈，研究结果也与实际状况有所差距，所以综合调度算法应运而生[24]。随着实际生产环境的复杂变化，综合调度着眼于分布式调度问题，并结合实际生产面临的多车间、工序迁移、特殊工序等问题展开研究，并得到了一定的研究成果[25,26]。  
..........

第2章 综合调度问题综述 

2.1  综合调度问题背景 

以往制造生产优化研究往往将加工与装配问题分为两个课题进行研究，随之而产生的问题对实际生产造成的影响不可忽视：加工与装配关系紧密，分开研究割裂加工与装配的约束关系造成结果失真。当大批量流水线生产满足不了社会要求后，小批量复杂产品的生产成为了主流，而加工与装配分开研究成为了主要瓶颈，而综合调度解决了这一问题。统一加工与装配定义为工序，并用工艺树表示工序之间的纵向和横向关系，模拟了实际生产的加工状态，更进一步的，根据加工环境的不同，设定相应的约束条件，如紧密衔接工序、零等待工序、柔性加工工序等特殊问题，提出了解决特殊加工的综合调度算法。

........

2.2  问题模型概述 
综合调度统一工序加工与工序装配，为了合理的表示工序之间的关系，应用工艺树模拟表示产品加工关系，纵向表示工件之间的关系，横向表示工序之间的序列关系。如图 2-1 工艺树，横向关系如 A4、A3 表示工序加工次序与静态加工时间关系。纵向关系如 A5、A6 表示工件之间关联性，工艺树的标准表示法，一般为 An/Mn/Tn，简略表示为 A6/2/15。拟关键路径法从静态角度考虑影响加工完工时间的因素，但加工是动态过程，静态工艺树能反应工序之间的静态关系，所以综合调度算法进一步提出动态关键路调度算法，随加工过程的动态进行，更新关键路径，动态掌握影响加工进程的长路径工序，根据动态路径调整加工次序，得到最优调度结果，大大缩短工期，合理调整工序加工次序[36]。多数调度算法考虑工序之间的关系，而设备的高效利用也是尽早完工的关键，所以设备空闲驱动策略解析了设备空闲和设备忙两种状态，设备驱动需以空闲为信号，若可加工工序不唯一，按照长路径短用时进行排序，达到空闲时间利用高效，并尽早完工的目标。设备忙状态，提高设备并行机制，纵向提高设备利用率。 
............

第 3 章  利用工序迁移时间的两车间设备驱动综合调度算法 ............ 10 
3.1  引言 ..... 10 
3.2  问题模型描述 ....... 11 
3.3  问题分析与相关概念 .... 11
3.4  策略设计 ...... 12
3.5  调度算法设计 ....... 14 
3.6  实例分析与对比 ............ 16 
3.7  本章小结 ...... 24 
第 4 章  利用工序迁移时间的三车间综合调度算法 .......... 25 
4.1  引言 ..... 25
4.2  三车间调度的数学模型 ......... 26 
4.3  问题分析 ...... 26 
4.3.1  三车间设备分析 ..... 26
4.3.2  三车间迁移问题分析 ...... 27 
4.4  策略设计 ...... 28
4.5  调度算法设计 ....... 31
4.6  算法对比分析 ....... 33 
4.7  本章小结 ...... 37 
第 5 章 利用工序迁移时间的多车间综合调度算法 .......... 39 
5.1  引言 ..... 39 
5.2  多车间非对称资源加工模型 .......... 40 
5.3  问题分析 ...... 41
5.4  策略设计 ...... 42 

第5章    利用工序迁移时间的多车间综合调度算法

5.1  引言 
传统的调度方法将加工与装配问题分开解决，但随着研究的深入，综合调度算法提出将加工与装配统一定义为工序，明确了加工不是单一处理的过程，，装配也不是独立的环节，所以两者协同作用可以解决适用范围广一般综合调度问题、对应特殊环境的特殊调度问题。随着工业的进步，两车间、多车间调度成为企业提高生产效率的手段，但随之而来的工序迁移问题成为了学者研究的方向。 为了解决多车间复杂环境下的加工问题，并达到尽早完工的目的，首先考虑了设备利用率高的设备空闲驱动策略，思路是：设备空闲驱动策略是以设备空闲为驱动信号，只要设备空闲就去调度可加工工序；而在多车间加工环境下，会出现相同设备均空闲(不唯一)的情况，处理过程设计为：1．判断可加工工序，若其紧前工序所在车间设备也空闲，为减少迁移次数则安排在紧前工序所在车间；2．若可加工工序判断出工序必发生迁移，则任意安排工序加工车间。3．若某空闲设备可加工的工序不止一个，可加工工序均按条件竞争设备，其中选择长路径上用时短的工序效果更优。 但通过综合研究分析表明：对于多车间复杂加工环境下的调度问题，工序在车间之间的迁移已经成为一个不可避免的问题，若仅仅从减少迁移次数上研究，不考虑迁移时间，更不考虑如何利用迁移时间，那么设备空闲驱动策略需进一步完善。所以，为了考虑工序如何合理选择加工车间，考虑复杂多变的迁移时间如何利用，本章提出了利用工序迁移时间的多车间综合调度算法。
.........

结论 

本文的算法以两车间、三车间、多车间为研究环境，研究工序在不单一车间之间的调度，重点在于设备分布多样化的情况下如何迁移工序，算法研究具有实际意义，综合总结本文如下： 
1．从工序迁移问题出发，考虑工序迁移时间、工序迁移策略，做到合理迁移并利用迁移时间的目的。为了有效减少两车间设备空闲等待时间，提出两车间设备空闲驱动策略，每当设备空闲即对可加工工序进行寻找，并采用长路径和短用时策略排序，调度设备每个空闲时刻搜索到的可加工工序；提高设备利用率，减少迁移时间占用设备加工时间，提出迁移时间利用策略，使设备工作效率提高。实例表明，该算法可充分利用设备空闲时间提高设备利用率。
2．为了对两车间调度问题进行扩展，研究了三车间设备各种组合分布情况，在不同的情况下分析影响工序调度的因素，在早加工结束并合理迁移的目标下研究调度算法。首先，为了解决三车间复杂环境下车间选择问题，分析各个工序与其紧前、紧后工序设备之间的关系，根据设备之间的关联性，合理安排工序加工车间。其次，以往加工过程中，设备空闲才开始调度工序，若遇到迁移情况，设备需等待迁移工序，造成了迁移延误时间，为了降低迁移延误时间，提出待加工工序预判断策略，在紧前工序完工时间，释放的待加工工序中进行预判断，若需发生迁移，则提前迁移到所需车间。最后，有些迁移无法预先完成，造成了设备等待迁移的延误时间，为了利用迁移等待时间，提出迁移时间利用策略，在无法预迁移而造成的迁移等待时间内安排闲置工序加工，使设备有效利用迁移时间。
3．最后一章算法继承前两章的算法研究成果，扩展到多车间调度研究。针对多车间工序迁移问题，为了解决迁移时间影响产品加工时间的综合调度问题，提出了利用工序迁移时间的多车间综合调度算法。为了解决多车间复杂环境下车间选择问题，提出多车间设备属性车间选择策略，根据工序设备属性与紧前、紧后工序加工设备的关联性合理安排工序加工车间；为了降低迁移延误时间，提出待加工工序预判断策略，在工序释放时刻安排迁移工序预迁移到加工车间；为了利用迁移等待时间，提出迁移时间利用策略，在无法预迁移而造成的迁移等待时间内安排闲置工序加工，使设备有效利用迁移时间。实例表明，该算法可充分利用设备空闲时间提高设备利用率，并有效利用迁移时间达到尽早完工的目的，且算法复杂度不高于二次多项式。 
.........
参考文献(略)

本文编号：84420