基于排隊(duì)模型的工礦企業(yè)生產(chǎn)調(diào)度研究

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

(1.廣西科技大學(xué)計(jì)算機(jī)學(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)管理問題成為當(dāng)今各工礦企業(yè)需著重解決的問題之一，它關(guān)系到各工礦企業(yè)的安全性生產(chǎn)和高效的生管理模式［1-2］。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

因此，sj的總成本為

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

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

其平均等待時(shí)間

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

總等待成本

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

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

2.2 調(diào)度方法

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

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

由定義可知，

即當(dāng)ti類任務(wù)到達(dá)時(shí)，其調(diào)度到各個(gè)服務(wù)節(jié)點(diǎn)的概率和為1。

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

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

3 仿真分析

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

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

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

3 結(jié)語

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

［1］ 徐俊剛，戴國忠，王宏安.生產(chǎn)調(diào)度理論和方法研究綜述［J］.計(jì)算機(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］.計(jì)算機(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］.計(jì)算機(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］ 周艷平.基于博弈理論的多目標(biāo)生產(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］ 盧曉紅，賈振元，劉弟新.基于排隊(duì)論的吊車精益生產(chǎn)調(diào)度研究［J］. 計(jì)算機(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)輝，唐小我.排隊(duì)論:基礎(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］.工礦自動(dòng)化，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］.工礦自動(dòng)化，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.