柔性开放车间调度算法研究

发布时间：2020-08-12 22:59

【摘要】：在制造领域,调度是生产管理的核心和关键技术,合理的调度可以缩短制造期、减少资源浪费,提高经济效益。随着生产过程的日益复杂和竞争的加剧,调度的作用越来越重要。柔性开放车间调度问题(FOSSP)是生产中常见的调度问题,也是亟待解决的高难度组合优化问题。本文主要研究加工可中断、不可中断和具有机器使用限制三种情况下的柔性开放车间调度问题(Om(P)|pmtn,ri|Cmax、Om(P)||Cmax和Om(P)|r,aN,I|Cmax)的数建模和近似调度算法设计。针对问题特点,分别采用网络流和半匹配理论设计了相应的近似调度算法,并给出了算法的最坏情况界等性能参数。本文主要研究内容包括以下五个方面： 1.研究了柔性开放车间调度问题的数学建模方法。分析了可中断、不可中断和具有机器使用限制三种情况下柔性开放车间生产过程的约束条件,将它们形式化的表示为一组约束函数,以制造期最短为优化目标,建立了上述三种柔性开放车间调度问题的混合整数规划模型,为算法验证奠定了基础。 2.以制造期最短为优化目标,给出了基于网络流的Om(P)|pmtn,ri|Cmax(?)司题调度算法。算法将Om(P)|pmtn,ri|Cmax问题分解为资源分配和工件排序两个子问题,首先将调度问题转化为网络流模型,通过最大流算法确定使机器满负荷工作的资源分配方案。为了提高最大流算法的效率,研究了融入加工领域知识的活跃顶点选择策略,采用最小负载优先和最大工作量优先启发式规则设计了高效率的最大流算法。针对最大流存在陷入局部优化的情况,给出了优化方法。在最大流的基础上,通过加工时间矩阵的减量集合确定工件的加工顺序 3.针对Om(P)||Gmax问题求解难度大的特点,给出了以稠密调度为目标的近似调度算法求解方案,该方案将调度问题分解为资源匹配和调度优化两个子问题,每次资源匹配所有工件都仅完成一个操作,那么具有m个操作的工件集合需要进行m次资源匹配,通过连接各资源匹配结果得到初步调度解,最后对初步调度解进行优化,消除不必要的机器空闲时间,得到稠密调度解。在两个子问题中,资源匹配是核心问题,文中采用赋权二分图进行建模,通过半匹配求得负载差异最小的资源匹配结果,并且针对小规模和大规模问题分别设计了基于最优增广路径和基于遗传算法的最优半匹配算法。在资源匹配的基础上,本文给出了初步调度解的构造方法及其优化方法。 4.研究了Om(P)|r,aN.I|Cmax问题制造期下界的计算方法。由于存在机器使用限制,无法通过简单的方法获得制造期的下界。因此,本文通过约束松弛将原问题转化为机器使用限制下可中断柔性开放车间调度问题(Om(P)|r,aN.I,pmtn|Cmax),Om(P)|r,aN.I,pmtn|Cmax易于解决,将它的最短制造期作为Om(P)|r,aN.I|Cmax问题制造期的下界。具体的解决方法是首先建立Om(P)|r,aN.I,pmtn|Cmax|司题的混合整数规划模型,在此基础上将模型中的约束条件转化为弧的容量约束,得到问题的网络流模型。然后,通过最大流算法求得它的制造期,以此作为Om(P)|r,aN.I|Cmax问题的制造期下界。 5.针对Om(P)|r,aN.1|Cmax问题,给出了最坏情况界为2的稠密调度算法。Om(P)|r,aN1|Cmax问题允许机器在制造期内含有一个不可用时间窗,并且被中断工件在机器恢复可用后可以继续加工。文中将机器的不可用时间窗定义为虚拟工件,它的加工起止时间等于不可用时间窗的开始时间和结束时间。为了降低问题的难度,首先在不考虑虚拟工件的情况下进行资源匹配,进而通过分析虚拟工件与资源匹配制造期间的关系,得到三种模式关系。针对每种模式的特点,给出了考虑虚拟工件后的资源匹配调整方法。在此基础上,设计了Om(P)|r,aN.1|Cmax问题的稠密调度算法。在算法性能研究方面,本文从理论和算例试验两个方面分析了上述三种柔性开放车间调度算法的性能。在理论上,分析了调度算法的时间复杂度和最坏情况界,并通过随机产生的算例验证了算法的正确性,结果表明算法能够求得调度问题的有效解,并且制造期满足最坏情况界指标。
【学位授予单位】：哈尔滨工程大学
【学位级别】：博士
【学位授予年份】：2011
【分类号】：TH186
【图文】：

总体结构,论文,调度问题,机器

图1.3论文的总体结构图F19.1.3Tllestr·L一etL一e91丑Plloftlledisse一tatio一1第5一章研究了机器使用限制卜柔性川飞放车问调度问题，给{日了最坏情况界为2的稠密调)夏算法。首先，通过分析调度问题的约束条件，建花了i亥问题的混合整数规划模型，为算法ll{确险验i让奠定了基础。进而，为了得到制造)t)]的卜界，本章通过松弛不.IJ一中断约束，建_立了可中断隋况的网络流模型，少}通过最大流算争去求得它「l{J制造期，以此作为机器使用限制下柔性开放车I’l习调度问题的刽jl]造期卜界。对J几机器使用限制，文，「，采川了虚拟工件表示法，将机器的不万!J一用时间窗转化为厂副以l_件，在此幕础卜通过分析虚拟}件与资源匹配制造期间的关系，得到了二几干，1，模式关系及其调整方法。在此从础卜，给出了稠密调度算法。最后分析了稠密调度算法的}l.]I朴」复杂度和最坏情况界，井进行了算例试验，结果表}明算法f]’旨够求得调度问题的稠密调度解，井日.制造均{满足最坏情况界指标。本文最后对个文进行了总结，展望了卜步的付「究}_作。

概念图,无向图,一元关系,边关

lJ一分别为两个11_不相交的r集厂!和价，又寸J一万，{，子千泣边。一比.、，，)，均有、，，:厂，和、，/任矛遥，I_l协条边。都对!、布」个权亚哟。)。_分1冬1是‘类特殊的无向图，图2.2为一个赋权_分图，边表小两个项点I’l]J存在邻接关系。为了进一步分析厂}和价中丁贞点l’[lJl’l勺一元关系，引出了匹配的概念。、{‘.丫2一、’3一、’」..一比一.一、’b图2.2一分图「 19.2.2BipaltilegI’aPI1【定义2.4】匹配:边集合F里万足1冬IC的个匹配，若咚】(尸}，的协个项点都仪’。产一，}，自勺一条边关联11}定义 2.4.J知，}冬 12.3(a)足合李去匹配

【参考文献】