楊雨露，任曉青，邱 婉，包振強(qiáng)，王偉業(yè)

（揚(yáng)州大學(xué) 信息工程學(xué)院，揚(yáng)州 225127）

0 引言

傳統(tǒng)遞階結(jié)構(gòu)的制造資源計劃（MRP）分解方法將計劃與調(diào)度分為兩個階段，在確定零件各生產(chǎn)周期的生產(chǎn)批量時，由于沒有考慮具體的調(diào)度約束，計劃與調(diào)度不能夠有效的銜接，通常導(dǎo)致制定的計劃在調(diào)度中不可行[1]，影響了調(diào)度的動態(tài)適應(yīng)性和決策的有效性[2]。目前，對于將計劃與調(diào)度兩者集成的問題，國內(nèi)外不少學(xué)者已經(jīng)有了較為深入的研究，然而其中大部分文獻(xiàn)重在解決單資源單目標(biāo)車間調(diào)度問題[3～7]，即以生產(chǎn)周期為優(yōu)化目標(biāo)，以加工設(shè)備為資源約束，且工藝路線固定的車間調(diào)度問題。但是，實(shí)際作業(yè)車間中，工件通常有多條不同的加工路線，當(dāng)車間自身加工能力不足時，不管怎樣調(diào)度都不能在規(guī)定工期內(nèi)完成相應(yīng)的計劃，必須采取外包的方式。也就是說工件的調(diào)度除了受加工設(shè)備這一種資源約束外，還受其自身加工能力以及合作伙伴的約束[8]。針對以上問題，本文建立了一個基于工序成本的集成協(xié)作計劃與調(diào)度模型，既能確定最佳的工藝路線，又能確定工序的成本和總成本。并用改進(jìn)的遺傳算法求解該模型，給出了成本最低的最佳調(diào)度，在保證計劃完成的前提下實(shí)現(xiàn)了調(diào)度的同步。

1 基于工序成本的集成協(xié)作計劃與調(diào)度模型

本文所建模型為：作業(yè)車間有多種工件需要加工，同一種工件有多條不同的工藝加工路線可選，同一個工件不同的工序有嚴(yán)格的先后順序，并且作業(yè)車間自身的加工能力不足。要求制定一個能同時滿足一下要求的生產(chǎn)計劃：1）能為各個工件選擇合適的工藝加工路線；2）能在盡可能短的生產(chǎn)周期內(nèi)完成加工任務(wù)；3）能根據(jù)工序成本和外包所需的協(xié)作成本給出總成本最低的最佳調(diào)度集合。

本文所用符號與變量定義如下：定義H為很大的正數(shù)；N為待加工任務(wù)的個數(shù)；n為不可外包的工件數(shù)；TZ為工件的生產(chǎn)周期；Z為完工工期；Tihjk為工件i在選擇工藝加工路線為h后其工序j在第k臺設(shè)備上的完工時間；調(diào)度后的工件加工數(shù)量用P表示。此外，調(diào)度約束中的符號定義如下：若工件i選擇工藝加工路線為h后的工序j在工件p選擇工藝加工路線為q后的工序s前被加工，且k設(shè)備既能加工j也能加工p，則Yihjpqsk=1，否則Yihjpqsk=0；若工件i選擇工藝加工路線h，則Xih=1，否則Xih=0。

其中，當(dāng)工件i的工藝加工路線滿足式(1)和式(9)時，最后一道工序的完工時刻所對應(yīng)的調(diào)度目標(biāo)為Maximize P（Minimize Tz）；式(2)和式(3)表示對于工件i的兩個連續(xù)的工序，若在不同的設(shè)備上加工，則i的前一道工序必須在后一道工序前加工；式(4)表示在同一臺加工設(shè)備k上，選擇了第q條加工路線后的Ops（Ops表示工件p的第s道工序）比選擇了第h條加工路線后的Oij先加工完；式(5)表示的加工順序與式(4)相反，但二者同時保證了同一臺設(shè)備在同一時刻不能加工多道工序；式(7)和式(8)保證任一工件在選擇了一條工藝加工路線后都具備上述先后順序；式(9)表示只能從各工件的多道工藝加工路線中選擇一條；式(10)表示N個待加工任務(wù)中有n個無法外包給合作伙伴。

2 算法設(shè)計

本文通過對遺傳算法[9～11,14]進(jìn)行改進(jìn)來解決求解本文所建的基于工序成本的集成協(xié)作計劃與調(diào)度模型。采用的啟發(fā)式規(guī)則[12,13]是優(yōu)先選擇最短加工時間的工序（Shortest Processing Time first，SPT），它被證實(shí)是求解生產(chǎn)周期和平均流動時間的最佳規(guī)則。

2.1 染色體表現(xiàn)型

針對所建立的存在柔性路徑的模型，本文采用基于工序的染色體編碼方案。給相同工件的不同工序標(biāo)注同一符號，他們在染色體中的順序即為工序的順序，如表1所示。同時，由于考慮了協(xié)作，本文在設(shè)計染色體編碼時附加了一段基于工件編碼的協(xié)作染色體，如表2所示，用1表示外包，0表示自行加工。

染色體的初始種群為隨機(jī)產(chǎn)生。

表2 附加染色體編碼方式

2.2 選擇算子

本文采用賭輪機(jī)制優(yōu)先選擇適應(yīng)度值高的個體進(jìn)行遺傳操作。種群P 的規(guī)模為N，本文適應(yīng)度函數(shù)如式(12)：

其中Cmax表示種群中成本最大值，Cmin表示種群中成本最小值，C(Li)表示所求染色體對應(yīng)的成本。ε是為了避免適應(yīng)值為0而給的一個小小的補(bǔ)償。此外，若經(jīng)過調(diào)度排序后染色體的生產(chǎn)周期超出規(guī)定的生產(chǎn)周期，則規(guī)定其適應(yīng)值為一個很小的值。

2.3 交叉算子

程序運(yùn)行后得到一個新染色體c1，交換p1和p2再執(zhí)行一次以上程序得到另一個染色體c2。最后從這四條染色體中選擇適應(yīng)值大的兩個進(jìn)入下一步操作。

2.4 變異算子

本文的變異方法為隨機(jī)交換所選染色體中任意兩個基因位上的基因，如圖1所示。

表1 主染色體編碼方式

圖1 變異操作

3 算例及仿真

本文所設(shè)算法參數(shù)如下：種群規(guī)模N=50，迭代次數(shù)T=50。

本文的實(shí)驗(yàn)仿真數(shù)據(jù)如下：有6臺加工設(shè)備，9種工件，其中每個工件有3道不同的工序。表3的加工信息表給出了各零件在不同的可加工設(shè)備上的加工時間；表4的工件成本表給出了各零件的變動成本以及各自的協(xié)作成本；表5的工序成本表給出了各工序在不同的可加工設(shè)備上的加工成本。

表3 加工信息表

表4 工件成本表

表5 工序成本表

上述算例經(jīng)實(shí)驗(yàn)后得到一組解集，從中可知，自行加工的最小生產(chǎn)周期為35，也就是說，若交貨期大于35，則該車間可自行加工完成，但若交貨期小于35，無論怎么調(diào)度，都無法在規(guī)定時間內(nèi)完成任務(wù)，必須將部分工件外包給協(xié)作伙伴完成。圖2～圖4分別給出了完工周期為38，29和24所對應(yīng)的甘特圖。由圖可知：周期為38的調(diào)度任務(wù)全部自行完成；周期為29時，由于自身能力的約束不能完全自行加工，將工件4、5、9外包給了協(xié)作伙伴；周期為24時將工件1、3、4、9外包給了協(xié)作伙伴。由此可見，外包給協(xié)作伙伴的工件數(shù)量越多，則對應(yīng)的完工周期越短。但外包數(shù)量并不是越多越好，圖5（其中橫坐標(biāo)表示完工周期，縱坐標(biāo)表示對應(yīng)的總成本）給出了完工周期和總成本之間的關(guān)系，分析該圖我們可知完工周期越短，總成本越大。因此決策者必須根據(jù)個人偏好和實(shí)際情況來進(jìn)行決策，以便選出最適合的調(diào)度排序。

圖2 無協(xié)作甘特圖

圖3 有協(xié)作甘特圖（周期29）

圖4 有協(xié)作甘特圖（周期24）

4 結(jié)束語

本文提出了一個基于工序成本的集成協(xié)作計劃與調(diào)度模型，解決了傳統(tǒng)遞階結(jié)構(gòu)的制造資源計劃分解方法將計劃與調(diào)度分為兩個階段，使計劃與調(diào)度不能夠有效的銜接的問題。同時，有效地統(tǒng)一了計劃、調(diào)度、工藝路線決策與協(xié)作生產(chǎn)。該模型有效地解決了制造企業(yè)加工能力不足的問題，更好的實(shí)現(xiàn)了企業(yè)內(nèi)部生產(chǎn)調(diào)度的及時性和企業(yè)外部協(xié)作生產(chǎn)快速適應(yīng)性。

圖5 完工周期和總成本關(guān)系

[1]劉勝輝,王麗紅.求解車間作業(yè)調(diào)度問題的混合遺傳算法[J].計算機(jī)工程與應(yīng)用,2008,44(29)：73-75.

[2]尚文利,范玉順.成批生產(chǎn)計劃調(diào)度的集成建模與優(yōu)化[J].計算機(jī)集成制造系統(tǒng),2005,11(12)：1663-1667.

[3]鞠全勇.智能制造系統(tǒng)生產(chǎn)計劃與車間調(diào)度的研究[D].江蘇：南京航空航天大學(xué),2007.

[4]Rajkumar M,Asokan P.A GRASP algorithm for the integration of process planning and scheduling in a flexible job-shop[J].International Journal of Manufacturing Research.2010,5(2)：230-251.

[5]Seyed Habib A,Rahmati M,Zandieh M.Yazdani.Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem[J].The International Journal of Advanced Manufacturing Technology,2013,64(5-8)：915-932.

[6]李崢峰.多時間因素作業(yè)車間調(diào)度問題的研究與工程應(yīng)用[D].湖北：華中科技大學(xué),2010.

[7]An Yu-Wei,Yan Hong-Sen.Solution strategy of integrated optimization of production planning and scheduling in a flexible job-shop[J].Zidonghua Xuebao/Acta Automatica Sinica,2013,39(9)：1476-1491.

[8]王洪鋒,李洪宇.生產(chǎn)計劃和車間排程問題的整數(shù)規(guī)劃解法[J].現(xiàn)代制造工程,2008,7：92-95.

[9]葛繼科,邱玉輝,吳春明,蒲國林.遺傳算法研究綜述[J].計算機(jī)應(yīng)用研究,2008,25(10)：2911-2916.

[10]Li Jian-hong.An improved GA for job-shop scheduling problem[J].Advanced Materials Research.2013,630：486-489.

[11]Zhao Zi-xiang.Job-shop scheduling optimization design based on an improved GA[C].// Proceedings of the World Congress on Intelligent Control and Automation.United States：Institute of Electrical and Electronics Engineers Inc.,2012：654-659.

[12]溫蘊(yùn),孫亞.基于啟發(fā)式規(guī)則和蟻群算法的車間作業(yè)調(diào)度方法[J].計算機(jī)應(yīng)用與軟件,2009,26(6)：187-188,194.

[13]Wang Jiaxin.Heuristic rule for scheduling[J].Qinghua Daxue Xuebao/Journal of Tsinghua University(Science and Technology),1995,35(5)：27-32.

[14]Chien C-F,Chen C-H.Using genetic algorithms (GA)and a coloured timed Petri net (CTPN) for modeling the optimization-based schedule generator of a generic production scheduling system[J].International Journal of Production Research.2007,45(8)：1763-1789.