一种解决协调制造调度问题的方法

[摘 要] 在当今制造业全球化的趋势下，复杂产品的生产往往交由一个企业或不同企业的多个车间共同完成，这些具有零部件配套关系的车间共同组成一个协同制造系统。本文针对协同调度问题的基本特征，根据复杂产品协同制造过程的实际需求，建立了两级分布式协同调度系统模型，并进一步研究提出一种改进蚁群算法来解决该问题。

[关键词] job shop调度；协同制造；蚁群算法；禁忌搜索

【中图分类号】 TP18 【文献标识码】 A 【文章编号】 1007-4244（2013）12-326-2

一、引言

在当今制造业全球化的趋势下，复杂产品的生产往往交由一个企业或不同企业的多个车间共同完成，这些具有零部件配套关系的车间共同组成一个协同制造系统。与传统生产调度系统相比，协同生产调度系统的各车间既要根据自身的资源和约束情况，又要兼顾与其具有配套关系的其他车间的生产实际情况来安排加工进度和节拍，问题的复杂性大大提高了。探索研究新的生产调度策略和优化算法来解决协同制造调度问题，是制造业发展提出的新要求。

协同制造系统要求利用不同工厂的制造资源，根据产品生产过程中的不同需求，为产品选择合适的工厂进行加工制造，使制造过程最优化。建立一个动态、柔性、可扩展、及时化的协同制造系统组织模型，是实现协同调度问题的首要条件。

二、协同调度系统结构分析

在协同制造环境下，两个或两个以上具有独立生产能力的工厂，组成了一个相互配合、目标一致的生产共同体。生产系统的行为，按照生产任务的目标和工艺特征等属性表现出不同的特点。于是，工厂间的组织结构可分为三种情况：线型结构、树型结构和网状结构。

（一）线型结构（上下游协同）。如图1所示，线型结构是最简单的协同制造组织结构，工厂之间只具有上下游关系。上游工厂生产出的半成品，转移到下游继续进行加工，这种类型的结构与单一工厂中的流水线生产相似。工厂间协同调度的核心是在半成品到达时，下游工厂能立即组织生产，节省库存费用，这就要求下游工厂充分了解上游工厂的生产状况，及时进行生产准备。

（二）树型结构（分布式协同）。树型结构主要应用于装配型工厂制造。如图2所示，在该结构中，工厂1与工厂2需要协调控制各自的生产进度和节拍，在同一交货期将零部件运输到工厂4，同时合理安排工厂3和工厂5的生产时间，使工厂4和工厂5同时将零部件或半成品送往下游工厂6，由工厂6进行总装配加工，生产出成品。

（三）网状结构（混合协同）。网状结构是较为复杂的一种协同制造组织结构，将网状结构的某一方面进行最简化，就是线型结构和树型结构。在网状结构中，如图3，工厂4向下游工厂5和6供应两种不同的零部件，假设工厂4在一段时间内，生产线上只能生产一种产品，工厂4既是工厂5的上游，同时又是工厂6的上游，而以工厂5为参照物，工厂4又是工厂6的上游的上游，因此在生产调度过程中，工厂4不仅要考虑到上下游的生产进程，还要考虑其自身的生产计划安排，合理控制生产节拍，实现整体最优和个体最优的多对象优化目标。

复杂产品的生产往往需要多个工厂配合完成，受到零部件供需和配套关系约束的工厂之间可以用树型结构（即分布式协同）描述。本文针对复杂产品的生产特点，以分布式协同为对象，研究建立协同调度系统模型，并设计算法进行实现。

三、分布式协同调度问题分析

分布式协同作为协同调度问题中的一种组织结构，既具有一般协同调度问题中多个工厂相互合作共同完成生产任务的特点，又具有其特殊之处。在分布式协同调度制造系统中，制造单元在地理位置上是分散的，制造环境和制造能力都具有多样性。本质上来讲，分布式制造系统的调度问题仍是一个作业与资源的优化分配问题。

结合传统的Job Shop调度问题，分布式协同调度问题必须满足以下约束：1.工厂及其内部的制造资源在地理位置上是分布的；2.每个工厂及其内部的制造资源是独立的自治主体，具有独立的加工能力和决策能力。每台加工设备的生产能力也是独立的，既可以相同也可以不同，但是设备的种类、数量和加工能力是一定的。每道工序在各个机器上的加工时间已经确定，且在整个加工过程中保持不变；3.同一工件的工序间必须根据工艺制造的要求，按照严格的加工顺序依次加工每道工序；4.具有配套关系的工件存在加工次序约束，例如工件A和工件B既是独立的生产任务，又是工件C的零部件，则工件C必须在具有工件A和工件B成品后才能完成加工；5.一个工件的不同工序的加工只能在同一工厂内完成；6.每台机器一次只能加工一个工序，工序一旦进行就不能中断。所有工件具有相同的优先级，在初始时刻都可以被加工；7.假设制造过程中物料的提供与运输都处于理想化状态，能够及时满足生产需求。

根据以上约束条件可知，分布式协同调度是在工艺路线、工件间的配套关系、订单交货期、任务最早开始时间、设备加工能力等条件约束下，对制造任务各工序进行排序，安排合理的加工顺序，并按照排序的结果将它们分配到不同工厂、不同机器上进行加工，从而实现总加工期最短、总流程时间最小等优化目标。

四、协同调度方法

为解决复杂的协同调度问题，根据制造过程协同的目标和制造过程协同作业的具体内容，提出一种基于“分布-递阶”结构和“分解-协调”优化机制的协同调度方法。

（一）“分布——递阶”结构模型。针对分布式协同调度的特点，根据系统中各个工厂的生产能力的不同，将生产任务进行分解，交给各个工厂生产完成，降低生产调度过程的复杂度。

物料清单（bill of material，BOM）描述了最终物件（成品）与低层物件（成品的零部件）之间的关系。物料清单中的每个物件都被赋予一个低层码（low-level code，LLC），这个代码用于标记某个该物件在物料清单中的最低层数。其中，最终物件（就是那些不是任何其它物件组成部分的物件）的低层码是零，只被最终物件使用的组件的低层码是一，只为组件使用的零件的低层码是二，以此类推。在图4中，成品J是低层码为零的最终产品，零件1虽然直接为J使用，但是因为它同时也是部件1（它的低层码是2）的一个组成部分，所以它的低层码是三。

将生产任务经过基于BOM的分解后，得到每一个相关零部件的子生产任务总量，并根据已知的生产调度系统中各个工厂的加工能力，按照一定的原则进行分配，以选定的性能指标为目标进行优化。

（二）“分解——协调”优化机制。构造两级优化框架，通过分布式制造将调度任务分解成子任务到工作单元内解决，进行一级优化；根据一级优化结果，确定瓶颈设备和关键部件为中心，协调具有配套关系的部件的生产进度，对一级优化结果进行修正，完成二级优化。其中，确定瓶颈设备进行重调度是二级优化的中心环节。

在生产制造过程中，瓶颈设备的效率决定了生产系统的效率。因此，要提高系统的产能，首先得找出瓶颈环节，充分利用瓶颈资源。

根据瓶颈的定义，瓶颈（或瓶颈资源）指的是实际生产能力小于或等于生产负荷的资源，阻碍了制造单元中产品的流动。因此要判别一个资源是否为瓶颈，应从该资源的实际生产能力与它的生产负荷来考察。在本文中，根据一级优化结果，计算每台机器的生产负荷，从而确定瓶颈设备。

五、结论

本文分析了分布式协同调度问题的特点，提出了分布式协同调度问题模型；同时，进一步研究探讨了求解分布式协同调度问题的思路，建立了基于“分布-递阶”结构和“分解-协调”优化机制的协同调度方法。但是本文只讨论建立了一种协调制作调度问题的模型和方法，具体的算法实现还需要继续研究。

参考文献：

[1]燕忠，袁春伟.增强型的蚁群优化算法[J].计算机工程与应用，2003，39（23）：62-64.

[2]杨敬松，崔广才.基于混合遗传算法的分布式车间作业调度问题[J].长春理工大学学报，2005，28（3）：19-22.

[3]刘洪威.基于多Agent分布制造调度方法研究[D].沈阳：沈阳工业大学，2007.

[4]吴春辉.基于瓶颈分析的成套订单调度算法研究[D].武汉：华中科技大学，2006.

作者简介：李兰云（1987-），女，汉族，河南辉县人，河南科技学院高等职业技术学院助教，研究方向：工业生产工程建模与控制、优化、管理一体化。

推荐访问： 调度 协调 解决 方法 制造

---