歐陽浩 黃鎮(zhèn)謹 戎陸慶 陳 波

(1.廣西科技大學計算機學院，廣西柳州545006;2.廣西科技大學管理學院，廣西柳州545006)

工礦企業(yè)中各生產礦井調度室和礦務局調度室之間有專門的通信線路連接，這為工礦企業(yè)中各工序的生產調度提供了硬件基礎。在生產過程中如何協(xié)調各生產環(huán)節(jié)等生產管理問題成為當今各工礦企業(yè)需著重解決的問題之一，它關系到各工礦企業(yè)的安全性生產和高效的生管理模式［1-2］。

生產調度問題是運籌學中的經典問題。過去的幾十年中，人們對它進行了大量的研究并解決了一系列有代表意義的調度和優(yōu)化問題［3-9］。以往的解決方案都是設計單一的調度方案，而在實際的生產流程中，由于資源、設備或空間的有限性，一些任務需要等候服務節(jié)點的處理，這類環(huán)節(jié)構成了具有排隊行為的隨機服務系統(tǒng)［10］，如產品的出入庫調配、加工中心對各類加工件的加工過程、維修人員的調配等。在這些環(huán)節(jié)中由于服務節(jié)點的服務能力不同，服務成本也不一樣，到達系統(tǒng)的任務類型也不完全相同。因此，必須根據(jù)任務和服務節(jié)點的特征，進行合理的調配，以減少整個隨機服務系統(tǒng)的成本開銷。特對這類具有隨機服務行為的生產環(huán)節(jié)進行了研究，提出合理的任務調度方法。

1 任務和系統(tǒng)模型

生產流程的各類隨機服務環(huán)節(jié)中，由于生產環(huán)境、設備狀態(tài)、人員狀況的不確定性，各個任務到達系統(tǒng)的時間是隨機的。其時間間隔可能服從均勻分布、指數(shù)分布、Erlang分布等。出于分析的需要，下面給出任務和服務節(jié)點的形式化定義。

定義1:到達系統(tǒng)的任務可由四元組 (T，γ，C，W)表示，其中ti∈T表示第i類任務，λi∈γ表示第ti類任務單位時間內的平均到達數(shù)量，ci表示完成任務ti所需要付出的成本，wi表示ti類任務在等待隊列中等待單位時間所需的成本。

定義2:提供服務的服務節(jié)點可由三元組(S，S ，S )表示，其中

表示服務節(jié)點集合，si表示第i類服務節(jié)點;

表示服務節(jié)點空閑時的單位時間的成本;

任務的到達率可以采用對隨機服務系統(tǒng)的大量監(jiān)測數(shù)據(jù)進行分析，然后利用統(tǒng)計分析的方法確定出其屬于哪種理論分布，并估計參數(shù)值。各類成本可以利用經驗數(shù)據(jù)，采用統(tǒng)計學的方法計算而得。

定義3:隨機服務系統(tǒng)可表示為三元組(T，μm×n，S)，其中 T、S分別表示任務和服務節(jié)點，μm×n表示服務節(jié)點服務時間矩陣，uij表示服務節(jié)點si對任務ti的平均服務時間。

系統(tǒng)的流程可以這樣描述:各個任務按照一定的分布到達服務系統(tǒng)，調度人員或調度單元根據(jù)任務類型，服務節(jié)點當前的執(zhí)行情況計算任務分派給各服務節(jié)點所產生的成本，并根據(jù)成本的大小最終決定把任務分派到相應的服務節(jié)點隊列中。為方便起見，對每一個服務節(jié)點，本研究僅考慮其符合M/M/1隊列模型的情況，即到達的任務流服從泊松分布，服務時間服從負指數(shù)的排隊系統(tǒng)模型。系統(tǒng)的模型如圖1所示。

圖1 系統(tǒng)模型Fig.1 System model

2 系統(tǒng)成本及調度方法

2.1 系統(tǒng)成本計算

設pij為將ti類任務分派到sj服務節(jié)點的概率，由前定義，根據(jù)排隊論知識，服務節(jié)點sj對ti類任務的服務強度為

考慮調度概率pij，服務節(jié)點sj的期望服務強度為

對于服務節(jié)點sj，由于服務的任務不相同，因此需要計算其對n類任務的期望成本。由任務的定義可知，ti類任務的到達率為λi，因此對于服務節(jié)點sj，其期望到達率為

sj對m類任務的期望成本為

因此，sj的總成本為

所有的服務器總成本為

服務節(jié)點sj等候隊列中ti類任務的平均任務數(shù)為

其平均等待時間

服務節(jié)點等待成本sj的等待成本為

總等待成本

因此系統(tǒng)的總成本為

可知，對于給定系統(tǒng)，其服務節(jié)點和任務一般是固定的，因此除了調度概率pij，其他變量都可以通過測量和概率分析而得。

2.2 調度方法

由前面的分析可知，對于給定的系統(tǒng)，系統(tǒng)的總成本隨著調度概率的不同而動態(tài)變化，因此調度的目的就是確定調度概率矩陣

使得總成本C最小。從成本公式可以看出，影響成本的因素主要包括任務在服務節(jié)點上的執(zhí)行成本、服務節(jié)點的空閑成本、任務的等待成本，而且，對于特定的隨機服務系統(tǒng)，還要考慮服務節(jié)點的啟動或者關閉成本。因此，在確定調度概率時，必須將這些因素考慮進去，進行適當?shù)恼{配，以期望獲得的總成本最小。具體的調配方法如下:當有ti類任務到達時，首先計算該任務與服務節(jié)點的匹配因子，根據(jù)匹配因子的大小計算調度概率因子，選擇調度概率大的服務節(jié)點為該任務服務。匹配因子由下面公式確定:

由定義可知，

即當ti類任務到達時，其調度到各個服務節(jié)點的概率和為1。

從匹配因子可知，當一個任務到達時，空閑成本越高的服務節(jié)點，其調度概率越高，而執(zhí)行成本越高的服務節(jié)點，調度概率越低。對于某一類任務來說，該類任務在某服務節(jié)點的服務強度越高，則該類任務被調度的概率就越大，因為該服務節(jié)點對該類任務具有更高的服務效率;等待成本則兼顧了服務節(jié)點的負載平衡，服務節(jié)點的等待隊列越長，則等待成本越高，對應地，把任務分配給該服務節(jié)點的可能性越低;在一些特定的隨機服務系統(tǒng)中，比如加工系統(tǒng)、物流系統(tǒng)中，服務節(jié)點在啟動和關閉時又可能會產生比較大的成本開銷，因此在這種情況下，在進行任務調度時需將啟動成本和關閉成本考慮在內。當服務節(jié)點隊列沒有任務時，分配給該單元任務就要產生啟動成本，當服務節(jié)點隊列中只剩1個任務時，則在計算匹配因子時需要把關閉成本考慮在內。

定義好匹配因子后，各個權值反映了各個量的重要程度，在不同的情況下，可以通過調整權值的大小來決定任務的調度策略。當要降低某服務節(jié)點的空閑成本時，可采用把在該服務節(jié)點有大服務強度的任務優(yōu)先分派到該服務節(jié)點上實現(xiàn)。當要降低系統(tǒng)的執(zhí)行成本時，可考慮將在該服務節(jié)點具有較小執(zhí)行成本的任務優(yōu)先分派到該服務節(jié)點。為了降低總的等待成本，則可考慮優(yōu)先將任務分派到等待隊列長度較短的服務節(jié)點。

3 仿真分析

為了進一步說明以上調度策略的有效性和優(yōu)劣，本研究利用Matlab的SimEvents工具箱進行了仿真分析，并將其與其他調度方式進行了比較，其結果如圖2所示。

圖2 調度策略與總成本關系Fig.2 Scheduling policy and total cost■—Sto_choice;▲—Min_busy;◆—Min_total

圖2 中，橫坐標為到達的任務數(shù)，縱坐標為總成本，隨機服務系統(tǒng)符合排隊模型。Sto_choice為隨機分派方式，即將每一個到達的任務隨機的分派給服務節(jié)點，Min_busy為基于最小執(zhí)行成本的調度策略，即將分派到具有最小 的服務節(jié)點。Min_total采用的是本文所描述的調度策略。從結果看，對于隨機服務系統(tǒng)來說，考慮了各項因素的Min_total策略具有較小的總成本。

3 結語

生產調度是工礦企業(yè)生產管理中一個很重要的問題，但其分析過程復雜。針對具有排隊性質的生產流程，本研究提出了一種以總成本為優(yōu)化目的，以調度概率為準則的排隊模型的調度方法。通過分析和仿真結果表明，該調度方法能夠降低此類生產流程的總成本。

［1］ 徐俊剛，戴國忠，王宏安.生產調度理論和方法研究綜述［J］.計算機研究與發(fā)展，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］ 李 芳，單大亞，馬 婷.基于多智能體的虛擬企業(yè)群協(xié)同生產調度模式研究［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］ 區(qū)偉明，胡奇英.CIMS物流調度系統(tǒng)的建模與仿真［J］.計算機集成制造系統(tǒng)，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的煤炭生產調度系統(tǒng)研究［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］ 孫 偉，王宜雷，王 慧，等.蟻群算法在選煤廠產品結構優(yōu)化中的應用［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.