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

曾 強(qiáng) 鄧敬源 常夢(mèng)輝 張進(jìn)春

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

0 引言

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

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

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

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

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

1.1 問(wèn)題描述

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

1.2 符號(hào)定義

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

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

1.3 優(yōu)化模型

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

(1)目標(biāo)函數(shù)

(1)

(2)約束條件

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

(2)

tcbij≥tcei(j-1)若Ji工序j采用設(shè)備p,工序j-1采用設(shè)備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所用設(shè)備號(hào)為k

(6)

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

(7)

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

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

2 基于工作日歷的時(shí)間推算方法

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

2.1 工作日歷設(shè)計(jì)

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

ABCDEFGH1序號(hào)日期周幾備注序號(hào)日期周幾備注212017/1/2112017/1/76322017/1/27522017/1/146?????????

圖16天工作制工作表

Fig.1Sixdayworkingsystemsheet

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

ABCDEFGHIJKL1設(shè)備號(hào)設(shè)備代碼設(shè)備類(lèi)別工作制時(shí)段數(shù)時(shí)間開(kāi)工停工開(kāi)工停工開(kāi)工停工21300T車(chē)床5天工作制288:0012:0013:0017:0032T52車(chē)床6天工作制3210:007:008:0015:0016:0023:00?????????????

圖2設(shè)備工作表

Fig.2Machinessheet

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

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

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

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

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

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

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

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

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

3 遺傳算法設(shè)計(jì)

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

3.1 相關(guān)工作表設(shè)計(jì)

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

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

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

圖4 自定義類(lèi)型

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

3.3 獲取參數(shù)

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

3.4 編碼方式

采用基于工序的編碼方式對(duì)個(gè)體進(jìn)行編碼：

(8)

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

3.5 種群初始化

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

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

3.6 遺傳操作

(1)遺傳操作流程。本文設(shè)計(jì)的遺傳操作流程見(jiàn)圖7。

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

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

(9)

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

(10)

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

(11)

3.7 解碼操作

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

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

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

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

(1)獲取設(shè)備調(diào)整時(shí)間st和加工時(shí)間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)設(shè)備最早可開(kāi)始調(diào)整時(shí)刻g。如圖9所示，分三種情況分別處理。

圖9 獲取工件R(i,2)的工序R(i,3)的設(shè)備最早可開(kāi)始調(diào)整時(shí)刻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時(shí)，即待安排工序是工件R(i,2)的第1道工序。若不考慮設(shè)備的工作日歷和已占用時(shí)間，則該工序的最早可開(kāi)始設(shè)備調(diào)整時(shí)刻與調(diào)度起始時(shí)刻相等，故取g=bt。

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

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

(3)獲得設(shè)備R(i,4)當(dāng)前空閑時(shí)間段數(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è)空閑時(shí)間段；否則將g和tb的最大值賦給t1。令tsb=Getat(t1,R(i,4))得到設(shè)備調(diào)整開(kāi)始時(shí)刻，再令tse=Forwardwd(tsb,st,R(i,4))得到設(shè)備調(diào)整結(jié)束時(shí)刻，令tcb=Getat(tse,R(i,4))得到工序加工開(kāi)始時(shí)刻，令tce=Forwardwd(tcb,ct,R(i,4))得到工序加工結(jié)束時(shí)刻，然后判斷tce是否小于等于te。若不滿足上述條件，則轉(zhuǎn)向下一個(gè)空閑時(shí)間段；若滿足條件則表示當(dāng)前工序可插入設(shè)備R(i,4)的第k個(gè)空閑時(shí)間段。將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的初始長(zhǎng)度為2，僅包含2個(gè)元素，第1個(gè)為調(diào)度起始時(shí)刻bt，第2個(gè)為時(shí)間大值tln。此時(shí)空閑時(shí)間段數(shù)frnum=1。當(dāng)為設(shè)備R(i,4)安排某工序a后，需在bt～tln之間插入2個(gè)值，分別是tsba(設(shè)備調(diào)整開(kāi)始時(shí)刻)和tcea(加工結(jié)束時(shí)刻)。此時(shí)bt～tln被分割成2個(gè)空閑時(shí)間段，分別是bt～tsba和tcea～tln，空閑時(shí)間段數(shù)frnum=2。當(dāng)再為R(i,4)安排某工序b后(假設(shè)工序b安排在工序a加工結(jié)束時(shí)刻之后)，空閑時(shí)間段分別為bt～tsba、tcea～tsbb、tceb～tln，空閑時(shí)間段數(shù)frnum=3。依次類(lèi)推，隨著工序的不斷安排，MM(R(i,4)).TS的長(zhǎng)度動(dòng)態(tài)變化、元素動(dòng)態(tài)更新。需說(shuō)明的是：若tcea=tsbb則MM(R(i,4)).TS數(shù)據(jù)結(jié)構(gòu)仍舊不變，空閑時(shí)間段數(shù)和空閑時(shí)間段保持不變。只是第2個(gè)空閑時(shí)間段的時(shí)間差為0，在后續(xù)的工序安排中，由解碼操作流程可以看出不會(huì)在tcea～tsbb之間插入工序。設(shè)插入時(shí)段為設(shè)備R(i,4)的第k個(gè)空閑時(shí)段，則更新MM(R(i,4)).TS的步驟如下：首先，將MM(R(i,4)).TS的長(zhǎng)度增加2位；然后，從k空閑時(shí)段對(duì)應(yīng)的第2個(gè)數(shù)據(jù)起，將后面的數(shù)據(jù)后移2位，從而騰出兩個(gè)空位；最后，在兩個(gè)空位處分別填入待插入工序的設(shè)備調(diào)整開(kāi)始時(shí)刻和加工結(jié)束時(shí)刻。

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

3.8 計(jì)算適應(yīng)度

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

圖11 計(jì)算適應(yīng)度流程圖Fig.11 Flow of calculating the fitness

4 案例分析

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

表3 工件

表4 工藝流程

表5 設(shè)備

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

表7 周六需工作的日期

表8 周日需工作的日期

表9 計(jì)算參數(shù)

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

圖12 某次進(jìn)化過(guò)程Fig.12 An evolutionary process

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

圖14 設(shè)備甘特圖Fig.14 Gantt chart of the machines

序號(hào)任務(wù)工件工序設(shè)備設(shè)備代碼調(diào)整時(shí)間加工時(shí)間調(diào)整開(kāi)始時(shí)刻調(diào)整結(jié)束時(shí)刻加工開(kāi)始時(shí)刻加工結(jié)束時(shí)刻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ù)表)

序號(hào)任務(wù)工件工序設(shè)備設(shè)備代碼調(diào)整時(shí)間加工時(shí)間調(diào)整開(kāi)始時(shí)刻調(diào)整結(jié)束時(shí)刻加工開(kāi)始時(shí)刻加工結(jié)束時(shí)刻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ù)表)

序號(hào)任務(wù)工件工序設(shè)備設(shè)備代碼調(diào)整時(shí)間加工時(shí)間調(diào)整開(kāi)始時(shí)刻調(diào)整結(jié)束時(shí)刻加工開(kāi)始時(shí)刻加工結(jié)束時(shí)刻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道工序，分別在不同的設(shè)備上加工，因此可以提前進(jìn)行設(shè)備調(diào)整，當(dāng)上道工序完成加工時(shí)，可立即開(kāi)始下道工序的加工，采用這種安排方式在一定程度上縮短了生產(chǎn)周期。其他工件在安排工序時(shí)與工件4采用了相同的處理方式。

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

5 結(jié)語(yǔ)

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