基于多任务的车间生产调度算法的研究

范营营，刘海彬，赵博选，张 培

(西安交通大学 制造系统与质量工程研究所，陕西 西安 710049)

基于多任务的车间生产调度算法的研究

范营营，刘海彬，赵博选，张 培

(西安交通大学 制造系统与质量工程研究所，陕西 西安 710049)

为解决因中国机械制造业约95%的企业的生产类型为多品种小批量而引出的调度难题，设计了以启发式算法为主的柔性车间调度算法，该算法对于多工艺路线的加工工件，以工件的加工相似性来划分不同单元，以负荷平衡为依据来确定工艺路线，以紧迫系数为优先规则来保证交货期。该调度算法不仅考虑到车间负荷等问题，而且提供了减少设备空闲时间的优化算法，对资源的优化配置和科学运作起到举足轻重的作用。成功实现了“在有限的资源条件下，使加工作业任务在合理的时间内加工完成”，缩短了产品在车间的流动时间，减少了在制品库存，在保证交货期的前提下最大限度地提高了资源利用率，使派工层面科学化、正规化。

生产调度；柔性车间；启发式

随着企业信息化水平的不断提高，在CMIS基础上发展起来的制造执行系统在计划排产方面起到了核心作用。在传统的生产系统中，生产过程存在着许多问题，如生产过程稳定性差、缺乏柔性等，这些问题导致生产过程中的反应弧过大，造成产品堆积、生产效率低下等情况的发生。MES(Manufacturing Execution System)作为企业资源计划和自动控制之间的面向制造过程的集成车间生产管理控制系统，它的信息及时性应该能够较好地适应生产运行变化迅速这一情况。提高企业生产调度的科学性和车间运作的信息化水平，对企业发展不仅具有客观的现实价值，而且还具有巨大和深远的理论意义。

1 算法研究

1.1柔性车间调度问题的描述

产品的工艺路线柔性主要体现在2个方面：一是加工工艺的柔性，产品的某些部分可以选用不同的加工工艺进行实现，而不同的加工工艺所需要经过的工序种类是不同的，这也可根据车间的实际生产状况动态抉择； 二是工序的柔性，产品的某道工序可以在多台设备上加工完成，可以根据实际情况动态选择。

1.2总算法流程及实例说明

在零件存在多工艺路线、工序存在多可选设备的基础上，综合考虑加工时间、加工顺序、生产批量、设备能力、任务交货期等实际生产约束条件，以最短加工时间、最佳设备及单元平衡、最少跨单元加工等作为优化目标，提出了单元构建技术与启发式算法相结合的混合算法。如图1所示。

图1 总算法流程

第1步：初始设备单元划分。

利用数学方法进行对象的分类，利用设备之间的相似性系数表达零件工艺路线之间的相似性，把多种实际因素换算为两个机床的相似性系数，最后进行计算，然后选取相似性系数的最大值，将相似值最大的两个机床分到一个单元，反复迭代，直到把机床划分完毕为止。

第2步：每个零件的工艺路线选择和设备分配。

仅仅考虑零件加工路线的相似性是不够的，还要考虑综合工序、设备、任务等各方面因素，为此采用基于规则的启发式优化算法，兼顾工序的任务交货期和设备能力等实际约束条件，利用启发式算法，对多工艺工件的工艺路线进行选择，实现设备资源的优化分配。过程如图2所示。

图2 选择工艺与设备算法

第3步：每台设备上的任务排序。

对设备的工序任务排序要考虑所有调度工序的最早开工日期，并且按工序的工艺路线来进行顺序调度。从问题本质的角度，此算法考虑了工序的顺序约束。例如在每个调度阶段，优先加工紧迫系数最小的任务的工序，从而达到尽量不延长流程时间的目的，整体上获得最优或者高质量的近似最优解。算法流程如图3所示。

图3 任务排序算法

紧迫系数是指用交付期减去当前日期的差值除以任务的剩余加工时间，用CR表示，当CR等于1表示加工时间刚好够用，大于1表示加工时间富裕，小于1表示已经拖期。当一个作业完成后，其余作业的CR值会有变化，应随时调整。紧迫系数越小，其优先级越高，故紧迫系数最小的任务先进行加工。

第4步：优化排序。

步骤1：遍历所有设备，找出加工时间最长的设备。

步骡2：对该设备，遍历其所有的工序任务队列的加工开始时间、加工时间、加工结束时间，若所有的设备在各个工序段的间隔时间均为零，则排序结果不可调节，转入步骤5。

步骤3：找到第一个开始前空闲时间不为零的工序P(i)，若为首工序，则直接设W为零，否则转入步骤4。

步骤4：设P(K)在该设备上的前一加工任务为P(i)，后一加工任务为P(j)。若P(j-1)的完工时间TF(j-1)小于P(K)的开始时间TS(K)，且max{TF(j)，TS(j-1)} +Tj+TK≤TS(K+1)，则交换P(K)与P(j)在该设备上的加工顺序，令TS(j)=max{TF(j)，TF(j-1)}，进入步骤5；否则暂时置W=0，转步骤1。

其中：P(K)表示工序K的工序名称；TS(K)表示工序K的加工开始时间；TF(K)表示工序K的加工结束时间；TK表示工序K的加工工时。

步骤5：更新队列，重新遍历，恢复前面所有暂时置等待时间为零的工序的等待时间在置零前的值，找出有新的空闲时间的设备，转步骤2，否则结果不可调节，算法结束。

第5步：检验交货期。

检验是否满足交货期，若不满足则设备加班，或者利用外协帮助。

1.3程序运行示例

在Windows 2007平台上利用VS2010工具，以SQL2008为数据库，通过C#编程实现了以上算法，并结合某企业生产数据(见表1)进行试用。以多工艺路线的零件为示例的程序生成结果如图4所示。该示例可以描述为已知几个工件的多个工艺路线，通过上述的算法求解由设备资源构成的制造单元，并把调度结果以甘特图形式展示出来。

2 结束语

总之，随着企业信息化的深入，作业车间的计划调度问题的研究也取得了长足的进步，各种方法和理论应运而生。作业调度算法作为MES的核心，在很大程度上考虑了柔性车间遇到的各种因素，实用性较强，为现行的企业车间生产管理提供了很多的方法，未来必将为我国现行的企业生产管理提供行之有效的策略。

表1 某企业工件数据表

图4 调度结果甘特图

[1] 王爱民，丁国智，宁汝新．制造单元快速构建技术研究[J]．北京理工大学学报，2006，26(10)：851-854.

[2] Yin Y,Yasuda K．Manufacturing cells' design in consideration of various production factors[J]．International Journal of Production Research，2002，40(4)：885-906.

[3] 王风儒，徐蔚文，徐洪副．用效率调度算法求解非标准作业车间调度问题[J]．计算机集成制造，2007，7(7)：13-15.

[4] 盛伯浩，罗振璧，赵宏林，等．快速重组制造系统(RRMS)——新一代制造系统的原理及应用[J]．制造技术与机床, 2001(8):37-43.

[5] 王伟玲．离散型制造企业车间生产调度与控制系统的研究与开发[D]．沈阳：沈阳工业大学，2005.

[6] 桂欢欢．基于MES的车间生产调度系统研究[D]．南昌：南昌大学，2007.

[7] 刘艳丽，刘希玉．启发式算法在计划排产中的应用[J]．计算机技术与发展，2008，18(3)：222-224.

TheSchedulingAlgorithmofWorkshopBasedonMulti-task

FAN Yingying, LIU Haibin, ZHAO Boxuan, ZHANG Pei

(Xi'an Jiaotong University, Shaanxi Xi'an, 710049, China)

In view of flexible workshop scheduling algorithm for the Chinese 95% machinery enterprises with small batch scheduling problem, it presents the heuristic algorithm for multi-process routes workpiece. Dividing into different units to the workpiece based on similarity, it determines the load balancing process route, ensures delivery to the urgency factor based on precedence rules. This algorithm not only takes into account issues such as shop load, but also provides optimization algorithms to reduce the idle time of equipment for optimal allocation of resources. Its goal is "under conditions of limited resources, so that the processing operations task processing is completed within a reasonable time". The application shows that the algorithm can reduce in-process inventory, maximize the resource utilization under the premise of guaranteed delivery, solve the problem of human intervention.

Production Scheduling; Flexible Workshop; Heuristic Algorithm

10.3969/j.issn.2095-509X.2014.03.013

2013-11-19

国家高技术发展计划资助项目(2012AA040907)

范营营(1985—)，女，河北威县人，西安交通大学硕士研究生，专业方向为机械制造及其自动化。

THl8;TP39

A

2095-509X(2014)03-0049-03