混合工作日歷下作業(yè)車間調(diào)度遺傳進化方法

曾 強 鄧敬源 常夢輝 張進春

河南理工大學能源科學與工程學院，焦作,454000

0 引言

作業(yè)車間調(diào)度問題(job shop scheduling problem，JSP)是復雜的NP-hard問題[1-2]，多年來一直是學術(shù)界的研究熱點。考慮到設備自動化程度、運行可靠性、固定成本、生產(chǎn)任務量的不同及人性化管理的需要，我國多品種小批量機械加工企業(yè)或車間內(nèi)各設備往往采用不盡相同的工作日歷，即混合工作日歷現(xiàn)象在多品種小批量機械加工企業(yè)中普遍存在。然而，現(xiàn)有作業(yè)車間調(diào)度研究成果尚不能有效解決混合工作日歷下的作業(yè)車間調(diào)度問題。

作業(yè)車間調(diào)度對于工作日歷的處理主要有三種情況：不考慮工作日歷、假定待調(diào)度設備采用統(tǒng)一的工作日歷、假定待調(diào)度設備采用混合工作日歷。絕大多數(shù)現(xiàn)有作業(yè)車間調(diào)度屬于第一種情況。在這種情況下，調(diào)度在連續(xù)的時間軸上安排工序[3-5]，雖然計算量最少，但得到的調(diào)度方案未與具體的日歷時間掛鉤，故難以有效指導生產(chǎn)實踐。第二種情況屬于調(diào)度后考慮工作日歷，其出發(fā)點是假定待調(diào)度設備采用統(tǒng)一的工作日歷，先拋開工作日歷的約束，使調(diào)度在連續(xù)的時間軸上安排工序，待得到最優(yōu)調(diào)度方案后根據(jù)統(tǒng)一的工作日歷進行時間推算，將最優(yōu)調(diào)度方案“映射”到具體的日歷時間上[6]，但它僅適用于待調(diào)度設備具有統(tǒng)一的工作日歷的情況。第三種情況屬于調(diào)度過程中考慮工作日歷，即為設備安排工序時依據(jù)其工作日歷進行。由于在調(diào)度過程中的時間推算過程需要進行大量的判斷，所以比第一、二種情況的計算量明顯增加。萬春輝等[7]進行作業(yè)車間調(diào)度時在調(diào)度過程中考慮了混合工作日歷。在調(diào)度前對設備的工作日歷進行個性化的設置，即為每臺設備設置工作日及工作班次，因為設備的工作日歷會經(jīng)常發(fā)生變化。由于待調(diào)度設備往往較多，為每臺設備做個性化的工作日歷設置需要花費大量時間，若調(diào)度周期較長，其包含的日歷時間數(shù)據(jù)增多，會使調(diào)度過程中的時間推算計算量大大增加。因此，在計算效率和工作日歷的精細化程度之間需要進行適當權(quán)衡。

作業(yè)車間調(diào)度求解方法主要有最優(yōu)化方法、啟發(fā)式方法、仿真方法、專家系統(tǒng)方法、神經(jīng)網(wǎng)絡方法、智能搜索方法等。最優(yōu)化方法通過數(shù)學規(guī)劃方法獲取最優(yōu)調(diào)度方案，僅適用于求解小規(guī)模調(diào)度問題。啟發(fā)式方法基于調(diào)度規(guī)則獲取近似調(diào)度方案，缺乏對整體性能的有效把握和預見能力，在實際應用中常將它與其他方法結(jié)合使用。仿真方法通過對實際生產(chǎn)環(huán)境的建模來模擬實際生產(chǎn)過程從而得到近似調(diào)度方案，仿真結(jié)論往往因模型不同而不同，很難獲得一個一致的結(jié)論[8]。專家系統(tǒng)通過基于知識的系統(tǒng)根據(jù)車間信息選擇最好的調(diào)度規(guī)則從而得到近似調(diào)度方案，但開發(fā)周期長、成本高昂，需要豐富的調(diào)度經(jīng)驗知識，對新的環(huán)境適應性較差。人工神經(jīng)網(wǎng)絡方法通過模仿生物神經(jīng)系統(tǒng)來獲取調(diào)度方案，僅適用于解決實驗環(huán)境下規(guī)模較小的問題[9]。目前作業(yè)車間調(diào)度應用較多的求解方法是智能搜索方法，包括遺傳算法[10-11]、禁忌搜索算法[12]、模擬退火算法[13]、蟻群搜索算法[14]、粒子群搜索算法[15]、蜂群搜索算法[16]、蝙蝠算法[17]及其混合算法等[18-19]。其中，遺傳算法因其有較好的全局搜索性能、魯棒性好、可擴展性好等優(yōu)點被廣泛用于求解作業(yè)車間調(diào)度問題。

基于以上分析，針對混合工作日歷下作業(yè)車間調(diào)度問題，筆者提出了一種遺傳進化優(yōu)化方法。

1 數(shù)學優(yōu)化模型構(gòu)建

1.1 問題描述

車間需在c臺設備(編號依次為1,2,…,c)上安排m個工件(編號依次為1,2,…,m)的加工任務。假設：①各設備按事先被指定的工作日歷運行。本文的工作日歷是工作制和工作時段的合稱。一旦某設備的工作制和工作時段被設定，則該設備在同一個調(diào)度周期內(nèi)每個工作日均按相同且固定不變的工作時段運行。②各設備采用的工作日歷不盡相同。③各工件的工藝流程事先被確定。④各工件每道工序所用設備事先被唯一確定。⑤各工序在指定設備上的調(diào)整時間和加工時間事先被確定。⑥工件加工是非搶占式的，即當一個工件正在加工時，不能停下來加工其他工件。⑦設備調(diào)整或工件加工可跨越設備停工時段，即當設備按工作日歷停工時，設備停止調(diào)整、工件停止加工，待設備重新開工時繼續(xù)未完成的工作。⑧設備初始狀態(tài)時其時間軸連續(xù)，即尚未被安排任何任務。⑨調(diào)度從調(diào)度起始時刻往后進行，該調(diào)度起始時刻由調(diào)度人員給定。要求：在以上假設條件下進行合理調(diào)度，在滿足一定約束條件下使生產(chǎn)周期最短。

1.2 符號定義

表1給出了本文涉及參數(shù)的定義。

表1 相關(guān)參數(shù)

1.3 優(yōu)化模型

以生產(chǎn)周期最短為優(yōu)化目標，建立一類混合工作日歷作業(yè)車間調(diào)度優(yōu)化模型。

(1)目標函數(shù)

(1)

(2)約束條件

tsbij≥tcei(j-1)若Ji工序j采用設備p,工序j-1采用設備q加工且p=q

(2)

tcbij≥tcei(j-1)若Ji工序j采用設備p,工序j-1采用設備q加工且p≠q

(3)

At(tcbij～tceij)=ctij?i,j

(4)

At(tsbij～tseij)=stij?i,j

(5)

tsbij∈Wktseij∈Wktcbij∈Wktceij∈Wk?i,j,Jij所用設備號為k

(6)

tsbij≥bttseij≥bttcbij≥bttceij≥bt?i,j

(7)

式(1)表示生產(chǎn)周期最小化，這里的生產(chǎn)周期是指m個工件的加工結(jié)束時刻與最早的設備調(diào)整時刻之間的日歷時間；式(2)表示若Ji的工序j-1與工序j所用設備相同(p=q)，由于設備被占用無法提前調(diào)整，故工序j必須在工序j-1加工結(jié)束時刻之后才能開始設備調(diào)整；式(3)表示若Ji工序j-1與j工序所用設備不同(p≠q)，則工序j可以提前開始進行設備調(diào)整以保證工序j-1加工結(jié)束后它能盡快開始加工；式(4)表示任意工序的加工開始時刻與加工結(jié)束時刻之間的有效工作時間等于其加工時間；式(5)表示任意工序的設備調(diào)整開始時刻與結(jié)束時刻之間的有效工作時間等于其調(diào)整時間；式(6)表示任意工序的設備調(diào)整開始時刻和結(jié)束時刻、加工開始時刻和結(jié)束時刻必須落入所用設備的工作時段內(nèi)；式(7)表示任意工序的設備調(diào)整開始時刻不能早于給定的調(diào)度起始時刻bt。

從以上優(yōu)化模型可以看出，該調(diào)度優(yōu)化模型不是常規(guī)的線性規(guī)劃模型，約束條件式(4)～式(6)不屬于常規(guī)約束條件。相對于傳統(tǒng)的作業(yè)車間調(diào)度問題，該問題具有更高的復雜性，適合采用智能搜索算法求解。本文選用遺傳算法對上述優(yōu)化模型進行求解。

2 基于工作日歷的時間推算方法

混合工作日歷下作業(yè)車間調(diào)度的關(guān)鍵問題是如何基于工作日歷進行時間推算。按照假設條件①，本文的工作日歷是工作制和工作時段的合稱。基于此，本文用Excel設計了若干張工作表，每張工作表對應一個工作制，在此基礎上設計設備工作表，在其中將工作制指定給各設備，并為其設置工作時段，最后利用Excel VBA設計了推算函數(shù)實現(xiàn)基于工作日歷的時間推算。

2.1 工作日歷設計

(1)工作制設計。以6天工作制為例，設計名稱為6天工作制的工作表，其結(jié)構(gòu)見圖1。A～D列設置非周末但不工作的日期，E～H列設置周末但要工作的日期。

ABCDEFGH1序號日期周幾備注序號日期周幾備注212017/1/2112017/1/76322017/1/27522017/1/146?????????

圖16天工作制工作表

Fig.1Sixdayworkingsystemsheet

(2)工作制及工作時段設置。設計設備工作表，其結(jié)構(gòu)見圖2。D列為設備工作制，E列為日工作時段數(shù)，F(xiàn)列為日工作時間，從G列開始的各列為各工作時段的開工、停工時刻。工作時段須成對輸入，范圍從0:00～24:00，須保證各工作時段的停工時刻大于開工時刻且各工作時段之間不能有交叉。

ABCDEFGHIJKL1設備號設備代碼設備類別工作制時段數(shù)時間開工停工開工停工開工停工21300T車床5天工作制288:0012:0013:0017:0032T52車床6天工作制3210:007:008:0015:0016:0023:00?????????????

圖2設備工作表

Fig.2Machinessheet

2.2 基于工作日歷的時間推算函數(shù)設計

以Excel VBA為平臺設計了6個函數(shù)實現(xiàn)時間推算，分別是Isworkday、Nextworkday、Getsd、Forwardwd、Backwd和Getat。

(1)Isworkday函數(shù)。該函數(shù)有2個參數(shù)，md(Date型)和wds(String型)，其作用是根據(jù)設備工作制wds判斷日期md是否為其工作日，若是工作日則返回1，否則返回0。

(2)Nextworkday函數(shù)。該函數(shù)有3個參數(shù)，md(Date型)、x(Integer型)和wds(String型)，其作用是獲得根據(jù)設備工作制wds從日期md推算x天后的工作日，x>0時為正向推算，x<0時為反向推算。

(3)Getsd函數(shù)。該函數(shù)有2個參數(shù)，t(Double型)、mn(Integer型)，其作用是根據(jù)設備mn的工作時段獲得時間t所在的位置，其返回值為數(shù)組A，該數(shù)組有2個元素，A(2)是標志元素，其值為0表示時間t屬于設備mn第A(1)個非工作時段，其值為1則表示時間t屬于設備mn第A(1)個工作時段。在圖3中，該設備的工作日有2個工作時段，8:00～12:00(編號為1)和13:00～17:00(編號為2)，它們把時間0:00～24:00劃分成5個時間段，另外3個時間段為非工作時段，0:00～8:00(編號為0)、12:00～13:00(編號為1)、17:00～24:00(編號為2)。

圖3 某設備工作時段與非工作時段Fig.3 Work time and non-work time periods of a machine

(4)Forwardwd函數(shù)。該函數(shù)有3個參數(shù)，mdt(Date型)、tt(Double型)和mn(Integer型)，其作用是根據(jù)設備mn的工作日歷獲得從某個工作時刻mdt正向推算tt小時后的工作時刻。

(5)Backwd函數(shù)。該函數(shù)有3個參數(shù)，mdt(Date型)、tt(Double型)和mn(Integer型)，其作用是根據(jù)設備mn的工作日歷獲得從某個工作時刻mdt反向推算tt小時后的工作時刻。

(6)Getat函數(shù)。該函數(shù)有2個參數(shù)，mdt(Date型)和mn(Integer型)，其作用是根據(jù)設備mn的工作日歷獲得從某個時刻mdt正向推算得到的最早工作時刻。

3 遺傳算法設計

針對混合工作日歷下作業(yè)車間調(diào)度問題的特點，以Excel VBA為平臺設計了一種遺傳進化算法(genetic algorithm，GA)。

3.1 相關(guān)工作表設計

除2.1節(jié)設計的工作制工作表和設備工作表外，根據(jù)需要，設計了參數(shù)設置、工件、工藝流程、進化過程、最優(yōu)解等工作表，用于輸入?yún)?shù)的設置和進化結(jié)果的輸出。

3.2 定義類型、變量及數(shù)組

根據(jù)需要，定義了圖4所示的自定義類型mach、proc、job、chr和表2所示的全局變量及數(shù)組。其中，chr.R為tpnum×10的矩陣，1～10列依次存儲任務序號、工件號、工序號、設備號、調(diào)整時間、加工時間、設備調(diào)整開始時刻、設備調(diào)整結(jié)束時刻、加工開始時刻、加工結(jié)束時刻。MA為mnum×22的數(shù)組(按8個工作時段設計，當然還可以增加列數(shù)從而增加工作時段)，用于存儲各設備的參數(shù)。JB為jnum個元素的數(shù)組，其元素類型為job，用于存儲各工件的參數(shù)。MMB為mnum個元素的數(shù)組，其元素類型為mach，用于存儲調(diào)度前各設備的時間狀態(tài)。算法流程見圖5。

圖4 自定義類型

圖5 算法流程Fig.5 Flow of the algorithm

3.3 獲取參數(shù)

從工作表中讀取相關(guān)參數(shù)賦給表1中的變量。其中，MA從設備工作表讀取第2行及以后的數(shù)據(jù)。MMB按如下方法賦值：按照假設條件⑧，調(diào)度初始時刻各設備時間軸連續(xù)，假設條件⑨表明調(diào)度從調(diào)度起始時刻bt往后進行，因此在本算法中采用for循環(huán)為各設備的空閑時間段各賦兩個元素，bt和tln。以設備i為例，令MMB(i).TS(1)=bt，MMB(i).TS(2)=tln。JB按如下方法賦值：采用For循環(huán)從1～jnum分別對JB的每一個元素賦值。對工件i，先從工作表“工件”中讀取第i個工件的工件名稱、型號、工序數(shù)分別賦給JB(i).name，JB(i).type、JB(i).pnum，再用RedimJB(i).PR(JB(i).pnum)重新定義JB(i).PR的維數(shù)，再用for循環(huán)從工作表“工藝流程”中讀取該工件對應工序參數(shù)分別賦給JB(i).PR(1)～JB(i).PR(JB(i).pnum)。

3.4 編碼方式

采用基于工序的編碼方式對個體進行編碼：

(8)

ch.R為tpnum×10的矩陣，第2列為編碼所用，基因值為1～jnum的隨機整數(shù)，各整數(shù)出現(xiàn)的次數(shù)等于對應工件的工序數(shù)，其他各列為輔助或解碼所用。

3.5 種群初始化

按照圖6所示的流程分別產(chǎn)生popsize個隨機可行個體，依次存入種群OLDPOP，從而完成種群初始化。圖中，給第4列賦設備號的方法如下：根據(jù)工件號R(i,2)、工序號R(i,3)直接從JB對象數(shù)組中讀取。例如，對于第i行，有R(i,4)=JB(R(i,2)).PR(R(i,3)).mn。

圖6 產(chǎn)生隨機個體流程Fig.6 Flow of generating random individuals

3.6 遺傳操作

(1)遺傳操作流程。本文設計的遺傳操作流程見圖7。

圖7 遺傳操作流程Fig.7 Flow of genetic operation

(2)交叉操作。根據(jù)個體編碼方式的特點，為減少計算次數(shù)，基于遺傳算子改進策略，采用基于工序順序的交叉方式來保證子代個體可行性[20]。具體方法如下：同一工件的工序之間具有先后順序，為保證交叉操作不破壞這種先后順序，固定某父體的某個工件號所在行內(nèi)容(工件號、工序號和設備號)不變，從上到下依次用另一父體中除該工件號所在行之外的其他行取代本父體剩余行。例如：

(9)

若P1.R中固定工件1，P2.R中固定工件2不動，則P1.R與P2.R交叉后的結(jié)果如下所示：

(10)

(3)變異操作。與交叉操作類似，為減少計算次數(shù)，基于遺傳算子改進策略，采用基于工序順序的變異方式來保證子代個體可行性[20]。具體方法如下：隨機產(chǎn)生一個1,2,…,tpnum之間的整數(shù)mp作為變異點，以此點為基準向上向下分別尋找與該點工件號相同的最近位置s1和s2，若向上沒有找到則令s1=0，向下沒有找到則令s2=tpnum+1；取k1=s1+1，k2=s2-1，隨機產(chǎn)生k1～k2的整數(shù)k，將該工件號、工序號及設備號滑移至k位置。例如，式(3)中，若P1′.R中假定mp=3，則可求得k1=2,k2=8，若隨機產(chǎn)生的整數(shù)k=6，則P1′.R變異后的結(jié)果如下所示：

(11)

3.7 解碼操作

解碼操作的目的是根據(jù)ch.R的前4列及相關(guān)參數(shù)，從前到后依次安排每個加工任務，確定ch.R的第5～10列。由于本文優(yōu)化目標是求生產(chǎn)周期最短化，為了盡可能縮短生產(chǎn)周期，采用如下兩種措施。第一種是將工序時間細分為設備調(diào)整時間和加工時間，使得下道工序的設備調(diào)整工作有條件提前進行，從而使上道工序加工完畢后能盡早開始加工[21-22]；第二種是采用正向可插入式擠壓調(diào)度方法，采用“見縫插針”的方式在設備的時間軸上安排工序，以便盡可能減少設備空閑時間。解碼操作流程見圖8，對應函數(shù)為Decode。

圖8 解碼操作流程Fig.8 Flow of decoding operation

解碼第一步：將解碼前設備時間狀態(tài)對象數(shù)組MMB賦給MM，將ch.R賦給R。

解碼第二步：令i=1，2，…，tpnum，從前往后依次安排各工序，確定ch.R的第5～10列值。此步又分為以下5個子步驟。

(1)獲取設備調(diào)整時間st和加工時間ct。這一步可直接從JB讀出，即st=JB(R(i,2)).PR(R(i,3)).st，ct=JB(R(i,2)).PR(R(i,3)).ct。

(2)獲取工件R(i,2)的工序R(i,3)設備最早可開始調(diào)整時刻g。如圖9所示，分三種情況分別處理。

圖9 獲取工件R(i,2)的工序R(i,3)的設備最早可開始調(diào)整時刻gFig.9 Obtaining the machines’ earliest start time g of the process R(i,3) of job R(i,2)

情況1：R(i,3)=1時，即待安排工序是工件R(i,2)的第1道工序。若不考慮設備的工作日歷和已占用時間，則該工序的最早可開始設備調(diào)整時刻與調(diào)度起始時刻相等，故取g=bt。

情況2：R(i,3)≠1且工件R(i,2)的工序R(i,3)與R(i,3)-1均在同一臺設備p上加工。這種情況下，工件R(i,2)的工序R(i,3)必須等到工序R(i,3)-1完工后才能開始設備調(diào)整，故取g等于工件R(i,2)的工序R(i,3)-1的加工結(jié)束時刻。設工件R(i,2)的工序R(i,3)-1在R中的行號為h，則取g=Getat(R(h,10),R(i,4))。

情況3：R(i,3)≠1且工件R(i,2)的工序R(i,3)與R(i,3)-1不在同一臺設備上加工。此時工件R(i,2)的工序R(i,3)-1可從R(i,3)-1的加工結(jié)束時刻提前st小時開始設備調(diào)整，待設備調(diào)整完畢，工序R(i,3)-1正好完成加工，使工序R(i,3)可立即開始加工。設工件R(i,2)的工序R(i,3)-1在R中的行號為h，則首先采用Getat函數(shù)根據(jù)設備R(i,4)的工作日歷正向推算得到工作時刻t(工序R(i,3)-1的加工結(jié)束時刻未必在R(i,4)的工作時間段內(nèi)，其最早可能開始加工時刻為正向推算得到的工作時刻t)，再利用Backwd函數(shù)從t反向推算st小時得到設備最早可開始調(diào)整時刻g。具體地，第一步，令t=Getat(R(h,10),R(i,4))；第二步，令g=Backwd(t,st,R(i,4))。

(3)獲得設備R(i,4)當前空閑時間段數(shù)賦給frnum。方法如下：令frnum=Ubound(MM(R(i,4)).TS)/2。

(4)令tb=MM(R(i，4)).TS(2k-1)，te=MM(R(i，4)).TS(2k)，Δ=te-tb。

(5)令k=1～frnum，依次判斷是否Δ大于等于ct且te大于等于g，若不滿足上述必要條件，則考慮下一個空閑時間段；否則將g和tb的最大值賦給t1。令tsb=Getat(t1,R(i,4))得到設備調(diào)整開始時刻，再令tse=Forwardwd(tsb,st,R(i,4))得到設備調(diào)整結(jié)束時刻，令tcb=Getat(tse,R(i,4))得到工序加工開始時刻，令tce=Forwardwd(tcb,ct,R(i,4))得到工序加工結(jié)束時刻，然后判斷tce是否小于等于te。若不滿足上述條件，則轉(zhuǎn)向下一個空閑時間段；若滿足條件則表示當前工序可插入設備R(i,4)的第k個空閑時間段。將ct,st,tsb,tse,tcb,tce依次存入R(i,5)～R(i,10)，并更新MM(R(i,4)).TS。

圖10 更新MM1(R(i,4)).TSFig.10 Updating MM(R(i,4)).TS

圖10為更新MM(R(i,4)).TS的示意圖。MM(R(i,4)).TS的初始長度為2，僅包含2個元素，第1個為調(diào)度起始時刻bt，第2個為時間大值tln。此時空閑時間段數(shù)frnum=1。當為設備R(i,4)安排某工序a后，需在bt～tln之間插入2個值，分別是tsba(設備調(diào)整開始時刻)和tcea(加工結(jié)束時刻)。此時bt～tln被分割成2個空閑時間段，分別是bt～tsba和tcea～tln，空閑時間段數(shù)frnum=2。當再為R(i,4)安排某工序b后(假設工序b安排在工序a加工結(jié)束時刻之后)，空閑時間段分別為bt～tsba、tcea～tsbb、tceb～tln，空閑時間段數(shù)frnum=3。依次類推，隨著工序的不斷安排，MM(R(i,4)).TS的長度動態(tài)變化、元素動態(tài)更新。需說明的是：若tcea=tsbb則MM(R(i,4)).TS數(shù)據(jù)結(jié)構(gòu)仍舊不變，空閑時間段數(shù)和空閑時間段保持不變。只是第2個空閑時間段的時間差為0，在后續(xù)的工序安排中，由解碼操作流程可以看出不會在tcea～tsbb之間插入工序。設插入時段為設備R(i,4)的第k個空閑時段，則更新MM(R(i,4)).TS的步驟如下：首先，將MM(R(i,4)).TS的長度增加2位；然后，從k空閑時段對應的第2個數(shù)據(jù)起，將后面的數(shù)據(jù)后移2位，從而騰出兩個空位；最后，在兩個空位處分別填入待插入工序的設備調(diào)整開始時刻和加工結(jié)束時刻。

解碼第三步：當把1～tpnum個工序全部安排完畢后，將得到的調(diào)度數(shù)組R及MM賦給ch。即令ch.R=R,ch.MMA=MM。至此，解碼操作結(jié)束。

3.8 計算適應度

計算個體適應度的流程見圖11。首先，利用解碼函數(shù)Decode對個體ch進行解碼得到調(diào)度數(shù)組ch.R，然后采用for循環(huán)找出ch.R第7列的最小值賦給smin、第10列的最大值賦給smax，再計算目標值ch.o，ch.o=smax-smin。由于本文優(yōu)化目標是生產(chǎn)周期的最小化，故適應度值需由優(yōu)化目標轉(zhuǎn)化為最大化值。轉(zhuǎn)化的方法一般有兩種，一種是取倒數(shù)，另一種是用足夠大的正數(shù)減去目標值。本文采用第二種方法計算適應度，用大數(shù)ln減去目標值ch.o得到適應度，即ch.fit=ln-ch.o。

圖11 計算適應度流程圖Fig.11 Flow of calculating the fitness

4 案例分析

某機加車間在某調(diào)度周期內(nèi)要在9臺設備上安排15個工件的加工，工件信息見表3、工藝流程見表4，設備信息見表5。本例中設備所用工作制共有3種，即5天工作制、6天工作制和7天工作制。對于5天工作制，由于非周末節(jié)假日不工作，故將表6的非周末節(jié)假日填入工作表5天工作制的A～D列；由于周六、周日不工作，故將E～H列留空。對于6天工作制，將表6的非周末節(jié)假日填入工作表6天工作制的A～D列；將表7中所列周六需工作的日期填入工作表6天工作制的E～H列。同理，對于7天工作制，將表6的非周末節(jié)假日填入工作表7天工作制的A～D列；將表7中所列周六需工作的日期填入工作表7天工作制的E～H列，再將表8所列周日需工作的日期填入7天工作制E～H列；其他參數(shù)見表9。

表3 工件

表4 工藝流程

表5 設備

表6 非周末節(jié)假日

表7 周六需工作的日期

表8 周日需工作的日期

表9 計算參數(shù)

圖12為某次獨立進化的進化過程圖。表10是本次進化得到的最優(yōu)調(diào)度方案對應的調(diào)度表。圖13、圖14分別為該最優(yōu)調(diào)度方案對應的工件甘特圖和設備甘特圖。由表10第22行可以看出，工序J4.3在設備3(代碼為200T)上加工，其設備調(diào)整起始時刻為2017/3/7 16:24、結(jié)束時刻為2017/3/8 0:18，雖然2017/3/7 16:24至2017/3/8 0:18之間的日歷時間遠大于0.9小時，但根據(jù)該設備的工作日歷可知，2017/3/7 16:24至2017/3/8 0:18的工作時間為0.9小時，正好于設備調(diào)整時間0.9小時吻合。同樣，表10的第3行可以看出，工序J4.1在設備1(代碼為300T)上加工，其工序加工起始時刻為2017/3/3 10:42、結(jié)束時刻為2017/3/7 11:06，雖然2017/3/3 10:42至2017/3/7 11:06之間的日歷時間遠大于16.4小時，但其工作時間卻只有為16.4小時(其中，從表5～表7可以看出，2017/3/4、2017/3/5是設備300T的休息日)，也正好與工序的加工時間16.4小時相吻合。以上表明算法在工序的安排過程考慮了設備的工作日歷(包括工作制和工作時段)，使得設備調(diào)整起止時刻、工序加工起止時間與實際情況完全吻合。

圖12 某次進化過程Fig.12 An evolutionary process

圖13 工件甘特圖Fig.13 Gantt chart of the jobs

圖14 設備甘特圖Fig.14 Gantt chart of the machines

序號任務工件工序設備設備代碼調(diào)整時間加工時間調(diào)整開始時刻調(diào)整結(jié)束時刻加工開始時刻加工結(jié)束時刻1J1.1111300T0.911.22017/3/1 8:002017/3/1 8:542017/3/1 8:542017/3/2 13:062J8.1811300T0.94.82017/3/2 13:062017/3/2 14:002017/3/2 14:002017/3/3 9:483J4.1411300T0.916.42017/3/3 9:482017/3/3 10:422017/3/3 10:422017/3/7 11:064J14.11413200T0.95.82017/3/1 9:002017/3/1 9:542017/3/1 9:542017/3/1 15:425J4.2422T521.211.22017/3/7 9:542017/3/7 11:062017/3/7 11:062017/3/8 0:186J9.1911300T0.95.82017/3/7 11:062017/3/7 12:002017/3/7 13:002017/3/8 9:487J5.1511300T0.911.12017/3/8 9:482017/3/8 10:422017/3/8 10:422017/3/9 14:488J15.11512T520.96.22017/3/1 8:002017/3/1 8:542017/3/1 8:542017/3/1 16:069J2.1211300T0.913.72017/3/9 14:482017/3/9 15:422017/3/9 15:422017/3/13 13:2410J5.2522T520.98.92017/3/9 13:542017/3/9 14:482017/3/9 14:482017/3/10 1:42

(續(xù)表)

序號任務工件工序設備設備代碼調(diào)整時間加工時間調(diào)整開始時刻調(diào)整結(jié)束時刻加工開始時刻加工結(jié)束時刻11J7.1711300T0.96.52017/3/13 13:242017/3/13 14:182017/3/13 14:182017/3/14 11:4812J8.2822T520.97.82017/3/3 8:542017/3/3 9:482017/3/3 9:482017/3/3 18:3613J15.21521300T0.952017/3/14 11:482017/3/14 13:422017/3/14 13:422017/3/15 9:4214J6.1611300T0.911.72017/3/15 9:422017/3/15 10:362017/3/15 10:362017/3/16 15:1815J11.11111300T0.96.42017/3/16 15:182017/3/16 16:122017/3/16 16:122017/3/17 14:3616J12.11213200T0.95.62017/3/1 15:422017/3/1 16:362017/3/1 16:362017/3/2 5:1217J8.3833200T0.962017/3/3 16:062017/3/3 17:002017/3/4 0:002017/3/4 6:0018J6.2622T520.911.52017/3/16 14:062017/3/16 15:002017/3/16 16:002017/3/17 4:3019J5.3533200T1.262017/3/10 0:302017/3/10 1:422017/3/10 1:422017/3/10 7:4220J14.21422T520.95.82017/3/1 16:062017/3/1 17:002017/3/1 17:002017/3/1 22:4821J12.21222T520.94.82017/3/2 4:182017/3/2 5:122017/3/2 5:122017/3/2 11:0022J4.3433200T0.96.12017/3/7 16:242017/3/8 0:182017/3/8 0:182017/3/8 6:2423J11.21123200T0.96.52017/3/17 13:422017/3/17 14:362017/3/17 14:362017/3/18 4:0624J6.3633200T0.98.42017/3/18 4:062017/3/18 5:002017/3/18 5:002017/3/18 14:2425J12.31231300T0.97.22017/3/17 14:362017/3/17 15:302017/3/17 15:302017/3/20 14:4226J1.2122T520.98.62017/3/2 12:122017/3/2 13:062017/3/2 13:062017/3/2 22:4227J6.4644J50010.913.32017/3/18 13:302017/3/18 14:242017/3/18 14:242017/3/19 5:4228J3.1311300T0.97.22017/3/20 14:422017/3/20 15:362017/3/20 15:362017/3/21 14:4829J13.11312T520.96.22017/3/2 22:422017/3/3 0:362017/3/3 0:362017/3/3 6:4830J2.2222T520.97.92017/3/13 12:302017/3/13 13:242017/3/13 13:242017/3/13 22:1831J11.31132T520.96.52017/3/18 3:122017/3/18 4:062017/3/18 4:062017/3/18 11:3632J7.2722T520.96.52017/3/14 10:542017/3/14 11:482017/3/14 11:482017/3/14 19:1833J1.3133200T1.213.22017/3/2 15:482017/3/2 17:002017/3/3 0:002017/3/3 14:1234J7.3733200T0.94.82017/3/14 16:062017/3/14 17:002017/3/15 0:002017/3/15 4:4835J4.4444J50010.98.32017/3/8 5:302017/3/8 6:242017/3/8 6:242017/3/8 16:4236J10.11011300T0.97.52017/3/21 14:482017/3/21 15:422017/3/21 15:422017/3/22 15:1237J12.41249111CNC1.282017/3/20 13:302017/3/20 14:422017/3/20 14:422017/3/21 4:4238J13.21321300T0.94.52017/3/22 15:122017/3/22 16:062017/3/22 16:062017/3/23 11:3639J7.4745J40011.25.62017/3/14 15:482017/3/14 17:002017/3/15 8:002017/3/15 14:3640J6.56563U51.511.62017/3/17 16:302017/3/17 18:002017/3/20 0:002017/3/20 13:3641J15.31533200T0.97.22017/3/15 7:482017/3/15 9:422017/3/15 9:422017/3/15 16:5442J12.51255J40011.28.22017/3/20 15:482017/3/20 17:002017/3/21 8:002017/3/22 8:1243J15.41544J50010.95.52017/3/15 16:002017/3/15 16:542017/3/15 16:542017/3/15 22:2444J14.31433200T0.96.32017/3/2 5:122017/3/2 6:062017/3/2 6:062017/3/2 13:2445J9.2922T520.98.32017/3/8 8:542017/3/8 9:482017/3/8 9:482017/3/8 19:0646J13.31333200T0.94.92017/3/23 10:422017/3/23 11:362017/3/23 11:362017/3/23 16:3047J2.3233200T1.29.92017/3/13 15:482017/3/13 17:002017/3/14 0:002017/3/14 10:5448J11.41143200T0.97.12017/3/18 14:242017/3/18 15:182017/3/18 15:182017/3/20 5:2449J1.4144J50010.99.92017/3/3 13:182017/3/3 14:122017/3/3 14:122017/3/4 2:0650J1.51563U51.57.32017/3/3 16:302017/3/3 18:002017/3/6 0:002017/3/6 7:1851J3.2322T520.96.22017/3/21 13:542017/3/21 14:482017/3/21 14:482017/3/21 22:0052J13.41344J50010.97.22017/3/23 14:362017/3/23 16:302017/3/23 16:302017/3/24 0:4253J9.3933200T0.95.32017/3/8 16:062017/3/8 17:002017/3/9 0:002017/3/9 5:1854J3.3333200T1.28.52017/3/21 15:482017/3/21 17:002017/3/22 0:002017/3/22 9:3055J11.51158120CNC1.152017/3/18 15:542017/3/18 17:002017/3/20 8:002017/3/20 14:0056J11.61169111CNC1.2102017/3/21 4:422017/3/21 5:542017/3/21 5:542017/3/21 17:5457J11.711772U51.26.52017/3/21 15:482017/3/21 17:002017/3/22 8:002017/3/22 15:3058J14.41445J40011.29.82017/3/2 11:122017/3/2 13:242017/3/2 13:242017/3/3 15:12

(續(xù)表)

序號任務工件工序設備設備代碼調(diào)整時間加工時間調(diào)整開始時刻調(diào)整結(jié)束時刻加工開始時刻加工結(jié)束時刻59J6.6669111CNC1.211.82017/3/21 17:542017/3/22 1:062017/3/22 1:062017/3/22 14:5460J4.54563U51.515.32017/3/8 15:122017/3/8 16:422017/3/8 16:422017/3/9 16:0061J5.4545J40011.213.82017/3/9 15:482017/3/9 17:002017/3/10 8:002017/3/11 14:4862J14.51454J50010.96.82017/3/4 2:062017/3/4 3:002017/3/4 3:002017/3/4 10:4863J5.5558120CNC1.172017/3/11 13:422017/3/11 14:482017/3/11 14:482017/3/13 13:4864J9.4948120CNC1.162017/3/8 15:542017/3/8 17:002017/3/9 8:002017/3/9 15:0065J15.515563U51.27.82017/3/15 16:482017/3/15 18:002017/3/16 0:002017/3/16 7:4866J10.21022T520.94.92017/3/22 14:062017/3/22 15:002017/3/22 16:002017/3/22 20:5467J3.4344J50010.916.32017/3/22 8:362017/3/22 9:302017/3/22 9:302017/3/23 3:4868J3.53563U51.57.82017/3/23 2:182017/3/23 3:482017/3/23 3:482017/3/23 13:3669J4.6469111CNC1.26.22017/3/9 14:482017/3/9 16:002017/3/9 16:002017/3/10 4:1270J2.4244J50010.911.62017/3/14 10:002017/3/14 10:542017/3/14 10:542017/3/15 0:3071J8.48463U51.28.22017/3/6 7:182017/3/6 9:302017/3/6 9:302017/3/7 0:4272J1.6168120CNC1.18.52017/3/4 15:542017/3/4 17:002017/3/6 8:002017/3/7 8:3073J10.31033200T0.95.52017/3/22 16:062017/3/22 17:002017/3/23 0:002017/3/23 5:3074J10.41048120CNC1.14.82017/3/22 15:542017/3/22 17:002017/3/23 8:002017/3/23 13:4875J9.59572U51.27.92017/3/9 13:482017/3/9 15:002017/3/9 15:002017/3/10 14:5476J7.5754J50010.98.62017/3/15 22:242017/3/16 0:182017/3/16 0:182017/3/16 9:5477J8.58572U51.28.62017/3/6 15:482017/3/6 17:002017/3/7 8:002017/3/8 8:3678J2.52572U51.29.32017/3/14 15:482017/3/14 17:002017/3/15 8:002017/3/16 9:18

從表10第3行、5行、22行、35行、60行、69行可以看出，工件4有6道工序，分別在不同的設備上加工，因此可以提前進行設備調(diào)整，當上道工序完成加工時，可立即開始下道工序的加工，采用這種安排方式在一定程度上縮短了生產(chǎn)周期。其他工件在安排工序時與工件4采用了相同的處理方式。

從表10可以看出，按序號升序排列，設備8(代碼為120CNC)上安排的工序依次為J11.5、J5.5、J9.4、J1.6、J10.4，而從圖14可以看出，設備8上從左到右安排的工序依次為J1.6、J9.4、J5.5、J11.5、J10.4，二者不一定完全一致。產(chǎn)生這種現(xiàn)象的原因在于解碼過程中采用了正向可插入式擠壓調(diào)度方法，可以盡可能地減少設備空閑時間從而縮短生產(chǎn)周期。

5 結(jié)語

為解決混合工作日歷下作業(yè)車間調(diào)度的困難，提出了一種遺傳進化方法，該方法突破了傳統(tǒng)作業(yè)車間調(diào)度的局限，能在可接受的計算時間內(nèi)得到有效的作業(yè)車間優(yōu)化調(diào)度方案。在該方法中，對于工序起止調(diào)整時刻、起止加工時刻的計算采用自定義的時間推算函數(shù)進行準確推算，能保證混合工作日歷下作業(yè)車間調(diào)度方案的可行性。在解碼過程中采用了兩項技術(shù)用以縮短生產(chǎn)周期：將工序時間細分為設備調(diào)整時間和加工時間，能使下道工序的設備可提前開始設備調(diào)整；采用正向可插入式擠壓調(diào)度方法安排工序。