多车间均衡机制的并行综合调度算法研究
第1章 绪论
1.1 课题研究背景
产品生产过程的求解具体体现在纯优化加工调度或纯优化装配调度问题上。很多学者通过利用和对比遗传算法、微分进化法和免疫调度算法等，为流水线生产方式提供了较优的方案；还有很多学者通过利用和对比粒子群算法、蚁群算法、启发式算法[和混合算法等，为多品种小批量的产品生产制造提供较优的调度思想。以上算法有一个相同点，即都将工件作为最小处理单元，并先在生产线加工，再转到装配线组装。由于社会对需求多样化的增长，加快了产品在多元化方面的发展，进而促进了产品制造业往多品种小批量方向发展的趋势。如果依旧单方面优化，必然会导致产品内部的制造过程出现分裂，降低加工和装配的并行性，从而增大了产品的制造周期并减小了企业的利益。因此，越来越多的学者前赴后继的研究产品工件间具有约束的调度优化问题。
1.2 国内外研究现状及分析
各个领域均有许多专家和学者们热衷于研究调度优化问题。研究者们考虑传统的单工厂生产环境的生产调度问题工厂封闭性和独立性较强，并且企业在不断的发展和扩张，单车间调度已无法满足企业的需求，因此分布式多工厂越来越受研究者的青睐。本文重点研究了多品种小批量在多工厂生产制造模式下的调度优化问题，针对分布式多工厂的制造模式并不过分强调协作的多工厂一定是跨国的。
1.2.1 分布式多工厂的分类
基于单工厂的生产管理考虑，多工厂的生产管理需要扩展以下的两方面内容：
1．多工厂之间的生产配套
这种生产配套体现为两点：若异地分布的工厂均能够单独完成某一生产计划，就需设计策略来将生产计划分分配给异地分布的工厂或各工厂分担此生产计划；若任意两个异地分布的工间存在着供应和需求的关系，就需根据产品工件的内部结构来实现工厂彼此间的时间与数量的配套性。
2．生产与运输的协同制造
针对工厂地理位置所具有的异地性特点的问题，就有必要考虑如何利用现有的、便捷的交通工具把下游的工厂所需使用的物料从上游的工厂较快地运送道下游工厂所在地，考虑运输消耗既是企业运营成本的重要部分之一，又消耗了一定的运输时间，因此，生产和运输的衔接有必要进行协作规划。
1.2.2 分布式多工厂算法的概况
针对具有主生产调度的多工厂问题，可采用两阶的顺序处理方式。该算法考虑了采用第一阶处理后的半成品既能够直接传递给第二阶，有能够存入到第一阶段和第二阶段的中间缓存器内。于是建立了相应的模型，将货物的短缺设定为订单的丢失处理，最小化的总成本设定为目标函数。该类问题转化成了线形规划的模型。
第2章 综合调度问题综述
2.1 综合调度问题
随着个性化产品需求的不断增加，大家逐渐对加工和装配可同时考虑的综合调度单件复杂产品引起了关注，若采用以往的纯装配车间调度算法和纯加工的流水调度算法解决加工和装配可一同考虑的综合调度，产品的总处理时间会受到影响。因为采用纯加工和纯组装制造产品，在时效上存在着先后关系，会降低产品制造过程的并行性，导致产品的加工周期延长和交货期延迟。学者们提出了一同考虑加工和装配的综合调度算法，提高生产效率，缩短生产周期。因此，调度算法的全面合理和优化技术的研究，存在着重要的理论意义和广泛的实用价值。
在综合调度问题的研究中，加工设备是加工设备与装配设备的统称，加工工序是加工工序与装配工序的统称。单件产品的综合调度问题可描述为：n个待加工的工序集，根据工序间的工艺次序约束将n个工序分配到m台加工设备上。工序的加工必须满足的一些约束条件，如工序间有加工次序约束，每个工序必须满足其所有紧前工序处理完毕后才可以被加工处理；一个工序在某一时间点只能占用一台设备，还需要满足加工不能中断。
2.2 综合调度的模型
在综合调度研究问题中，所涉及到的主要概念有如下几条：
1．复杂产品
加工工序间具有复杂约束关系，且工艺图呈复杂树状结构图的一类产品。
2．路径
工艺图中某一加工工序到产品最后一道工序的权重之和，该权重一般用工序的加工时间表示，即时间成本。、
3．关键路径
产品工艺图中，所有加工工序路径值最大的路径，对整个产品完工时间有着至关重要的影响。
4．甘特图
即产品所有工序最终调度结果的直观表示图，其中以长条图的样式表示工序及其加工用时，横坐标表示加工工时，纵坐标表示设备资源。
其中的工艺调度模型，可用如图 2-1 表示，树状结构上的结点代表产品的工序，产品 q 包含 7 个工序（工序 1~工序 7）；有向树的边代表工序间加工顺序的偏序关系，说明产品具有约束关系，如处理完工序2才能加工工序5，在工序5和工序4均加工后才能加工工序7；根结点表示复杂产品的最后一个工序，其加工完毕代表该产品加工完毕，其中工序 7 是产品 q 的根结点工序。其中该加工工艺模型中有三条路径，第一条路径为工序2、工序5及根节点工序7，第二条路径为工序 1、工序 3、工序 6 及根节点工序 7，第三条路径为工序 4、工序6及根节点工序7。当各工序的加工时长为已知时，就可求出各路径的权重并确定关键路径。
第3章 车间均衡批次处理的对称二车间综合调度算法 ..................... 9
3.1 引言 ................................ 9
3.2 问题描述 ................................... 9
3.3 方案设计与分析 ....................... 10
第4章 临界值均衡处理的对称二车间综合调度算法 .............. 23
第5章 分批次均衡处理的非对称三车间综合调度算法 .............. 34
第5章 分批次均衡处理的非对称三车间综合调度算法
5.1 引言
第4章提出的临界值均衡处理的对称二车间综合调度，解决了第3章算法导致的设备利用率低的问题。但第 3、4章算法均不能解决非对称多车间问题，于是本章将带有相对独立工序的对称二车间批次处理合理的应用到非对称三车间综合调度问题上。针对复杂产品在非对称三车间生产调度的问题，提出分批次均衡处理的非对称三车间综合调度算法。该算法先按设备所在车间属性将设备分成非对称资源、局部对称资源和对称资源。对非对称资源上工序根据设备属性确定车间，局部对称和对称资源上可加工工序采用批次处理，其中部分工序按提出的工序关联策略确定车间，不能确定车间的工序形成缓存集，按提出的排列均衡调整策略确定集中工序的车间。分配到各车间的可调度工序采用长路径等策略确定再根据工序约束条件确定开始加工时间。通过理论分析，该算法可以在二次复多项式内解决非对称三车间综合调度。
结论
本文主要研究了复杂单产品分布式多车间综合调度问题，该项研究针对对称二车间和非对称三车间分别进行研究，具有一定的理论意义。得出的主要结论如下：
1．针对复杂单产品在对称二车间生产环境下加工，如何有效分解单件复杂产品并快速加工的分布式制造的综合调度问题，考虑到两个车间的资源的高效使用率，才能加快产品生产速度，再考虑工序加工的高度并行和工序之间的迁移次数，因此设计了车间均衡批次处理的综合调度算法。最后通过实例分析该算法，在考虑二车间均衡加工的同时控制了工序的迁移次数，且有较低复杂度。
2．有效减少产品在两个车间进行分布式加工时产生的工序迁移次数，是分布式二车间综合调度算法具有高性能的保障。为更加有效地减少工序迁移次数，对车间均衡批次处理进行逆向考虑，即先考虑位移次数再考虑均衡，设计临界值均衡处理的综合调度算法。最后通过实例分析该算法，在考虑工序工艺紧前约束的同时考虑二车间加工的并行性，能更加有效的减少工序的迁移次数并解决了车间均衡批次处理的设备利用率低的问题，使得车间任务分配更合理，便于多车间的扩展，并将复杂度控制在二次多项式内。
3．针对车间具有特有的加工能力的非对称分布式三车间综合调度问题，要达到复杂产品的有效拆分，控制车间的负载平衡，缩短产品的总体加工时间。在采用批次处理的基础上，将紧前关联策略扩展到工序关联，并设计了分批次均衡处理的非对称三车间综合调度算法。最后通过实例分析该算法，有效的将非对称设备上加工的工序紧凑，从而缩短了产品完工时间，且复杂度控制在二次多项式内。
本文通过批次处理解决多车间均衡机制的并行综合调度问题，批次处理时针对动态生成的叶子节点，运输时间单位化为1。由于时间关系及该问题的刚刚起步，没有研究动态生成的串工序进行批次处理，也没有研究运输非单位化、运输时间与车间地理位置和一次运输可运输多个工序等情况，本文提出的算法可以作为其研究的基础。
参考文献（略）