趙宏觀，杜百崗，郭順生

(1.唐山海港中材裝備制造有限公司，河北 唐山 063000；2.武漢理工大學 機電工程學院，湖北 武漢 430070)

在建材裝備制造企業(yè)中，由于建材裝備的大型化和復雜性，導致裝備產(chǎn)品的體積龐大、零部件眾多、生產(chǎn)周期長[1]。目前，國內(nèi)的建材裝備行業(yè)已經(jīng)基本飽和，建材裝備制造企業(yè)的項目大部分針對國外，而裝備產(chǎn)品的大型化和長周期，使得裝備交付給項目業(yè)主的難度加大，對于一個中等規(guī)模的建材裝備制造企業(yè)，其年產(chǎn)量在1萬噸左右，無法采用陸運或空運等快捷的運輸方式，一般采用海運的方式，但海運的交付周期一般在1～2個月，甚至更長的時間。一方面，建材裝備制造企業(yè)需要按期完成各項目業(yè)主的制造任務(wù)，保證建材裝備的按期交付；另一方面由于各項目船期的不同，決策者需要根據(jù)不同的船期來制定相應(yīng)的制造任務(wù)計劃。船期的延誤可能導致建材裝備交付的延遲在幾個月以上，嚴重影響業(yè)主項目的啟動，而這一延誤對于項目業(yè)主的損失重大，日損失收益可能高達數(shù)十萬甚至上百萬，這不僅會降低建材裝備制造企業(yè)的信譽，還面臨著因延期交付導致業(yè)主的高額索賠。因此，制定合理的建材裝備制造任務(wù)調(diào)度計劃十分迫切。

基于裝箱單的建材裝備制造任務(wù)調(diào)度問題的本質(zhì)是車間作業(yè)調(diào)度問題(job-shop scheduling problem，JSP)。目前，針對JSP問題，國內(nèi)外進行了大量的研究。李啟銳等針對注塑生產(chǎn)車間作業(yè)調(diào)度，提出“歸模”的方法減少生產(chǎn)制造時間[2]。張飛等建立了最小化加工時間的車間調(diào)度模型，采用混沌粒子群算法進行求解[3]。戰(zhàn)紅等采用工序矩陣編碼對染色體進行編碼，求解優(yōu)化作業(yè)調(diào)度問題[4]。Li等采用遺傳算法對虛擬可重構(gòu)的制造單元進行作業(yè)計劃調(diào)度[5]。王冰等采用三角模糊數(shù)來求解梯形軟交貨期下的車間作業(yè)調(diào)度問題[6]。Zhang等采用直覺模糊集來解決車間作業(yè)調(diào)度問題[7]。賀仁杰等采用知識型協(xié)同演化方法求解柔性車間作業(yè)調(diào)度，該方法的特點是通過資源的競爭和信息共享推進算法的協(xié)同進化[8]。丁雷等研究了多品種、變批量下工時不確定車間作業(yè)任務(wù)的動態(tài)調(diào)度問題[9]。這些研究取得了具有借鑒意義的成果，但是針對建材裝備制造企業(yè)中基于裝箱單的制造任務(wù)調(diào)度問題仍然需要進一步研究。筆者以建材裝備制造企業(yè)為背景，對基于裝箱單的建材裝備制造任務(wù)以最小化船期延誤和總成本為目標構(gòu)建優(yōu)化調(diào)度模型，并采用遺傳算法進行求解。

1 基于裝箱單的建材裝備制造過程

由于建材裝備的體積龐大，生產(chǎn)周期長，為了提高建材裝備的交付周期，必須在制造階段考慮建材裝備的運輸。在這一過程中，通過裝箱單對制造任務(wù)進行調(diào)度和進度控制，保證各項目的船期。裝箱單是技術(shù)部在對設(shè)計部門提供的產(chǎn)品BOM進行轉(zhuǎn)化的基礎(chǔ)上，由生產(chǎn)部、質(zhì)量部和儲運部等對裝箱單信息的進一步完善而形成的指導性文件，其包含了制作內(nèi)容、制作工程量、尺寸信息、裝箱標識、制作班組等信息，是項目最終交貨的依據(jù)，也是制造過程中計劃制定、任務(wù)分配以及工程結(jié)算的依據(jù)。在建材裝備制造企業(yè)中，基于裝箱單的制造過程流程如圖1所示。根據(jù)業(yè)主項目的具體需求，由設(shè)計部門進行產(chǎn)品的設(shè)計，將圖紙交由技術(shù)部進行技術(shù)準備，考慮制作、裝配、發(fā)運等要求，形成指導性的裝箱單文件，生產(chǎn)部和儲運部按照裝箱單、項目交付期、船期等分別制定生產(chǎn)計劃和發(fā)運計劃，同時生產(chǎn)制作可能存在廠內(nèi)和外協(xié)兩種方式，需要進行合理的制造任務(wù)分配，對參與制造的各主體制定交包計劃，在制作過程中由生產(chǎn)部控制總體進度、質(zhì)量部負責質(zhì)量控制，質(zhì)檢合格后的成品交包入庫，按照發(fā)運計劃組織發(fā)運，最終交付業(yè)主進行現(xiàn)場施工。

圖1 基于裝箱單的制造過程控制流程

2 模型描述與構(gòu)建

2.1 模型描述

為了便于模型的描述，文中首先對基于裝箱單的建材裝備制造任務(wù)優(yōu)化調(diào)度模型中涉及的參數(shù)進行定義和描述，如表1所示。

考慮建材裝備制造企業(yè)基于裝箱單的制造過程控制流程，假設(shè)需要在交付船期Tj內(nèi)完成項目j的制造，項目j劃分成K個制造任務(wù)，制造任務(wù)k歸屬不同的制造類型，由制作方i來完成，而對于同種類型的制造任務(wù)而言，裝備結(jié)構(gòu)的差異性導致不同的加工難度。在對制造任務(wù)進行調(diào)度時，每個制造方已分配相應(yīng)的制造任務(wù)計劃，同時每個制作方能加工的制造任務(wù)類型也是不同的。由于企業(yè)堆放場地的限制，制造任務(wù)的完成時間如果提前太多，企業(yè)需要租賃場地進行成品的堆放，如果延誤船期可能導致高額的索賠。本模型的目的是在保證項目交付船期的前提下，考慮可能的場地租賃成本、因船期延誤導致的業(yè)主索賠損失成本下的制造任務(wù)調(diào)度計劃制定問題。由于存在多個制作方和制造任務(wù)，求解空間隨著制造方及制造任務(wù)的增加呈幾何級數(shù)增長，本文求解的制造任務(wù)調(diào)度問題是一個多目標約束下的NP-hard問題，為滿足上述目標，根據(jù)建材裝備制造企業(yè)的實際情況做如下假設(shè)：

表1 模型參數(shù)定義

(1)廠內(nèi)制作班組和廠外分包隊統(tǒng)稱為制作方，均等納入制造任務(wù)的調(diào)度；

(2)針對不同類型的制造任務(wù)，企業(yè)與制作方按照事先約定的單位工程量制造成本進行制造任務(wù)的加工，因此在制造任務(wù)計劃調(diào)度周期內(nèi)對于裝備的制造成本是恒定的；

(3)制造任務(wù)一旦進行，按照調(diào)度計劃進行連續(xù)加工，不存在制造過程的中斷；

(4)成品運送到港口采用固定的運輸方式，其運輸成本是固定的。

2.2 目標函數(shù)

(1)最小化船期延誤。為了保證項目的交付船期，對于每一個項目j的制造任務(wù)k，其完成的時間Rjk要盡可能小于項目j的交付船期Tj，使得企業(yè)總體的船期延誤最小，目標函數(shù)描述如下：

(1)

(2)最小化總成本。這里主要考慮因制造任務(wù)計劃調(diào)度導致的總成本，總體可分為4部分，即：信譽違約損失成本C1、制造成本C2、場地租賃成本C3和運輸成本C4，其中信譽違約損失成本主要是業(yè)主索賠的損失成本，一般情況下，建材裝備制造企業(yè)通過合同的形式與業(yè)主訂立項目延期的索賠額度，具體描述如下：

(2)

(3)

(4)

(5)

企業(yè)的目標是通過對建材裝備制造任務(wù)的調(diào)度使裝備的總成本最小，由此總成本目標函數(shù)可表示為：

Z2=min(C1+C2+C3+C4)=

(6)

2.3 約束條件

(1)制造任務(wù)約束。為了避免調(diào)度任務(wù)過于復雜，一個制造任務(wù)由一個制作方來完成，且項目的所有制造任務(wù)均分配完畢，同時一個制造任務(wù)只歸屬于一個制造類型，其數(shù)學約束表達如下：

(7)

(8)

(9)

(2)制造能力約束。由于每個制造方擁有的人員、設(shè)備等不相同，其能夠制作的制造任務(wù)類型也不相同，因此只有具有某類型制造能力的制作方才能分配相應(yīng)制造任務(wù)，同時分配的制造任務(wù)不能超過制作方的最大制造能力，其數(shù)學約束表示如下：

?m∈{1,2,…,M},Xijk=1,

Yjkl=1,Eim=0,Fim∈Ojk

s.t.Giml≤Bil

(10)

(3)場地堆放約束。由于企業(yè)的堆放場地有限，因此在任意時刻廠內(nèi)堆放的成品量不能超過廠內(nèi)的最大堆放能力，其數(shù)學約束表示如下：

?m∈{1,2,…,M},Rjk≤m,Zjk=0

(11)

3 模型求解

遺傳算法(genetic algorithm, GA)是一種模擬自然界生物進化過程的智能搜索算法。筆者采用遺傳算法進行優(yōu)化，針對文中求解的基于裝箱單的建材裝備制造任務(wù)調(diào)度問題，遺傳算法求解的基本步驟如下：

(1)初始化算法參數(shù)。算法初始化參數(shù)包括表1中模型的相關(guān)參數(shù)以及遺傳算法的最大迭代次數(shù)MaxGen、群體規(guī)模PopSize以及交叉概率Pc、變異概率Pm等。

(2)染色體編碼與初始化種群。采用整數(shù)編碼方法描述染色體，染色體編碼包括制作方編碼和制造任務(wù)編碼，對于一個由3個制作方，5個制造任務(wù)的調(diào)度問題，一種可能的染色體描述為13223415。在初始化過程中隨機生成滿足群體數(shù)量的染色體序列。

(3)算法終止條件。判斷是否達到算法的最大迭代次數(shù)MaxGen，如果達到終止條件，輸出最優(yōu)個體，算法結(jié)束；否則轉(zhuǎn)步驟(4)。

(4)染色體解碼與適應(yīng)度評估。按照染色體中制作方基因片段順序進行解碼，根據(jù)制作方的制造能力約束按順序從制造任務(wù)基本片段中劃分制造任務(wù)，直到所有制造任務(wù)劃分完成。在解碼的過程中，可能出現(xiàn)無法滿足約束的情況，重新生成滿足約束的染色體。

由于求解模型為多目標最小化問題，根據(jù)企業(yè)實際，選定船期延誤為第一優(yōu)化目標，總成本為第二優(yōu)化目標，即在最小化船期延誤下優(yōu)化總成本。對于最小化問題，為滿足適應(yīng)度要求，選定式(1)和式(6)的倒數(shù)作為適應(yīng)度進行評估函數(shù)。

(5)最優(yōu)保存策略。將當前群體中的最優(yōu)個體與全局最優(yōu)個體比較，并將適應(yīng)度高的個體作為全局最優(yōu)個體。

(6)隨機聯(lián)賽選擇。從群體中隨機選擇兩個個體，首先比較船期延誤適應(yīng)度，將適應(yīng)度高的個體保留至下一代，如果適應(yīng)度相同，比較總成本適應(yīng)度，將總成本適應(yīng)度高的個體保留至下一代，同時進行PopSize次選擇，保證群體規(guī)模。

(7)固定單點交叉。交叉以一定的概率Pc進行，為了避免在交叉過程中產(chǎn)生非法染色體，交叉點的位置固定為制作方的數(shù)量，如步驟(2)中染色體示例中交叉點的位置為3。

(8)多點交換變異。變異以一定的概率Pm進行，分為兩部分，一部分是制作方基因位的變異，另一部分是制造任務(wù)基因位的變異，對于每一種變異，從對應(yīng)的基因片段上隨機選擇兩個位置，互換基因，完成變異。

(9)形成下一代群體，轉(zhuǎn)步驟(3)。

4 應(yīng)用算例

唐山某建材裝備制造企業(yè)主要以制造水泥、冶金、煤炭、礦山、發(fā)電等主機設(shè)備和鋼結(jié)構(gòu)為主，由于企業(yè)項目主要面向海外，船期交付緊張，需要合理安排制造任務(wù)調(diào)度計劃。筆者模擬了其水泥包裝車間項目、鏈式提升機項目和回轉(zhuǎn)窯項目的裝箱單制造任務(wù)，由7個制作方制作的調(diào)度過程，為了簡化問題的求解，文中假定所有制作方?jīng)]有正在制作的任務(wù)，所有制造任務(wù)的難度系數(shù)均為1。表2為項目基本信息，表3為項目制造任務(wù)信息，表4為制作方信息，另外由于廠內(nèi)的最大堆放能力、港口租賃單價和運輸單價分別為5 t、50元/t、120元/t。

表2 項目基本信息

表3 裝箱單制造任務(wù)信息

表4 制作方信息

采用遺傳算法進行求解，并采用Matlab R2009b進行算例仿真，為避免算法的過早收斂，通過多次算法運行，設(shè)定遺傳算法的相關(guān)參數(shù)為：MaxGen=200，PopSize=60，Pc=0.85，Pm=0.05；

算法進化曲線如圖2所示，大約在120代左右收斂，獲取了較優(yōu)調(diào)度方案。算法配置結(jié)果及調(diào)度方案比較如表5和表6所示，從表中可以看出與企業(yè)原始的調(diào)度方案相比，優(yōu)化后的調(diào)度方案在時間延誤和總成本上分別降低了25%和3.37%，說明了調(diào)度算法的有效性。

圖2 遺傳算法進化曲線

任務(wù)編號優(yōu)化調(diào)度方案制作方完成時間/d原始調(diào)度方案制作方完成時間/d任務(wù)編號優(yōu)化調(diào)度方案制作方完成時間/d原始調(diào)度方案制作方完成時間/d13551114312242762141531713546216730630432512177286285525218133?1336615131943042975621020229734?8392821614712938272263325107235235292311141212463132512783325329527135125826632430

注：*為導致時間延誤的制造任務(wù)完成時間。

表6 調(diào)度方案比較

5 結(jié)論

裝箱單是建材裝備制造企業(yè)針對生產(chǎn)制作的指導性文件。筆者從建材裝備制造企業(yè)基于裝箱單的制造過程出發(fā)，構(gòu)建了基于裝箱單的制造任務(wù)調(diào)度模型及求解算法，并通過算例有效驗證了模型的實用性和有效性。該研究成果對指導企業(yè)制定合理的建材裝備制造任務(wù)調(diào)度計劃具有重要意義。

[1] 李益兵,肖倩喬.面向大型建材裝備制造企業(yè)精益生產(chǎn)系統(tǒng)研究[J].武漢理工大學學報(信息與管理工程版),2013(5):714-717.

[2] 李啟銳,彭志平,陳曉龍.面向注塑車間的高效作業(yè)調(diào)度方法[J].計算機應(yīng)用,2014(6):1803-1806.

[3] 張飛,耿紅琴.基于混沌粒子群算法的車間作業(yè)調(diào)度優(yōu)化[J].山東大學學報(工學版),2013,43(3):19-22.

[4] 戰(zhàn)紅,楊建軍.基于工序矩陣編碼遺傳算法的車間作業(yè)調(diào)度優(yōu)化[J].制造業(yè)自動化,2013(7):86-88.

[5] Li Jingsheng, Wang Aimin, Tang Chengtong. Production Planning in Virtual Cell of Reconfiguration Manufacturing System Using Genetic Algorithm[J]. International Journal of Advanced Manufacturing Technology, 2014,74(1-4):47-64.

[6] 王冰,李巧云,羊曉飛.模糊車間作業(yè)調(diào)度的三點滿意度模型[J].控制與決策,2012(7):1082-1086.

[7] Zhang Xiaoge, Deng Yong, Chan Felix TS. IFSJSP: A Novel Methodology for the Job-shop Scheduling Problem Based on Intuitionistic Fuzzy Sets [J]. International Journal of Production Research, 2013,51:5100-5119.

[8] 賀仁杰,陳宇寧,姚鋒,等.求解柔性車間作業(yè)調(diào)度的知識型協(xié)同演化方法[J].計算機集成制造系統(tǒng),2011,17(2):310-315.

[9] 丁雷,王愛民,寧汝新.工時不確定條件下的車間作業(yè)調(diào)度技術(shù)[J].計算機集成制造系統(tǒng),2010,16(1):98-108.