基于排队模型的工矿企业生产调度研究

欧阳浩 黄镇谨 戎陆庆 陈 波

(1.广西科技大学计算机学院，广西柳州545006;2.广西科技大学管理学院，广西柳州545006)

工矿企业中各生产矿井调度室和矿务局调度室之间有专门的通信线路连接，这为工矿企业中各工序的生产调度提供了硬件基础。在生产过程中如何协调各生产环节等生产管理问题成为当今各工矿企业需着重解决的问题之一，它关系到各工矿企业的安全性生产和高效的生管理模式［1-2］。

生产调度问题是运筹学中的经典问题。过去的几十年中，人们对它进行了大量的研究并解决了一系列有代表意义的调度和优化问题［3-9］。以往的解决方案都是设计单一的调度方案，而在实际的生产流程中，由于资源、设备或空间的有限性，一些任务需要等候服务节点的处理，这类环节构成了具有排队行为的随机服务系统［10］，如产品的出入库调配、加工中心对各类加工件的加工过程、维修人员的调配等。在这些环节中由于服务节点的服务能力不同，服务成本也不一样，到达系统的任务类型也不完全相同。因此，必须根据任务和服务节点的特征，进行合理的调配，以减少整个随机服务系统的成本开销。特对这类具有随机服务行为的生产环节进行了研究，提出合理的任务调度方法。

1 任务和系统模型

生产流程的各类随机服务环节中，由于生产环境、设备状态、人员状况的不确定性，各个任务到达系统的时间是随机的。其时间间隔可能服从均匀分布、指数分布、Erlang分布等。出于分析的需要，下面给出任务和服务节点的形式化定义。

定义1:到达系统的任务可由四元组 (T，γ，C，W)表示，其中ti∈T表示第i类任务，λi∈γ表示第ti类任务单位时间内的平均到达数量，ci表示完成任务ti所需要付出的成本，wi表示ti类任务在等待队列中等待单位时间所需的成本。

定义2:提供服务的服务节点可由三元组(S，S ，S )表示，其中

表示服务节点集合，si表示第i类服务节点;

表示服务节点空闲时的单位时间的成本;

任务的到达率可以采用对随机服务系统的大量监测数据进行分析，然后利用统计分析的方法确定出其属于哪种理论分布，并估计参数值。各类成本可以利用经验数据，采用统计学的方法计算而得。

定义3:随机服务系统可表示为三元组(T，μm×n，S)，其中 T、S分别表示任务和服务节点，μm×n表示服务节点服务时间矩阵，uij表示服务节点si对任务ti的平均服务时间。

系统的流程可以这样描述:各个任务按照一定的分布到达服务系统，调度人员或调度单元根据任务类型，服务节点当前的执行情况计算任务分派给各服务节点所产生的成本，并根据成本的大小最终决定把任务分派到相应的服务节点队列中。为方便起见，对每一个服务节点，本研究仅考虑其符合M/M/1队列模型的情况，即到达的任务流服从泊松分布，服务时间服从负指数的排队系统模型。系统的模型如图1所示。

图1 系统模型Fig.1 System model

2 系统成本及调度方法

2.1 系统成本计算

设pij为将ti类任务分派到sj服务节点的概率，由前定义，根据排队论知识，服务节点sj对ti类任务的服务强度为

考虑调度概率pij，服务节点sj的期望服务强度为

对于服务节点sj，由于服务的任务不相同，因此需要计算其对n类任务的期望成本。由任务的定义可知，ti类任务的到达率为λi，因此对于服务节点sj，其期望到达率为

sj对m类任务的期望成本为

因此，sj的总成本为

所有的服务器总成本为

服务节点sj等候队列中ti类任务的平均任务数为

其平均等待时间

服务节点等待成本sj的等待成本为

总等待成本

因此系统的总成本为

可知，对于给定系统，其服务节点和任务一般是固定的，因此除了调度概率pij，其他变量都可以通过测量和概率分析而得。

2.2 调度方法

由前面的分析可知，对于给定的系统，系统的总成本随着调度概率的不同而动态变化，因此调度的目的就是确定调度概率矩阵

使得总成本C最小。从成本公式可以看出，影响成本的因素主要包括任务在服务节点上的执行成本、服务节点的空闲成本、任务的等待成本，而且，对于特定的随机服务系统，还要考虑服务节点的启动或者关闭成本。因此，在确定调度概率时，必须将这些因素考虑进去，进行适当的调配，以期望获得的总成本最小。具体的调配方法如下:当有ti类任务到达时，首先计算该任务与服务节点的匹配因子，根据匹配因子的大小计算调度概率因子，选择调度概率大的服务节点为该任务服务。匹配因子由下面公式确定:

由定义可知，

即当ti类任务到达时，其调度到各个服务节点的概率和为1。

从匹配因子可知，当一个任务到达时，空闲成本越高的服务节点，其调度概率越高，而执行成本越高的服务节点，调度概率越低。对于某一类任务来说，该类任务在某服务节点的服务强度越高，则该类任务被调度的概率就越大，因为该服务节点对该类任务具有更高的服务效率;等待成本则兼顾了服务节点的负载平衡，服务节点的等待队列越长，则等待成本越高，对应地，把任务分配给该服务节点的可能性越低;在一些特定的随机服务系统中，比如加工系统、物流系统中，服务节点在启动和关闭时又可能会产生比较大的成本开销，因此在这种情况下，在进行任务调度时需将启动成本和关闭成本考虑在内。当服务节点队列没有任务时，分配给该单元任务就要产生启动成本，当服务节点队列中只剩1个任务时，则在计算匹配因子时需要把关闭成本考虑在内。

定义好匹配因子后，各个权值反映了各个量的重要程度，在不同的情况下，可以通过调整权值的大小来决定任务的调度策略。当要降低某服务节点的空闲成本时，可采用把在该服务节点有大服务强度的任务优先分派到该服务节点上实现。当要降低系统的执行成本时，可考虑将在该服务节点具有较小执行成本的任务优先分派到该服务节点。为了降低总的等待成本，则可考虑优先将任务分派到等待队列长度较短的服务节点。

3 仿真分析

为了进一步说明以上调度策略的有效性和优劣，本研究利用Matlab的SimEvents工具箱进行了仿真分析，并将其与其他调度方式进行了比较，其结果如图2所示。

图2 调度策略与总成本关系Fig.2 Scheduling policy and total cost■—Sto_choice;▲—Min_busy;◆—Min_total

图2 中，横坐标为到达的任务数，纵坐标为总成本，随机服务系统符合排队模型。Sto_choice为随机分派方式，即将每一个到达的任务随机的分派给服务节点，Min_busy为基于最小执行成本的调度策略，即将分派到具有最小 的服务节点。Min_total采用的是本文所描述的调度策略。从结果看，对于随机服务系统来说，考虑了各项因素的Min_total策略具有较小的总成本。

3 结语

生产调度是工矿企业生产管理中一个很重要的问题，但其分析过程复杂。针对具有排队性质的生产流程，本研究提出了一种以总成本为优化目的，以调度概率为准则的排队模型的调度方法。通过分析和仿真结果表明，该调度方法能够降低此类生产流程的总成本。

［1］ 徐俊刚，戴国忠，王宏安.生产调度理论和方法研究综述［J］.计算机研究与发展，2004，41(2):257-267.Xu Jungang，Dai Guozhong，Wang Hongan.An Overview of Theories and Methods of Production Scheduling［J］.Journal of Computer Research and Development，2004，41(2):257-267.

［2］ 李 芳，单大亚，马 婷.基于多智能体的虚拟企业群协同生产调度模式研究［J］.计算机应用研究，2013，30(6):1624-1629.Li Fang，Shan Daya，Ma Ting.Model of collaborative production scheduling in virtual enterprise cluster based on multi-agent systems［J］.Application Research of Computers，2013，30(6):1624-1629.

［3］ 区伟明，胡奇英.CIMS物流调度系统的建模与仿真［J］.计算机集成制造系统，2004，10(9):1067-1072.Qu Weiming，Hu Qiying.Modeling and simulation of logistics dispatch system in CIMS［J］.Computer Integrated Manufacturing Systems，2004，10(9):1067-1072.

［4］ 周艳平.基于博弈理论的多目标生产调度问题研究［D］.上海:华东理工大学，2013.Zhou Yanping.Research of Multi-objective Production Scheduling Problem Based on Game Theory［D］.Shanghai:East China University Of Science，2013.

［5］ Ruben R，Jose A，Vazquez R.The hybrid flow shop scheduling problem［J］.European Journal of Operational Research，2010，205(1):1-18.

［6］ Brucker P.Scheduling Algorithm［M］:Fifth Edition.Heidelberg:Springer-Verlag，2007.

［7］ 卢晓红，贾振元，刘弟新.基于排队论的吊车精益生产调度研究［J］. 计算机工程与应用，2007，43(26):223-226.Lu Xiaohong，Jia Zhenyuan，Liu Dixin.Research on scheduling problem in lean production for crane service system based on queue theory［J］.Computer Engineering and Applications，2007，43(26):223-226.

［8］ 唐应辉，唐小我.排队论:基础与分析技术［M］.北京:科学出版社，2006.Tang Yinghui，Tang Xiaowo.Queuing Theory-Base and Analytic Technique［M］.Beijing:Science Press，2006.

［9］ 付琳燕，华 钢.基于MapX的煤炭生产调度系统研究［J］.工矿自动化，2006(5):75-78.Fu Linyan，Hua Gang.The research of production and dispatching system of coal mine based on mapX［J］.Industry and Mine Automation，2006(5):75-78.

［10］ 孙 伟，王宜雷，王 慧，等.蚁群算法在选煤厂产品结构优化中的应用［J］.工矿自动化，2012(5):52-54.Sun Wei，Wang Yilei，Wang Hui，et al.Application of ant colony algorithm in product structure optimization of coal preparation plant［J］.Industry and Mine Automation，2012(5):52-54.