基于动态优先级的离散车间调度系统开发

□吕伟

上海电气集团股份有限公司 中央研究院　上海　200070

基于动态优先级的离散车间调度系统开发

□吕伟

上海电气集团股份有限公司 中央研究院上海200070

通过分析某离散车间加工情况和调度人员经验，为不同加工工序定义不同类别的优先级，建立动态优先级模型。在此基础上，开发了一套离散车间调度系统，建立了动态调用优先级模型，在考虑资源约束的情况下，生成了有效的排程方案。

随着市场竞争加剧，原材料价格与人力成本不断提高，制造业面临着提高生产效益、降低生产成本以应对行业竞争的挑战。在现代制造企业中，面对不同的客户需求进行定制化生产，这对生产加工的灵活性要求很高。车间调度在生产计划的实施中占据关键地位，良好的车间调度可以使资源得到优化配置，能大大提高企业的经济效益。

离散型制造企业的生产过程复杂，生产计划制定困难。产品加工过程中，不同的产品会经过不同的加工车间，同一加工车间内对不同设备的需求也不同，这些差异经常导致工作流的不平衡。离散型车间的产品加工周期一般较长，工作流的不平衡致使有些加工任务在工作中心的排队时间较长，导致加工时间的延迟和在制品的堆积。传统的生产组织方式无法对资源进行动态调整，很难满足客户需求。

调度能够有效地解决业务竞争导致的工作流不平衡，是解决资源共享的有效手段［1］。关于动态优先级调度算法，美国宇航局研究员C.L.Liu和J.W. Layland［2］最早提出了用于固定优先级任务调度的速率单调任务调度算法。J.Y.T Leung和J.Whitehead等［3，4］提出了最小空闲时间优先（Least Slack Time First，LSF）算法，该算法把作业剩余空闲时间作为优先级评判标准，保证最紧迫的任务优先执行，主要应用于分布式网络、多媒体等领域。最早截止期优先算法也是一种动态优先级任务调度算法，该算法根据任务截止期来决定任务执行顺序，其应用范围包括工业网络、多媒体传输、军事装备等众多领域［5］。

笔者研究的对象是某离散加工车间，主要生产方式是按订单生产，研究目的是针对生产现场存在的诸多问题，按照原材料的到料状况、机械设备的使用状况、生产能力等因素进行综合考虑，制定出合理的生产排程计划，使原材料到位后生产能力及生产周期能满足客户的出货需求，同时保证机器设备不冲突，人员工作时间安排均衡饱满。

1　动态优先级模型

1.1模型假设

该离散车间是一个由50台加工系统组成的机加工车间，每台设备有对应的操作人员，加工对象由14个零部件组成，零部件具有一定的装配关系和加工顺序约束，每个零部件包含若干道工序，且流程固定，50台加工系统中包含车床组、铣床组、刨床组、钳床组、磨床组、焊接组，各组设备的加工能力一致。车间调度员通过最佳的调度，为各工序选配最佳资源，在满足设备加工能力及人员匹配的情况下，获得最佳的排程方案。

动态优先级模型假设：①任何设备无法同时加工超过两个工序；②任意工件无法同时在多台设备上加工；③工件必须严格按照工艺路线在指定机器上加工；④除特定工序指定工人外，忽略工人的熟练程度；⑤工件的安装及拆卸时间已经包含在该工序的加工工时中；⑥一般情况下，有设备就有工人，除特殊情况外，工人处于充足状态；⑦每个订单的14种原材料到位时间随机，遵循板材、管材、棒材的到位顺序。

1.2优先级指标定义

在调度问题中，最重要的是遇到多个任务可以同时在相同的设备上加工时，如何判定哪个任务先安排生产。本模型就是结合现场排程人员的历史经验，为现有加工过程定义不同类别的优先级，在生产过程中，动态计算待加工工序的优先级指标，按优先级顺序组织生产。

该模型的研究重点就是根据排程人员的经验，提出具体的规则，进而定义不同类别的优先级。通过现场实地调研，本类问题在实际排程中可分为以下五种层次。

（1）项目优先级X。项目优先级预设值为a1，将不同项目按照重要性排序，由此分配项目重要性因子α（重要性越高，α越大），X=α×a1。

（2）零件优先级Y。零件优先级预设值为a2，根据零件装配关系和加工顺序的约束，结合排程人员历史经验，将14个零件按重要性排序，由此分配零件重要性因子β（重要性越高，β越大），Y=β×a2。

（3）工序衔接优先级Z。工序衔接优先级预设值为a3，如某工序需要在某设备C上进行加工，C的上一个任务为相同零件的相同工序，那么该工序在该设备上的工序衔接优先级为Z=a3。

（4）工序优先级M。工序优先级的基础值设置为a4，如零件i共有k道工序，那么零件i的j道工序的工序优先级为M=（j/k）×a4。

（5）时长优先级N。时长优先级的基础值设置为a5，如某零件某工序需要加工时间m（单位为min），一套组件由n个零件组成，（m×n）max为所有零件工序中总加工时长的最大值，那么该道工序的时长优先级为

1.3模型建立

根据定义的优先级指标，系统在进行调度安排时会动态计算待加工工序的优先级，按照优先级排序，将各工序依照BOM表安排到当前空闲的加工设备上。在计算优先级时，根据不同情况优先级的比较规律，系统形成了比较通用的优先级比较方法，主要在三个层面进行比较：

根据以上定义，结合排程员的经验，得到如图1所示判定任务选择的动态优先级模型。

2　调度系统软件设计

2.1业务流程分析

车间现场调度的情况非常复杂，现场的排程条件是随时变化的，系统需要综合考虑项目安排、工艺、人员、设备、原材料等基础资源的可用情况，还要对设备宕机、新原材料到达、插单等特殊工况给出快速反应，生成合理的排程方案，图2给出了生产调度的主要流程，车间的作业流程划分为：现场加工、排程计划、监控三个部分，整个车间的作业以排程方案来驱动，通过调用动态优先级算法模型，制定可执行的、高效的排程方案。

为了有效执行计划，不能将排程计划直接下达，而需要依赖派工单将命令传达到各生产工位。根据动态优先级算法模型得出的排程方案，按零件划分生成派工单，下达零件加工的设备、人员、时间安排，派工单随零件在各工位流转，在指导生产过程的同时，也可以实现对生产过程的监控，反馈计划的执行情况，为下一期生产计划的编制提供参考。

图1　动态优先级模型

图2　生产调度主要流程

2.2调度系统模块划分

根据生产调度的工作流程可知，调度系统软件需实现的功能为：根据基础信息的设定，调用动态优先级模型，生成排产计划，根据排产计划得到派工单，用于车间指导生产，收集计划执行的数据，用于管理者了解生产计划的执行情况，以及设备的运行状况。同时为确保安全性，系统对用户的账户和权限要统一管理。根据以上分析，建立调度系统软件的4个功能模块：系统用户管理、基础信息维护、生产排程管理、信息查询模块，具体功能如图3所示。

整个调度系统的核心部分是动态优先级模型，模型的实现依赖于生产排程管理模块的功能。生产排程管理模块可以根据现场原材料到位情况和机器、人员、设备的可用情况，调用动态优先级模型，动态地计算待加工工序的优先级，按照优先级排序，对各工序安排机器和人员执行加工任务，将结果以甘特图（甘特图：基于作业排序的目的，以图示的方式通过活动列表和时间刻度形象地表示出任何特定项目的活动顺序与持续时间）的形式显示到界面中，并根据结果生成派工单，以便于将生产命令下达到各个工位上。

2.3与相关系统的信息交互

调度系统通过建立一套计算机软件系统，通过一些固化的排程规则，平衡有限生产能力和物料需求，最大限度消除或减少人为因素对生产的干预，帮助离散制造企业建立精准、详尽的生产计划。作为一套排程工具，生成的排程方案需要依靠现场的MES系统执行，生成排程方案的基础信息来自于ERP系统，系统之间存在密切的交互，如图4所示。ERP向调度系统下发订单信息、原料信息、生产配料信息、设备信息和标准工艺路线。调度系统根据下发的信息，制定排程方案，生成派工单下达至MES系统执行。同时，MES系统采集到的加工进度和设备状态数据会实时反馈到调度系统，用于生成下一时刻的排程方案。

图3　系统软件模块划分

图4　系统信息交互

3　系统实现

调度系统选用的客户端操作系统为Windows 7，服务器端操作系统为Windows Server 2008，数据库软件为 SQL Server 2008，系统开发工具为VB.NET。动态优先级算法部分由MATLAB2011编写，打包生成.dll文件由VB程序直接调用。

4　结束语

本课题通过对某离散加工车间的实地调研，从企业需求分析入手，开发了针对按订单生产、多品种小批量的离散型制造条件下的生产调度系统。通过分析现场存在的诸多约束条件和排程人员的经验，形成动态优先级模型，利用该模型充分调用资源，找到最佳排程方案，大大提高了生产车间的效率和稳定性。

［1］张登银，许扬扬，蒋娟.基于时延的动态优先级调度算法［J］.计算机技术与发展，2011，21（2）：162-165.

［2］LIUCL，LAYLANDJW.SchedulingAlgorithmsforMultiprog ramming in a Hard-Real-Time Environment［J］.Journal of the Association for Computing Machinery，1973，20（1）：46-61.

［3］LEUNGJ YT，WHITEHEADJ.On the ComplexityofFixedprioritySchedulingofPeriodicReal-timeTasks［J］. Performance Evaluation，1982，2（4）：237-250.

［4］夏家莉，陈辉，杨兵.一种动态优先级实时任务调度算法［J］.计算机学报，2012，35（12）：2685-2695.

［5］NARLIKAR G，WILFONG G，ZHANG L.Designing Multihop Wireless Backhaul Networks with Delay Guarantees［J］. Wireless Networks，2010，16（1）：237-254.

By analyzing the case of a discrete processing workshop and the experience of dispatchers，varied levels of priorities are defined against different working operations for establishment of dynamic priority model. On this basis，we developed a set of discrete workshop scheduling system that can enable dynamic calling of the priority model togenerate an efficient scheduling scheme in consideration of resource constraints.

动态优先级模型；排程方案；调度系统

Dynamic Priority Model；Scheduling Scheme；Scheduling System

TP 311.1

B

1672-0555（2016）01-033-04

2015年9月

吕伟（1989—），女，硕士，研发工程师，主要研究方向：智能制造系统