特许连锁模具制造网格下的制造单元启发式调度算法*

陈 娟，王宗忠

(1.广东工贸职业技术学院，广州 510510;2.广东工业大学，广州 510090)

1 特许连锁模具制造网格下的制造单元

目前我国模具制造业尚处于不发达阶段:大多数模具制造企业规模小，缺乏关键设备，加工手段原始，生产效率低下;企业各自为战，分散化经营，行业整体联系松散;模具设计、工艺与操作流程不规范，质量无法保证;模具生产管理流程不规范，无法有效控制制造成本和交货期。反观国际模具制造市场的最新发展趋势，一些大型生产厂商一直试图减少模具供应商的数量以减少管理的复杂性，并增大采购批量获得折扣来降低成本，此外，延迟付款和分期付款的付款方式业经成为入围大企业供应商的必须服从的条款。这些弊端造成了我国模具尤其是大型、精密、复杂、长寿命模具供不应求的局面，使得国内大多数模具企业缺乏国际市场竞争力，不具备承接大公司或大模具订单的能力。弱化或打破企业间的壁垒，进行行业资源整合是摆在全行业面前重要而迫切的课题。针对这种情况，笔者所在的研究小组提出了用特许连锁的经营模式来改造模具行业的新思路［1-2］。我们认为，根据中国模具行业的现状，特许连锁是实现行业资源整合的较好方式。同时，我们借鉴了近几年国内外一些专家学者提出的开放式网格服务结构OGSA［3］来构造模具制造系统。基于模具制造中资源配置的重要性和困难性，我们将物理意义上的制造资源与相应的基本管理方法相结合，形成具有提供某类服务能力的制造网格单元，对其进行标准化封装，并提供一组接口，所有的网格服务都通过这些接口实现。简单和基础的服务可以形成更复杂、更高级、更抽象的服务，这样层层迭进就可以十分方便的实现资源配置的快速性和高效性、制造过程的标准化以及制造系统的扩展。例如，我们将设计、加工、装配、存储、运输等制造环节看作服务过程，将内部的资源，如设备和人力资源，连同其中的计划过程、调度过程以及管理过程一起封装成制造网格系统的组成元素——网格单元，该单元只通过接口与外界联系，完成相应的制造服务(任务)。将上述特许连锁经营理念与网格化制造模式相结合得到模具特许连锁制造网格的示意图如图1所示。

图1 模具特许连锁制造网格

在统一承接了客户的模具订单后，作为网格中心的连锁总部(大型模具企业)将订单以企业制造项目(在模具企业，一套模具为一个项目)的方式来进行管理，从事以下几方面的工作:①承担主要的订单设计任务(这是因为大多数模具企业不具有设计能力)，如果某些加盟企业具有小订单的设计能力，可考虑将设计任务分配给它们;②制定项目物流规划方案，确定项目所需的物料数量、种类，采购这些物料的时机，这些物料在各个存储单元之间的合理分布，选择何种运送路线等等;③制定实际制造任务分配方案，即按各个加盟企业的实力将项目(如果企业能够承担整个项目)或工件任务分配给它们;④对加盟企业项目或任务执行过程进行监控，包括质量控制，成本控制和进度控制。对加盟企业而言，要考虑的是如何将连锁总部分配的项目(如果是项目则先要对项目进行分解)或任务，与提供该项服务的某个具体网格单元(设计、制造、仓储、运输等)匹配，匹配所依据的信息主要是每个网格单元的能力和动态负荷。对网格单元而言，在承接了某项具体的网格需求后，其所要决策的是单元内部具体设备和人员的实时调配问题，即确定某项任务由哪个人/哪台设备何时开始、何时完成。具体到制造单元，它负责将上层加盟企业分发下来的生产订单(零部件生产计划)进行分解，并根据底层设备控制层的生产信息编制详细作业计划，将各作业在各加工资源上排序，并在生产执行过程中通过生产跟踪反馈的信息及时对计划进行调整。

2 模具网格制造单元生产调度

要根据模具生产的特点来界定模具网格制造单元生产调度问题的性质。首先，模具的每个零件包含多道工序，每道工序由不同种类的机器加工而成，因而模具制造单元生产调度属于多机问题。第二，模具生产是面向订单的，订单的获得具有很大的随机性，这意味着从上层加盟企业层分配到模具制造单元的生产订单(工件)是陆续不断的、不定时的，因而模具制造单元生产调度属于动态调度。第三，模具生产是单件生产，一般每种模具只生产一套，因此到达模具制造单元的工件其工艺路线一般不同，因而模具制造单元生产调度属于Job-Shop问题。另外，在对模具企业进行调研的过程中，我们发现，模具零件的工艺路线一般是由参加过该套模具设计的设计人员担任工艺计划员预先确定的，模具零件就依照这条工艺路线来加工，只在极个别的情况下，才会发生工艺路线的改变。故在本文中，拟按确定工艺路线来讨论模具制造单元生产调度问题。第四，在模具的加工过程中，突发事件多，且工件加工时间等参数不确定，故模具制造单元生产调度属于随机性问题。最后，模具生产的目标是要在保证模具质量和交货期的基础上，最大限度地降低生产成本，提高企业收益。故模具制造单元生产调度通常属于多目标决策问题。

总而言之，模具制造单元生产调度属于多机、多任务、有复杂约束、不同任务具有不同工艺路线、任务不断不定时输入输出的Jop-shop类随机调度，是生产调度问题中较复杂的一类，属于NP完全问题。它的基本任务是围绕模具零件的加工制造，解决并行加工的多个零件如何共享有限资源以最大限度地满足加工成本、交货期的问题。它不但要对零件的各道工序任务在各个资源上的加工顺序和时间进行安排，而且要监控制造单元生产中出现的意外情况(包括上层加盟企业下达的生产订单信息的改变和下层设备控制层反馈的异常信息)对原先做好的工序任务安排进行实时的再调整，是一个持续更新、动态变化的过程。

3 基于优先规则的启发式调度算法

与其它算法相比，启发式算法具有以下优点［4］:①收敛速度快，能在较短的时间内得到让人满意的解;②算法编程简单，易于实现且容易修改;③不需要建立问题的数学模型;④是针对求解的某类具体问题设计的，依赖于问题的具体特征，利用了专门的知识和经验，只要设计得当就可能得到特定问题的较优解。基于此，本文针对模具制造单元生产调度问题设计了一种基于优先规则的可进行并行作业调度的启发式算法［5］，现用类C语言来描述该启发式算法:

4 算法验证与分析

设某模具制造单元的机器情况如表1:

表1 模具制造单元机器设备

现有6个工件同一周期排产，它们的工艺路线、工序加工时间、工序加工成本、交货期如表2(注:表中C(5，10)(7，8)表示某道工序要用CNC机床加工，用C1加工的时间是5、成本是10，用C2加工的时间是7，成本是8):

表2 工艺计划

根据上述算法获得生产计划的甘特图如图2所示。

图2 甘特图

J1、J2、J3、J4、J5、J6 的完工时间分别是 16、25、28、37、19、23，即只有J4有少量误工。工件加工的总成本为(10+4+6)+(4+6+3+6)+(5+6+9+6)+(8+5+5+6+6)+(6+5+5)+(2+6+7+7+4)=137，加工成本应当在119和154之间变动。

工件的加工情况和机器的利用情况如表3、表4所示。

表3 工件加工情况

表4 机器利用率

经过多次变换单元内各类机器的数目和工件加工路线，仍然用该算法来进行作业排序，仿真结果都证明该种启发式算法基本能够满足误工工件数量少、兼顾加工成本尽可能小的原则，并且该种算法具有一定的收敛速度。在此不一一列出。

5 结束语与创新点

实际上，单纯从算法的角度来看，对本文所探讨的制造单元生产调度问题的给定实例，该种启发式调度算法只包含对工件和机器的有限搜索、排序及不等式判断，其时间复杂度应是实例大小的多项式，可以快速对问题求解。同时，由于该算法在每个均分时段的起始时刻搜索在某类机器上等待排产的工件的工序任务及其个数、某类机器的可用机床个数，因此该算法可实现对实际生产过程中上层加盟企业和下层设备异常情况的及时反应并对生产计划作出及时调整，能够满足特许连锁网格制造单元的生产调度需求。

本文创新点:①本文的调度算法是针对特许连锁经营模式下的模具网格制造单元制定的;②该调度算法是一种新的行之有效的基于规则的启发式算法。

［1］陈庆新，田文生，陈新，等.特许连锁模式下的模具制造网格系统架构［J］.计算机集成制造系统，2003，9(7):595-600.

［2］陈娟，陈庆新，陈新.特许连锁经营模式下的模具制造系统建模［J］.制造业自动化，2004(增刊):58-66.

［3］Foster I，Kesselman C，Nick J et al.The Physiology of the Grid:An Open Grid Services Architecture for Distributed Systems Open Grid Service Infrastructure.Global Grid Forum，2002.

［4］刑文训，谢金星.现代优化计算方法［M］.北京:清华大学出版社，1999.

［5］毛宁，刘霞，林洁瑜.关于M类机器的非流水复杂作业排序问题的一种启发式算法［J］.工程数学学报，1996，6(13):65-73.