何 天 行

(杭州电子科技大学信息与控制研究所 浙江 杭州 310018)

0 引 言

调度是生产过程中一个非常关键的问题，因为它对生产的效率和资源利用率起到非常重要的作用。在过去的二十多年里，生产过程调度模型优化这一研究领域受到了相关科研人员的极大重视，一方面这是受来自提高效率、削减成本的压力和刺激，另一方面则是由于相关建模与求解技术的重大进步和计算能力的迅速增强。

基于连续时间的批处理短期调度模型在实际生产过程中应用更加广泛，一直被科研人员所重视。Pinto和Grossmann(1995)[1]提出基于连续时间的MILP模型，该模型主要解决多工序批处理短期调度问题，解决方法主要思路为在两个平行时间轴上分配订单和设备单元，然后使用一组变量集合来进行匹配，该组变量集合由四个参数构成，分别为工序、订单、时间槽、设备。Pinto等[2]又提出一种改进模型，创新地将预排序约束加入到设备时间槽中，核心方法是利用订单预排序，用包含更少参数的变量替代，以此减少所需的计算时间。但该模型存在很明显的短板，它只能用于预排序的订单，仍无法解决顺序约束。文献[3]提出的MILP模型，主要针对于单工序多产品可并行生产的批处理短期调度问题，重点解决了订单的顺序问题，所用的方法是使用了一组含三个参数(前序订单、后续订单、设备)的变量集合。文献[4]提出了一种新的对于批处理过程短期调度的连续时间模型，该模型最大的优点是极大地减少了决策变量的数量，所采用的方法是将订单和设备分离，但仍无法处理预排序问题的限制。文献[5]提出的连续时间MILP一般模型，是基于顺序依赖约束的多工序、多产品批处理短期调度问题。此模型创新地将预排序约束解放出来，让研究者可以自己选择是否考虑，在有效减少了变量数量的同时仍可以兼顾订单排序和订单切换。

王凌等[6]论述了分布式制造环境下，生产过程调度研究现状和相关成果。范华丽等[7]认为调度模型需要经受多变环境的考验，在静态环境下研究出的模型无法在实际生产中应用。其主要论述了实际生产过程中存在扰动的动态调度研究现状以及未来方向。刘民[8]认为在生产过程中会产生大量数据，对这些数据的研究可以有效地提高调度效率,本文着重论述了基于生产数据的调度方法研究情况。

目前，印染生产过程方向的调度研究十分有限。周晓慧等[9]提出基于时间槽描述生产过程调度模型,使用预排序规则和一个三维约束变量实现印染车间的精确调度。胡颖等[10]考虑了染色设备清洗和更换染料所需的时间，在此基础上建立坯布颜色相关的调度模型。文献[11]针对印染生产过程中生产设备之间切换成本、生产设备负荷平衡的问题,分析生产过程中的瓶颈设备来优化瓶颈设备使用、提高利用率,研究订单式印染生产过程，采用分层赋时着色Petri网(H TCPN)技术建立生产过程的模型。胡新晖等[12]采用再调度策略，在静态调度的基础上，考虑新订单的加入，将所有未完成调度任务重新整合后再分配到相关设备作业。

1 印染生产工艺

建立生产过程优化调度模型的前提是对相关生产工艺进行完备的描述和抽象。印染生产过程十分复杂，从坯布到成品要经过很多道工序，如图1所示，它描述了印染生产工艺与工序，包括烧毛、退浆、煮练、漂白、丝光、印花、染色、柔软、拉幅、预缩、质量检测和产品包装等。各工序内的生产过程是连续的，但工序之间既有间断也有连续，间断时用小车把前道工序的半成品推到下道工序。把这些工序划为三个阶段：前处理工艺、印染工艺和后整理工艺。前处理主要有坯布的烧毛、退浆、煮练、漂白和丝光，其中煮练主要是去除布匹上的杂质，丝光是增加布的光亮度；印染指染色和印花，是决定颜色的关键工序；后整理主要是印染后的柔软、拉幅、预缩、质量检测和成品包装。

图1 印染生产工艺流程

不同产品在每一道工序的设备上加工速度是不同的，加工速度由车速来体现。同一产品在同一道工序的不同设备上加工速度也是不同的。

每一小车的布有几百或几千米，以一小车为单位安排一定的车速进行加工。两道工序之间若是离散的，即用小车把半成品布推到下一道工序然后装机生产，这一时间就是两道工序之间的准备时间，这一时间与成品和设备无关，是固定的。

但染色机先染较深色的布，再染浅色的布，那么，染色机要清洗。而清洗的时间与两个颜色的深、浅对比度有关，也就是说，染色机的切换生产的切换时间与产品有关。

印染车间总体上是一个订单驱动的顺序生产过程，其中单个工序内是连续的，不同工序间既有连续也有间隙。

2 印染调度特征描述

从以上的工艺和生产流程看出，印染是顺序生产过程，完成一个订单需要经过的工序多，但不同订单所需经过的工序不一定相同，工序内是连续的，有的几道工序连在一起也是连续的，如柔软、拉幅和预缩一起是连续的，有的工序间是间隙的，如丝光到染色。因此，印染生产过程调度是Jop Shop问题，既有连续，又有间隙。

针对印染生产的特点和实际印染企业的经营管理方式，在建立印染生产过程的优化调度模型前，给出如下问题特征：

(1) 无材料等约束。在印染生产过程中，设备保持完好，不影响生产，原材料、工人和能源等都保证充足。

(2) 非抢占式生产。任何作业不能抢占已经在加工作业的设备。因为，每一小车的布有几百或几千米，以一小车为单位安排一定的车速进行加工，不可能不加工完，布是连续的。

(3) 设备车速与产品和工序相关。产品在某道工序的加工车速只与设备相关，并且是固定的，因此，产品在每一工序的加工时间是可计算的。

(4) 设备准备时间和切换时间。染色机加工深浅对比度大的产品切换时间是不固定的，但可以给出切换时间表，工序间的坯布小车运输加上设备开工准备时间是固定的。

(5) 24小时生产。有的印染企业两班倒，有的三班倒，全天24小时生产。所以，每天按24小时调度。

(6) 为了表述简单，假设一个订单只有一个产品。

3 调度模型

数学模型由约束和调度目标组成，约束要求按一定的条件安排订单在每一道工序的加工，而调度目标要求这种生产安排要最大程度地满足调度目标。

3.1 模型约束描述

(1) 生产设备上相邻加工订单的约束。

(1)

式(1)表示：如果在同一工序l上存在两个相邻订单i、j，并且使用工序l中的生产设备u来加工订单i，那么订单j就只能在生产设备u上进行加工。即在工序l上相邻加工的订单必须分配在同一台生产设备上加工。

(2) 生产过程中任一工序上任一订单最多存在一个唯一的直接后序加工订单。

(2)

式(2)表示：任一台生产设备一次只能加工一个订单，被加工的订单都有一个唯一的后续订单，最后一个订单除外。式(2)中不等号成立的条件：被加工的订单是最后一个订单。

(3) 生产过程中任一工序中任一订单最多有一个前序订单。

(3)

式(3)表示：任一台生产设备上加工的订单都有一个唯一的前序订单，第一个加工订单除外。

(4) 主要决策变量Wiu和Siu的关系。

Wiu≥Siu∀i∈I,u∈U

(4)

式(4)描述的逻辑是：订单i在生产设备u上的分配变量大于等于表示订单i是否为生产设备u上第一个加工订单的变量。如果订单i是生产设备u上的第一个被加工的订单，则此时变量Wiu和Siu的值都将等于1，等号成立。而如果订单i是分配在生产设备u上加工但却不是第一个被加工的订单时，则Wiu>Siu，不等号成立，即Wiu=1，Siu=0。剩下最后一种情况是订单i不在生产设备u上加工的情况，则两个变量的值都为零，等号成立。

(5) 生产过程中在每台生产设备上最多有一个初始订单。

(5)

(6) 生产过程中任一工序中任一订单必须由唯一一台生产设备加工。

(6)

式(6)表示：在所有工序中任一订单必须由唯一一台生产设备进行加工。

(7) 工序中订单起始时间和完成时间的关系。

∀l,m∈Li,m>l,i,j∈I

(7)

(8) 同一道工序上两个相邻订单的起始时间关系。

(Tiu+CTiu+Xijl×Ciju)

∀i,j∈I,i≠j,l∈L

(8)

式(8)描述了：任一工序，排位靠后的订单必须等前加工订单完成，才能开始启动加工。

(9) 订单延期。

∀i∈I,li∈L

(9)

3.2 模型目标函数

调度模型的目标函数定义为：在保证能按时完成订单的前提下，使得订单完成的提前期最小。

∀i∈I

(10)

式中：Li是加工订单i要经过的工序。

4 实例分析

本案例要调度的订单共5个，这些订单涉及的工艺和工艺路线如图2所示，共9道工序。

图2 案例订单涉及的印染生产工艺流程

表1给出了这些订单要经过的工序和每一工序上的加工设备。

表1 订单涉及的工序和设备

表2给出了5个订单的产品信息，包括订单名称、产品名称、产品颜色、产品生产数量、客户要求的交货期和产品加工的工艺路线。

表2 订单的相关数据

印染产品的加工从翻缝开始到包装结束要经过近20道工序，但不是所有的产品都要经过所有这些工序。如，表2中的全棉弹力帆布要经过9道工序，而全棉斜纹只经过6道工序，这是因为不同的产品对工艺有不同的要求，包括坯布质地和产品的颜色，如灯芯绒和平布对加工工艺的要求就不同，这也是印染调度是 Job Shop 问题的原因。

根据案例的求解结果，画出如图3所示的甘特图，图3中的U1表示设备1，I1表示订单1，如，订单1(I1)经过9道工序，在每一道工序使用的设备分别是U1、U2、U3、U4、U5、U6、U7、U8、U9。虚线和实线之间的时间间隔表示二道工序之间的推小车时间与设备准备时间之和。

图3 考虑工序间隙和染色机清洗的案例甘特图

工序7是染色工艺，订单2在完成丝光工序后进行染色，从图3看出，在染色时要清洗机器。这是因为，订单1产品的颜色是黑色的，而订单2产品的颜色是灰色的，图3指出，染色机U7是先加工订单1的，然后再加工订单2，黑比石头色要深的多，所以要清洗。

从图3还可以看出，调度结果染色机只清洗了一次。这是因为订单1、2、3、4和5产品的颜色分别是黑色、石头色、淡黄、骆黄色和橙色，后面四种颜色差别较小，而从图3看出，染色机加工的顺序是订单1、2、3、4和5，所以后面染色机就不需要再清洗。

5 结 语

本文通过对生产过程优化调度模型和印染生产工艺的研究，在现有模型的基础上，充分考虑了染色生产过程各工序间隙和染色机清洗两大主要影响因素，制定了相关调度规则。通过案例仿真，获得调度结果并以甘特图的形式展现，验证了考虑工序间隙和染色剂清洗调度模型的有效性和可行性。