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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

sj對m類任務(wù)的期望成本為

因此，sj的總成本為

所有的服務(wù)器總成本為

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

其平均等待時間

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

總等待成本

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

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

2.2 調(diào)度方法

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

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

由定義可知，

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

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

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

3 仿真分析

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

圖2 調(diào)度策略與總成本關(guān)系Fig.2 Scheduling policy and total cost■—Sto_choice;▲—Min_busy;◆—Min_total

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

3 結(jié)語

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

［1］ 徐俊剛，戴國忠，王宏安.生產(chǎn)調(diào)度理論和方法研究綜述［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é)同生產(chǎn)調(diào)度模式研究［J］.計算機應(yīng)用研究，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物流調(diào)度系統(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］ 周艷平.基于博弈理論的多目標生產(chǎn)調(diào)度問題研究［D］.上海:華東理工大學(xué)，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］ 盧曉紅，賈振元，劉弟新.基于排隊論的吊車精益生產(chǎn)調(diào)度研究［J］. 計算機工程與應(yīng)用，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］ 唐應(yīng)輝，唐小我.排隊論:基礎(chǔ)與分析技術(shù)［M］.北京:科學(xué)出版社，2006.Tang Yinghui，Tang Xiaowo.Queuing Theory-Base and Analytic Technique［M］.Beijing:Science Press，2006.

［9］ 付琳燕，華 鋼.基于MapX的煤炭生產(chǎn)調(diào)度系統(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］ 孫 偉，王宜雷，王 慧，等.蟻群算法在選煤廠產(chǎn)品結(jié)構(gòu)優(yōu)化中的應(yīng)用［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.