改進(jìn)混沌遺傳算法尋優(yōu)敏捷供需鏈動(dòng)態(tài)調(diào)度時(shí)段

摘要：本文面向敏捷供需鏈動(dòng)態(tài)調(diào)度時(shí)段優(yōu)選方案設(shè)計(jì)，構(gòu)建以最低總成本為目標(biāo)的動(dòng)態(tài)調(diào)度模型；基于傳統(tǒng)遺傳算法的常見缺陷以及啟發(fā)式算法的局限性，提出面向敏捷供需鏈時(shí)段資源動(dòng)態(tài)調(diào)度全局尋優(yōu)的改進(jìn)混沌遺傳算法。首先設(shè)計(jì)分節(jié)式編碼，再利用隨機(jī)法與貪心法產(chǎn)生更優(yōu)良初始種群，提高染色體可行性及遺傳效果；選用優(yōu)先保留交叉以及貪心機(jī)制下的目標(biāo)導(dǎo)向變異，確保優(yōu)良基因繼承，改善遺傳操作；實(shí)施局部鄰域搜索以及混沌搜索以加快收斂；提出最優(yōu)解判別法。最后，實(shí)例驗(yàn)證算法有效性，不但取得全局最優(yōu)解，而且子體更加收斂，離散度更低。

關(guān)鍵詞：敏捷供需鏈；動(dòng)態(tài)調(diào)度；時(shí)段；遺傳算法；混沌搜索

中圖分類號(hào)：F274 文獻(xiàn)標(biāo)識(shí)碼：A

收稿日期：2013-05-13

作者簡(jiǎn)介：孔令夷（1977-），男，山東煙臺(tái)人，西安郵電大學(xué)管理工程學(xué)院副教授，研究方向：敏捷制造、供應(yīng)鏈管理、生產(chǎn)運(yùn)營(yíng)管理、計(jì)算智能、工業(yè)工程與管理。

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目，項(xiàng)目編號(hào)：71102149；國(guó)家社會(huì)科學(xué)基金項(xiàng)目，項(xiàng)目編號(hào)：11CJY064；工信部通信軟科學(xué)研究項(xiàng)目，項(xiàng)目編號(hào)：2013R01-2；教育部人文社會(huì)科學(xué)研究項(xiàng)目，項(xiàng)目編號(hào)：12YJC790084；陜西省教育廳專項(xiàng)科研計(jì)劃資助項(xiàng)目，項(xiàng)目編號(hào)：12JK0056；西安郵電大學(xué)青年教師科研基金項(xiàng)目，項(xiàng)目編號(hào)：ZL2011-22。 知識(shí)世紀(jì)已來臨，企業(yè)間競(jìng)爭(zhēng)升級(jí)為供需鏈間競(jìng)爭(zhēng)，產(chǎn)品制造模式和市場(chǎng)營(yíng)銷方式都發(fā)生實(shí)質(zhì)性轉(zhuǎn)變。全球化及不確定性客戶需求的外部市場(chǎng)環(huán)境，對(duì)供需鏈提出了敏捷性的客觀要求，敏捷供需鏈（Agile Supply Chain，簡(jiǎn)稱ASC）ASC成為全球供需鏈轉(zhuǎn)型升級(jí)的首選捷徑，以及商業(yè)界和理論界的近期研究熱點(diǎn)。作為新世紀(jì)供應(yīng)網(wǎng)絡(luò)的全新模式，ASC整合精益生產(chǎn)、并行工程等先進(jìn)制造技術(shù)及理念，在高度競(jìng)合、動(dòng)態(tài)多變的外部商業(yè)環(huán)境中，集成供應(yīng)商、制造商、服務(wù)商、外包商、經(jīng)銷商等成員企業(yè)，快速實(shí)時(shí)響應(yīng)外界商機(jī)和需求變化。ASC區(qū)別于傳統(tǒng)供應(yīng)鏈的最大特點(diǎn)是基于虛擬化運(yùn)作方式，快速動(dòng)態(tài)調(diào)度供應(yīng)鏈成員企業(yè)所有可用資源，包括資源組合、調(diào)整、配置及解散。若要成功調(diào)度供需鏈資源，不但需要ICT技術(shù)、現(xiàn)代管理方法、強(qiáng)大的網(wǎng)絡(luò)基礎(chǔ)等，而且時(shí)段等瓶頸資源調(diào)度技術(shù)也是必不可缺的前提要件，即在ASC的稀缺時(shí)段資源約束下，怎樣選擇、組織、配置ASC資源，確定有效的進(jìn)貨、生產(chǎn)、儲(chǔ)存、運(yùn)輸、銷售、服務(wù)協(xié)同調(diào)度計(jì)劃，以最低成本完成復(fù)雜多變的訂單作業(yè)。

一、相關(guān)研究述評(píng)

很多學(xué)者已展開ASC進(jìn)產(chǎn)存運(yùn)銷的調(diào)度研究，成果頗豐。在知網(wǎng)搜索主題為“敏捷供需鏈”及“調(diào)度”的2000年以來文獻(xiàn)有83篇；在EI數(shù)據(jù)庫中做同樣查新，得到外文61篇；在Springer數(shù)據(jù)庫中也做同樣查新，得到16篇；經(jīng)過比對(duì)，EI庫與Springer庫有5篇重復(fù)者，有效外文文獻(xiàn)合計(jì)72篇，因此中外文相關(guān)文獻(xiàn)共計(jì)155篇。經(jīng)過系統(tǒng)梳理，ASC調(diào)度研究分類如下：

1.運(yùn)籌規(guī)劃法。文獻(xiàn)[1]研究?jī)晒S構(gòu)成的ASC的產(chǎn)運(yùn)協(xié)同調(diào)度，運(yùn)用混合整數(shù)規(guī)劃求解運(yùn)能無約束條件下的最優(yōu)調(diào)度解。文獻(xiàn)[2]研究零產(chǎn)品庫存下MTO型ASC的產(chǎn)運(yùn)協(xié)同調(diào)度，求解了最優(yōu)生產(chǎn)路線及運(yùn)輸路徑。文獻(xiàn)[3]研究MTO型ASC的產(chǎn)運(yùn)一體化調(diào)度，構(gòu)建面向交貨期延遲違約費(fèi)、運(yùn)輸費(fèi)及加班費(fèi)最小化等多目標(biāo)的最優(yōu)動(dòng)態(tài)調(diào)度規(guī)劃模型，給出求解方法。文獻(xiàn)[4]研究倒行樹狀結(jié)構(gòu)ASC的供產(chǎn)運(yùn)動(dòng)態(tài)調(diào)度問題，基于生產(chǎn)運(yùn)輸批量和運(yùn)輸配送變量設(shè)計(jì)，構(gòu)造并探究總成本最低的供產(chǎn)運(yùn)動(dòng)態(tài)優(yōu)化調(diào)度模型，提出適宜有效的動(dòng)態(tài)規(guī)劃算法。文獻(xiàn)[5]評(píng)估MC模式下供應(yīng)鏈動(dòng)態(tài)調(diào)度的矛盾性，基于供應(yīng)鏈總收益和成員滿意的雙視角，分析供應(yīng)鏈動(dòng)態(tài)調(diào)度的收益偏好決策，建立非線性調(diào)度規(guī)劃模型，示例檢驗(yàn)了模型適用性。文獻(xiàn)[6]剖析大規(guī)模定制下ASC動(dòng)態(tài)調(diào)度的影響因素，開發(fā)建立有針對(duì)性性、適宜MC模式、隨機(jī)約束下、供需鏈調(diào)度優(yōu)化的動(dòng)態(tài)規(guī)劃模型，論述了優(yōu)化調(diào)度目標(biāo)的合理性，解釋優(yōu)化調(diào)度實(shí)現(xiàn)過程，對(duì)變量賦予隨機(jī)數(shù)值，仿真MC模式下復(fù)雜、多目標(biāo)、動(dòng)態(tài)優(yōu)化火車生產(chǎn)供應(yīng)鏈調(diào)度過程，經(jīng)驗(yàn)證效果理想，并展望其實(shí)踐應(yīng)用。文獻(xiàn)[7]研究面向確定性需求的多級(jí)ASC調(diào)度，構(gòu)建期量約束下的線性規(guī)劃模型，以高度柔性及精益性實(shí)現(xiàn)為目標(biāo)而開發(fā)兩階段調(diào)度貪婪算法。文獻(xiàn)[8]鑒于ASC復(fù)雜性以及其組成部分的生產(chǎn)系統(tǒng)規(guī)劃的過大計(jì)算量，引入一種生產(chǎn)總體規(guī)劃及確定最佳生產(chǎn)起始點(diǎn)的新方法——夾點(diǎn)分析法，通過混合供需數(shù)據(jù)而深刻理解ASC運(yùn)作過程，簡(jiǎn)化再計(jì)劃及快速?zèng)Q策，并提出混合整數(shù)規(guī)劃模型求得最優(yōu)調(diào)度解。實(shí)證分別取自單一產(chǎn)品以及單處理機(jī)生產(chǎn)的多產(chǎn)品，前者的最優(yōu)生產(chǎn)計(jì)劃用加法模型求得；對(duì)于后者，也給出一種算法以優(yōu)化多產(chǎn)品出產(chǎn)順序，其計(jì)算次數(shù)僅為傳統(tǒng)解法的1/6。

總第437期

孔令夷：改進(jìn)混沌遺傳算法尋優(yōu)敏捷供需鏈動(dòng)態(tài)調(diào)度時(shí)段

····

商 業(yè) 研 究

2013/092.遺傳算法。文獻(xiàn)[9]研究ASC模式下混凝土預(yù)拌站及施工地的短期動(dòng)態(tài)產(chǎn)運(yùn)調(diào)度，使用傳統(tǒng)遺傳算法（Traditional Genetic Algorithm，簡(jiǎn)稱TGA）求解交貨期剛性約束下的調(diào)度方案最優(yōu)解。文獻(xiàn)[10]研究ASC質(zhì)量兼容產(chǎn)運(yùn)調(diào)度問題，融入模糊理論構(gòu)建質(zhì)量及成本約束下的生產(chǎn)和運(yùn)輸一體化調(diào)度模型，該模型以模糊化交貨期客戶滿意度最優(yōu)為目標(biāo)函數(shù)，并提出了模型求解的遺傳算法。

3.其他元啟發(fā)式算法。除了遺傳算法以外，還發(fā)現(xiàn)不少其他算法用于ASC調(diào)度方案求解。文獻(xiàn)[11]設(shè)計(jì)供需鏈調(diào)度矛盾解決途徑，剖析動(dòng)態(tài)調(diào)度機(jī)制，采用蟻群算法尋優(yōu)供需鏈運(yùn)作動(dòng)態(tài)調(diào)度。文獻(xiàn)[12]剖析拉式供需鏈動(dòng)態(tài)調(diào)度本質(zhì)，指出調(diào)度瓶頸，引入針對(duì)性改進(jìn)蟻群算法，數(shù)值實(shí)驗(yàn)顯示尋優(yōu)性較強(qiáng)。文獻(xiàn)[13]研究多工廠構(gòu)成的ASC的產(chǎn)運(yùn)動(dòng)態(tài)調(diào)度，提出引入并行工程以實(shí)現(xiàn)訂單的準(zhǔn)時(shí)生產(chǎn)、及時(shí)交貨，面向零排隊(duì)時(shí)間及零空閑時(shí)間，設(shè)計(jì)啟發(fā)式算法尋優(yōu)無限產(chǎn)能條件下的動(dòng)態(tài)調(diào)度方案。文獻(xiàn)[14] 研究面向大規(guī)模定制的ASC集成調(diào)度問題，以信息及過程集成作為調(diào)度目標(biāo)，建構(gòu)整合供應(yīng)商評(píng)選及外協(xié)商排序的綜合調(diào)度優(yōu)化模型，開發(fā)了穩(wěn)定且有效求解的蟻群算法。文獻(xiàn)[15]構(gòu)建面向多個(gè)不同地點(diǎn)市場(chǎng)的單機(jī)生產(chǎn)、單個(gè)運(yùn)輸工具的產(chǎn)運(yùn)銷協(xié)同調(diào)度模型，調(diào)度目標(biāo)是作業(yè)到達(dá)累計(jì)時(shí)間最小化，該問題被證明是強(qiáng)NP難問題，開發(fā)了多項(xiàng)式時(shí)間算法。

4.其他定性方法。文獻(xiàn)[16]分析供需鏈協(xié)同調(diào)度過程及相應(yīng)使能模型，論述大規(guī)模定制環(huán)境下協(xié)同供需鏈調(diào)度模式及實(shí)施架構(gòu)，但是缺乏對(duì)調(diào)度技術(shù)的探究。文獻(xiàn)[17]剖析ASC制約因素及追究其復(fù)雜矛盾性，系統(tǒng)性描述動(dòng)態(tài)優(yōu)化調(diào)度的三方面瓶頸環(huán)節(jié)，評(píng)述因素、矛盾及瓶頸之間的交互關(guān)系，基于此，設(shè)計(jì)優(yōu)化調(diào)度對(duì)策，然而并未給出有效的定量計(jì)算方法。

對(duì)以上幾類文獻(xiàn)進(jìn)行歸納及分析評(píng)鑒，都能發(fā)現(xiàn)存在明顯的局限性。首先透析運(yùn)籌規(guī)劃法，所求出的調(diào)度解方案與車間現(xiàn)場(chǎng)的單元調(diào)度偏差太大；僅僅采用靜態(tài)、單一的調(diào)度方法來解決動(dòng)態(tài)、多變的ASC調(diào)度問題，效果必然大打折扣；適用性較差，只能得到非常有限的應(yīng)用價(jià)值，而不能滿足ASC動(dòng)態(tài)調(diào)度的實(shí)際需要。其次，TGA存在早熟收斂及冗余迭代的常見固有缺陷，導(dǎo)致求解效率低，而且經(jīng)驗(yàn)證只能獲得局部最優(yōu)解，無法獲得全局最優(yōu)解。環(huán)境如果發(fā)生變化，傳統(tǒng)算法就顯得無能為力，還必須考慮更高級(jí)算法。再次，啟發(fā)式算法都局限于改善ASC調(diào)度的局部環(huán)節(jié)，并不能真正解決TGA的早熟缺陷，也就不能確保真正求得ASC全局性調(diào)度最優(yōu)解；而且它僅適用于有限條件，如無限產(chǎn)能、動(dòng)態(tài)種群、距離對(duì)稱、大規(guī)模定制等，其局限性較為明顯。最后一類屬于定性方法，不能給出最優(yōu)解，實(shí)用性不足。而且，已有文獻(xiàn)大多致力于供需鏈集成調(diào)度模式、機(jī)制及管理策略，對(duì)作為關(guān)鍵性、瓶頸性、核心性資源的可調(diào)度時(shí)段優(yōu)化調(diào)度研究尚顯不足，亟待深入探究。ASC動(dòng)態(tài)優(yōu)化調(diào)度的實(shí)質(zhì)是怎樣配置供需鏈成員企業(yè)的可調(diào)度時(shí)段，使其以最小供需鏈成本獲得最大產(chǎn)出。對(duì)于調(diào)度時(shí)段的形式，已有研究大致有兩種選擇可參照：其一是連續(xù)時(shí)段，各生產(chǎn)商可調(diào)度時(shí)段不能分割，基于單件生產(chǎn)時(shí)間就簡(jiǎn)單得出產(chǎn)出量，這種方法局限性明顯，如果單件加工時(shí)間與整個(gè)時(shí)段不構(gòu)成理想的倍數(shù)關(guān)系，則會(huì)造成時(shí)段資源浪費(fèi)；其二是ASC的各企業(yè)或車間所轄若干時(shí)段為已知，一個(gè)時(shí)段能且僅能完成一個(gè)生產(chǎn)工序，產(chǎn)出一件在制中間品（加工作業(yè)）或部件（部裝作業(yè)）或制成品（裝配作業(yè)）。本文擬選取后一種情形，以最大程度地提高ASC的精益性、敏捷性、資源配置效率及其總投入產(chǎn)出比。

近些年越來越多學(xué)者采用混沌論思想，大幅度增強(qiáng)算法搜尋最優(yōu)解的能力，確保優(yōu)良染色體基因的嚴(yán)格遺傳繼承，本文就是要通過引入混沌搜索的尋優(yōu)技術(shù)能更接近ASC動(dòng)態(tài)調(diào)度時(shí)段的現(xiàn)實(shí)情境，更貼切地表現(xiàn)并符合復(fù)雜多變、不確定性、隨機(jī)性的外部商機(jī)及需求，能生成隨機(jī)性強(qiáng)的優(yōu)良種群；本文還將利用混沌尋優(yōu)法的起始態(tài)敏感性優(yōu)良特性，應(yīng)用貪婪機(jī)制改進(jìn)算法的種群初始化、起始編碼方案，以圖實(shí)現(xiàn)混沌技術(shù)從一開始就能發(fā)揮最大效能；針對(duì)當(dāng)前被廣泛用于算法改進(jìn)的 Logistic 混沌法的均衡性差、收斂速度和精確度不滿意的現(xiàn)狀，本文擬對(duì)混沌搜索實(shí)施優(yōu)化，采納更優(yōu)的冪函數(shù)載波混沌搜索技術(shù)，優(yōu)化混沌向量，提升混沌尋優(yōu)速度； Bierwirth等基于各種算法數(shù)值實(shí)驗(yàn)比較研究，開發(fā)優(yōu)先保留交叉法（Precedence Preservation Crossover，PPX），極大地提升TGA的全局尋優(yōu)性能；最后，基于貪心法執(zhí)行啟發(fā)式目標(biāo)導(dǎo)向變異操作（Goal Orientation Mutation，GOM），同步匹配于混沌搜索的隨機(jī)性，確保優(yōu)良基因保留傳承，進(jìn)一步提高算法的隨機(jī)尋優(yōu)性。因此，本文基于對(duì)供需鏈生產(chǎn)、儲(chǔ)存、運(yùn)輸調(diào)度研究文獻(xiàn)述評(píng)，對(duì)ASC動(dòng)態(tài)時(shí)段調(diào)度建模，基于混沌理論及貪婪機(jī)制，開發(fā)一種對(duì)TGA全過程、系統(tǒng)性改進(jìn)的高級(jí)前沿算法——改進(jìn)混沌遺傳算法（Improved Chaos Genetic Algorithm，簡(jiǎn)稱ICGA），對(duì)編碼方案、種群初始化、遺傳相關(guān)算子操作、搜索操作、適值函數(shù)設(shè)置、選擇操作、最優(yōu)解判定等作出全面、整體、徹底改進(jìn)，克服TGA因過度依賴參數(shù)和算子、早熟收斂、冗余迭代而無法得到ASC動(dòng)態(tài)調(diào)度全局最優(yōu)的缺點(diǎn)，也彌補(bǔ)已有大量文獻(xiàn)拘泥于某種單一算法而不能實(shí)現(xiàn)ASC全鏈條優(yōu)化的不足，最后采用制造業(yè)實(shí)例檢驗(yàn)CGA在時(shí)段調(diào)度方面的相對(duì)高效性。

相對(duì)于前述以往的調(diào)度算法或方法，本文提出ICGA所表現(xiàn)出的無可替代優(yōu)勢(shì)在于：復(fù)雜、不確定、隨機(jī)情境下種群個(gè)體的高智能性、快速收斂、復(fù)雜問題簡(jiǎn)單化、易于操作、變量設(shè)置較少、局部?jī)?yōu)化與全局優(yōu)化相結(jié)合而保持統(tǒng)一化等。在中國(guó)知網(wǎng)數(shù)據(jù)庫再次對(duì)ICGA作文獻(xiàn)查新，以“混沌遺傳算法”為篇名，2008年至今刊載于核心期刊僅有33篇，說明該領(lǐng)域研究明顯不足、極其缺乏、亟待推進(jìn)。因此更有必要展開ASC動(dòng)態(tài)調(diào)度的ICGA研究，以彌補(bǔ)不足，嘗試突破。

二、ASC動(dòng)態(tài)調(diào)度時(shí)段模型構(gòu)建

（一）問題提出

ASC動(dòng)態(tài)調(diào)度時(shí)段問題是指沿ASC方向的生產(chǎn)、運(yùn)輸、銷售型上中下游企業(yè)根據(jù)復(fù)雜多變的市場(chǎng)商機(jī)快速優(yōu)選組合成員企業(yè)，敏捷地構(gòu)建動(dòng)態(tài)聯(lián)盟或虛擬企業(yè)，響應(yīng)大規(guī)?？蛻舻膫€(gè)性化、多元化需求，聯(lián)合制定進(jìn)、產(chǎn)、存、運(yùn)、銷協(xié)同整合的動(dòng)態(tài)調(diào)度計(jì)劃，確保具有可調(diào)用時(shí)段作業(yè)特征的供需鏈各方協(xié)同運(yùn)作，實(shí)現(xiàn)ASC全局優(yōu)化。假設(shè)ASC涉及多家企業(yè)的組合協(xié)作，下轄若干個(gè)生產(chǎn)車間，分別或共同執(zhí)行某類加工裝配型產(chǎn)品的所有組件加工工序，最后完成總裝給客戶交貨。某一道加工工序可能有多家候選企業(yè)或候選車間都能勝任，某家企業(yè)或車間也能為多家其他企業(yè)或車間提供外協(xié)加工、代加工或供應(yīng)生產(chǎn)用零部件。因?yàn)槠髽I(yè)或車間的運(yùn)輸距離、時(shí)間及運(yùn)輸配送物料價(jià)值量的不同，所以ASC內(nèi)部成員企業(yè)的運(yùn)輸成本各有不同；由于各生產(chǎn)車間的可用調(diào)度時(shí)段、加工對(duì)象價(jià)值量有異，因此企業(yè)或車間的生產(chǎn)及儲(chǔ)存成本也各不相同。而且，完成下道組件加工工序的企業(yè)或車間唯有所有上道（游）工序完工后才能進(jìn)行生產(chǎn)，即該類產(chǎn)品屬于成套性加工性質(zhì)。供需鏈的企業(yè)或車間之間運(yùn)輸采用順序移動(dòng)方式：上道工序按照客戶訂單將所有組件加工完畢后，由運(yùn)輸商一次性地專項(xiàng)運(yùn)輸配送給負(fù)責(zé)下道工序的企業(yè)或車間，運(yùn)輸批量等于產(chǎn)品訂貨數(shù)量。

ASC調(diào)度時(shí)段問題可表述為：給定ASC的已有企業(yè)或車間分別負(fù)責(zé)加工的組件種類、產(chǎn)能、可用調(diào)度時(shí)段、相互間運(yùn)輸時(shí)間及各種成本發(fā)生系數(shù)等，為完成產(chǎn)量為Q的產(chǎn)品生產(chǎn)、儲(chǔ)存、運(yùn)輸作業(yè)任務(wù)，在確定交貨期D的約束下，尋求各組件在不同企業(yè)或車間的調(diào)度時(shí)段最優(yōu)選擇方案，劃定ASC企業(yè)或車間之間的分工協(xié)作及供求關(guān)系，從而使ASC以最低的總運(yùn)營(yíng)成本最大限度地滿足動(dòng)態(tài)需求，敏捷地捕捉動(dòng)態(tài)商機(jī)，為各成員企業(yè)或車間獲得最大供需鏈總收益。綜上，ASC調(diào)度時(shí)段問題的本質(zhì)就是可調(diào)度時(shí)段優(yōu)選及重組，可以根據(jù)運(yùn)籌規(guī)劃法建模，以及借助聚類分析法解析。

（二）調(diào)度時(shí)段優(yōu)化模型構(gòu)建

設(shè)計(jì)以下參量：設(shè)ASC需完成的成品產(chǎn)量為Q，交貨期為D；ASC容納有n個(gè)企業(yè)或生產(chǎn)車間，用集合W表示，W={W1，…，Wi，…，Wj，…，Wn}，其中1≤i

式（1）第一部分是ASC的儲(chǔ)存成本，Bj=minBjk/xjk是車間j的第一個(gè)被調(diào)度時(shí)段的開工時(shí)刻，易知Bjk0=+∞，B0=D，F(xiàn)i=maxFikxik是車間i的最后一個(gè)被調(diào)度時(shí)段的完工時(shí)刻。式（1）第二部分是ASC的生產(chǎn)成本，第三部分是ASC的運(yùn)輸成本。約束條件式（2）是加工量約束，表示第h道工序耗用全部勝任其車間的可用調(diào)度時(shí)段總個(gè)數(shù)，即第h道工序的加工總次數(shù)，必等于成品產(chǎn)量Q。式（3）是ASC各關(guān)聯(lián)車間調(diào)度時(shí)段均衡性及匹配性約束，表示第h道工序耗用車間j的調(diào)度時(shí)段數(shù)量等于全部勝任其上道工序車間提供給車間j的用于第h道工序加工對(duì)象組件的相關(guān)零部件加工的調(diào)度時(shí)段數(shù)量。式（4）是成套性加工約束，表示車間j的最早開始生產(chǎn)時(shí)間必然大于其所有上道工序車間的完成加工時(shí)間再加上中間品運(yùn)輸時(shí)間的最晚者。式（5）是按時(shí)交貨約束，表示總裝車間1的最遲完成時(shí)間必須小于客戶交貨期，確保ASC準(zhǔn)時(shí)給客戶交貨。式（6）是決策變量約束，表示當(dāng)車間i的時(shí)段k未被調(diào)用，那么時(shí)段k就不會(huì)生產(chǎn)組件給其他車間，反之反亦，必有且僅有唯一的下游車間j接收時(shí)段k完工的組件。式（7）也是決策變量約束，表示兩個(gè)車間若沒有運(yùn)輸時(shí)間，則不存在上下游供求關(guān)系。

三、ASC動(dòng)態(tài)調(diào)度時(shí)段的改進(jìn)混沌遺傳算法

通過ASC動(dòng)態(tài)調(diào)度時(shí)段模型，能夠發(fā)現(xiàn)該問題復(fù)雜性極高：不但選擇供需鏈協(xié)作方，還要選擇各協(xié)作方的調(diào)用時(shí)段；不但確保組件生產(chǎn)商可調(diào)用時(shí)段滿足下游裝配需求，還要確保組件生產(chǎn)商及時(shí)從上游供貨商處獲取物料而正常開工；不但要平衡產(chǎn)能與需求計(jì)劃，還有平衡儲(chǔ)運(yùn)能力；不但控制生產(chǎn)成本，還要管控運(yùn)輸及儲(chǔ)存成本。加之眾多期量約束、調(diào)度時(shí)段可得性約束等，顯而易見，根據(jù)理論信息學(xué)中的信息復(fù)雜度理論，該問題具有NPC計(jì)算強(qiáng)復(fù)雜性，是典型的NP難問題。本文擬基于混沌理論應(yīng)用ICGA求解得出ASC動(dòng)態(tài)調(diào)度時(shí)段最優(yōu)方案，選用優(yōu)于二進(jìn)制的分節(jié)式時(shí)段編碼方法，引入與混沌搜索的高隨機(jī)性相匹配的貪婪法，再執(zhí)行強(qiáng)隨機(jī)性的順序交叉、移位變異、局部鄰域及混沌搜索操作，采用輪賭盤法進(jìn)行染色體串選擇，迅速求得ASC最優(yōu)調(diào)度時(shí)段決策方案。

（一）編碼方案

常用的二進(jìn)制編碼方式在時(shí)段調(diào)度中有明顯缺陷：碼長(zhǎng)過大，嚴(yán)重冗余，極大地影響了算法運(yùn)行效率，因而設(shè)計(jì)有效的分節(jié)式時(shí)段編碼方案，結(jié)合時(shí)段號(hào)、車間號(hào)及組件號(hào)三個(gè)十進(jìn)制碼而得出。

（二）初始化種群

初始種群的優(yōu)良性直接關(guān)系到混沌尋優(yōu)操作成效，可謂極其關(guān)鍵。隨機(jī)法不能確保其滿足大量的約束條件（如式2-8），易混雜許多無效個(gè)體，影響算法效率。擬利用貪心機(jī)制產(chǎn)生更多較優(yōu)染色體，改進(jìn)初始種群質(zhì)量，即選取若干局部最優(yōu)的可調(diào)度時(shí)段染色體納入到初始種群中，以包括貪心法的局部最優(yōu)解和隨機(jī)法的其他個(gè)體。

（三）交叉變異操作

GOM源自步步尋優(yōu)的貪心機(jī)理，如果父串中能找出兩個(gè)相鄰基因的生產(chǎn)、儲(chǔ)存及運(yùn)輸?shù)目偣?yīng)鏈成本是父串中所有相鄰基因間總成本最大者，則這兩者相鄰就很可能不太合理。處理方法是：任選二者其中一個(gè)基因與其他隨機(jī)生成的第三個(gè)基因?qū)φ{(diào)，也就是以總的供需鏈成本目標(biāo)函數(shù)最小化為導(dǎo)向，若對(duì)調(diào)后的新染色體串具有更高的適應(yīng)度，則變異操作成功，反之，再次更換一個(gè)隨機(jī)的基因與之對(duì)調(diào)，試圖增大其適應(yīng)度值。多次變異操作后的染色體串還不能真正獲取比原先父串更高的適應(yīng)度值，就針對(duì)二者其中另一個(gè)基因?qū)嵤┥鲜鐾耆瑯拥呐c隨機(jī)基因?qū)φ{(diào)操作，再次試圖提高父串被變異操作后的適應(yīng)度值。假如還未取得實(shí)效，根據(jù)啟發(fā)式思想，只好判定二者相鄰是合理的存在，但是還可以再考慮對(duì)原先二者的基因?qū)φ{(diào)，若對(duì)調(diào)后適應(yīng)度值提高，則用新串替換原串。反之，若在前述任一個(gè)環(huán)節(jié)取得了適應(yīng)度值提高的實(shí)效，即被變異操作后的串的適應(yīng)度值高于原父串，則替換父串，子串由此被生成。不難看出，GOM比對(duì)換、移位、插入、反序等變異操作能更多保留染色體內(nèi)基因的邏輯關(guān)系及合理順序，使得父串的優(yōu)點(diǎn)被遺傳下去。

（四）局部鄰域搜索及混沌搜索

5.若達(dá)到停止條件，即最優(yōu)調(diào)度時(shí)段解的判定條件，獲取最高適應(yīng)度值，則結(jié)束混沌搜索，得出最優(yōu)解x*ik ；反之，回到式（9） ，使g增加1，再算出n個(gè)新數(shù)，繼續(xù)向下操作。

（五）適應(yīng)度函數(shù)及選擇操作

適應(yīng)度值是衡量染色體質(zhì)量的關(guān)鍵參數(shù)，因本文追求總供需鏈成本最小化，所以，令適應(yīng)度函數(shù)：

其中，α是常量，ci為各車間的可調(diào)度時(shí)段數(shù)量，n為供需鏈的車間數(shù)量，m為加工組件的數(shù)量，z為實(shí)際發(fā)生成本，即目標(biāo)函數(shù)值。

生物物種不斷向高級(jí)演化的動(dòng)力機(jī)制就在于大自然選擇?；谌旧w適應(yīng)度評(píng)判，就能區(qū)分其優(yōu)良與否，即適應(yīng)性的高低。適應(yīng)度值較高者更有可能優(yōu)先被選擇，其在子代中的比例也將逐代增大，從而子代也將在演化過程中持續(xù)地優(yōu)于父代。本文擬用輪賭盤法選擇調(diào)度時(shí)段染色體個(gè)體，最大限度地保留最佳基因片段，保證算法的較高尋優(yōu)性。

TGA運(yùn)行過程難免有很多不可行解，浪費(fèi)CPU資源，拖延尋優(yōu)時(shí)間，致使效率不堪。因此擬對(duì)最優(yōu)解作出以下判定和鑒別：

先算得zmax=maxi，j，kz（i，j，k），根據(jù)決策變量約束，各企業(yè)車間的調(diào)度時(shí)段為有限資源，存在不可用時(shí)段，非調(diào)度范圍內(nèi)，而且企業(yè)或車間之間的供求關(guān)系也是受限定的，因此對(duì)包括不可調(diào)度時(shí)段或不存在上下游供求關(guān)系的ASC調(diào)度時(shí)段染色體串的總運(yùn)作成本設(shè)置為zp=z（ip，jp，kp）=λ*zmax+1，λ為足夠大的正整數(shù)，若子串中含有不可調(diào)度時(shí)段或不存在供求關(guān)系的基因，必有下式（11）存在：

即該子串的適應(yīng)度值最小，很快被淘汰掉，也就去除不滿足有限調(diào)度時(shí)段約束及供求關(guān)系約束的不可行最優(yōu)解出現(xiàn)的可能情形，以確保不破壞算法尋優(yōu)的可行性，即求出的最優(yōu)調(diào)度時(shí)段解必定是可行的。反之反亦，下式（12）一旦滿足，必然子串可行可信，若是最優(yōu)解，則可以成立而輸出?？傊?，若ICGA求得ASC可調(diào)度時(shí)段最優(yōu)解的適應(yīng)度值小于 （六）算法步驟

1.初始設(shè)定。包括常數(shù)、最大迭代次數(shù)、交叉變異概率Pm等。

2.染色體編碼。采用更有效的分節(jié)式時(shí)段編碼方案，窮盡所有染色體串。

3.設(shè)計(jì)初始群。綜合隨機(jī)法與貪心法生成初始種群。

4.交叉、變異及搜索。設(shè)置Pc概率作染色體交叉，以Pm概率作變異，還要作局部鄰域搜索、改進(jìn)混沌搜索。

5.選擇。以適應(yīng)度值函數(shù)f為評(píng)判依據(jù)，運(yùn)用輪賭盤法作選擇，以保優(yōu)質(zhì)染色體串，求出適應(yīng)性最強(qiáng)（即ASC總運(yùn)作成本最低）的染色體，即為本問題的最優(yōu)解。

6.核驗(yàn)最優(yōu)解。以式（12） 核驗(yàn)該最優(yōu)解的可行性，代入后成立即為可行，輸出；反之則棄用，回到第3步重新運(yùn)行該算法。

四、實(shí)證分析

通信制造業(yè)是我國(guó)著力振興、重點(diǎn)發(fā)展的產(chǎn)業(yè)之一，已經(jīng)形成產(chǎn)業(yè)密集發(fā)展態(tài)勢(shì)，能帶動(dòng)區(qū)域經(jīng)濟(jì)迅速發(fā)展。為了提升該產(chǎn)業(yè)整體競(jìng)爭(zhēng)力，加快其轉(zhuǎn)型升級(jí)步伐，有必要盡快構(gòu)建實(shí)力較強(qiáng)、面向全球化的通信設(shè)備ASC以及供產(chǎn)存運(yùn)銷動(dòng)態(tài)一體化調(diào)度管理體系。因此，本文選取在我國(guó)代表性通信設(shè)備ASC展開實(shí)證研究，來驗(yàn)證該模型的有效性和可行性。

以成品E（End Product，最終產(chǎn)品）為例，其組件G（Group Part，群組工件）的相關(guān)需求比例均為1，即1個(gè)成品E分別需要1個(gè)G4和G5組裝而成，其余依次類推，見圖1。圖中方框內(nèi)代 為了驗(yàn)證ICGA的優(yōu)勢(shì)，將其與文獻(xiàn)[20]的啟發(fā)式算法HA算法進(jìn)行同等條件下數(shù)值實(shí)驗(yàn)比較，見表3。ICGA除了運(yùn)行時(shí)間略長(zhǎng)以外，其余性能都明顯高出HA，改進(jìn)率都在20%左右，尤其是ICGA求解平均值更是優(yōu)于HA接近30%，實(shí)現(xiàn)了求解的改進(jìn)效果。再比較ICGA與HA的標(biāo)準(zhǔn)差，前者的離散度低，優(yōu)良子體更多。這主要源于：其一，ICGA對(duì)種群求解過程引入隨機(jī)特性，初始種群質(zhì)量?jī)?yōu)于HA；其二，結(jié)合混沌思想進(jìn)行搜索操作，使得改進(jìn)算法的尋優(yōu)性更強(qiáng)，子體收斂更快，總之，本文的ICGA更有效，克服了TGA的早熟收斂及冗余迭代缺陷，也解決了現(xiàn)有啟發(fā)式算法的有限適用性、實(shí)用性不足的問題。

五、結(jié)束語

以發(fā)展演進(jìn)的眼光來看，當(dāng)今及今后日益復(fù)雜多變的商業(yè)環(huán)境下，ASC動(dòng)態(tài)調(diào)度時(shí)段優(yōu)選策略務(wù)必順從追求速度、柔性及創(chuàng)新性的新型ASC運(yùn)營(yíng)模式，并且作為有機(jī)而不可分割的一部分被納入到整個(gè)ASC管理體系中去。ASC動(dòng)態(tài)調(diào)度時(shí)段需要面向不確定性、動(dòng)態(tài)性的訂單需求，優(yōu)選并重組所有可調(diào)度時(shí)段資源，高效開展生產(chǎn)、儲(chǔ)存及運(yùn)輸作業(yè)活動(dòng)。本文構(gòu)建精益型ASC動(dòng)態(tài)調(diào)度時(shí)段模型，考慮了動(dòng)態(tài)性訂單的工藝路線因素，整合各車間產(chǎn)能和加工工藝，更貼近于供需鏈中上下游車間生產(chǎn)運(yùn)行的實(shí)際情形，彌補(bǔ)了以往研究在工藝方面的偏頗性缺陷，明顯能提升ASC的響應(yīng)能力。我國(guó)通信制造業(yè)的實(shí)證研究證實(shí)了文中ASC動(dòng)態(tài)調(diào)度時(shí)段優(yōu)化算法的有效性、可行性、靈活簡(jiǎn)便性以及可擴(kuò)展性。但是，今后仍有待于采用更多類型的ASC案例來檢驗(yàn)ICGA的求解功效，探索怎樣使用更少的迭代次數(shù)獲取最優(yōu)調(diào)度解的途徑，進(jìn)一步加速子體遺傳及優(yōu)化收斂；而且，求解大規(guī)模分布式ASC車間動(dòng)態(tài)調(diào)度時(shí)段的高級(jí)前沿智能算法也需要探究；在最優(yōu)調(diào)度解不符合產(chǎn)能及時(shí)間等約束情況下如何調(diào)整糾錯(cuò)也是今后的研究難點(diǎn)和重點(diǎn)。

參考文獻(xiàn)：

[1] De Matta R，Miller T. Production and inter-facility transportation scheduling for a process industry[J].European Journal of Operational Research，2007，158（1）：72-88.

[2] Chen P. Integrating production and transportation scheduling in a make-to-order environment[D].Cornell University，2000.

[3] Zbayraka M O，Theopisti C P. A flexible and adaptable planning and control system for an MTO supply chain system[J]. Robotics and Computer-Integrated Manufacturing，2006，22（5-6）：557-565.

[4] Hall N G，Potts C N. Supply chain scheduling：Batch and delivery[J]. Operations Research，2003，51（4）：566-584.

[5] 姚建明，蒲云，張秀敏. 基于偏好決策的MC模式下供應(yīng)鏈調(diào)度優(yōu)化[J]. 中國(guó)管理科學(xué)，2005，13（5）：54-60.

[6] 姚建明，周國(guó)華.大規(guī)模定制模式下供應(yīng)鏈計(jì)劃調(diào)度優(yōu)化分析[J].管理科學(xué)學(xué)報(bào)，2003，6（5）：58-64.

[7] 王建華，李南，郭慧.敏捷供應(yīng)鏈靜態(tài)調(diào)度模型及其貪婪算法[J].計(jì)算機(jī)應(yīng)用，2010，30（3）：846-849.

[8] Singhvia，Madhavan K P，Shenoy U V. Pinch analysis for aggregate production planning in supply chains[J].Computers and Chemical Engineering，2004，28（6-7）：993-999.

[9] Naso D，Surico M. Genetic algorithms for supply-chain scheduling：A case study in the distribution of ready-mixed concrete[J].European Journal of Operational Research，2007，177（3）：2069-2099.

[10] 王瑋.敏捷供應(yīng)鏈質(zhì)量兼容生產(chǎn)計(jì)劃模型與算法[J].系統(tǒng)工程理論與實(shí)踐，2005（7）：75-80.

[11] 姚建明，劉麗文，蒲云.MC模式下供應(yīng)鏈動(dòng)態(tài)調(diào)度的蟻群尋優(yōu)分析[J].管理科學(xué)學(xué)報(bào)，2007，10（3）：7-14.

[12] 姚建明，張秀敏，劉麗文. 基于改進(jìn)螞蟻算法的拉動(dòng)式供應(yīng)鏈動(dòng)態(tài)調(diào)度分析[J]. 中國(guó)管理科學(xué)，2006，14（3）：20-26.

[13] Garcia J M，Lozano S，Canca D. Coordinated scheduling of production and delivery from multiple plants[J]. Robotics and Computer-Integrated Manufacturing，2004，20（3）：191-198.

[14] 孫靖，林杰.基于蟻群算法的大規(guī)模定制供應(yīng)鏈調(diào)度優(yōu)化研究[J].計(jì)算機(jī)應(yīng)用，2006，26（11）：2631-2634.

[15] Lic L，Vairaktarakis G L，Lee C. Machine scheduling with deliveries to multiple customer locations[J]. European Journal of Operational Research，2005，164（1）：39-51.

[16] 姚建明，張秀敏，劉麗文.面向供應(yīng)鏈的MC計(jì)劃調(diào)度功能模塊運(yùn)作研究[J].工業(yè)工程，2007，10（1）：25-30.

[17] 姚建明，劉麗文.MC下供應(yīng)鏈調(diào)度的制約因素及主導(dǎo)矛盾分析[J].工業(yè)工程，2007，10（5）：15-19.

[18] BIERWIRTH C，MATTFELD D，KOPFER H. On permutation representations for scheduling problems[C]//Proceedings of the 4th International Conference on Parallel Problem Solving from Nature. Berlin，Germany：Springer，1996：310-318.

[19] 葛宏偉.基于計(jì)算智能的若干優(yōu)化問題研究[D].長(zhǎng)春：吉林大學(xué)，2006.

[20] Asano M，Ohta H. A heuristic for job shop scheduling to minimize total weighted tardiness[J].Computer & Industrial Engineering，2002，42（2-4）：137-147.