陶寧蓉，蔣祖華，劉建峰，孫曉軍，朱玉龍，李軍濤

(1. 上海海洋大學(xué)工程學(xué)院，上海 201306; 2. 上海交通大學(xué)機械與動力工程學(xué)院，上海 200240；3. 高新船舶與深海開發(fā)裝備協(xié)同創(chuàng)新中心，上海 200240; 4. 上海外高橋造船有限公司，上海 200137)

考慮工藝流程的船體分段多堆場調(diào)度問題研究

陶寧蓉1，蔣祖華2,3，劉建峰4，孫曉軍4，朱玉龍4，李軍濤1

(1. 上海海洋大學(xué)工程學(xué)院，上海 201306; 2. 上海交通大學(xué)機械與動力工程學(xué)院，上海 200240；3. 高新船舶與深海開發(fā)裝備協(xié)同創(chuàng)新中心，上海 200240; 4. 上海外高橋造船有限公司，上海 200137)

為了有效解決在船舶建造過程中物流擁堵的問題，綜合考慮分段建造工藝流程、分段大小和堆場布局，以最小分段移動度為目標，提出基于工藝流程的多堆場船體分段調(diào)度方法，并針對調(diào)度過程中出現(xiàn)的阻擋分段提出堆位調(diào)整算法。對上海某造船廠分段物流進行的實際驗證表明，本方法可獲得較優(yōu)化的調(diào)度方案，可有效提高作業(yè)效率。

物流系統(tǒng)管理；分段堆場；分段工藝流程；分段移動度；阻擋分段

在現(xiàn)代造船模式下，船舶建造以中間產(chǎn)品“分段”作為基本作業(yè)單元，分段在組立車間成型后脫胎，需要經(jīng)過預(yù)舾裝、噴砂、涂裝等工藝，最后到船塢進行總組搭載。由于天氣、檢驗等不確定因素，分段在工序之間的流動并非無縫連接，堆場作為分段臨時存放的場所，用以緩解對生產(chǎn)車間資源的需求。然而，由于分段質(zhì)量大、體積大，移動緩慢且成本高，分段物流已成為船廠非常重視的活動之一。目前，因為調(diào)度不合理和管理缺乏，堆場上分段堆放無序，造成分段進出堆場移動困難，導(dǎo)致過多阻擋分段，嚴重影響生產(chǎn)的進度。因此，優(yōu)化分段堆場調(diào)度是船廠亟需解決的問題。

船體分段堆場調(diào)度屬于二維平面調(diào)度問題，但除了要考慮分段的時間約束和空間約束，還需要考慮分段在運輸過程中對移動路徑上的空間需求[1]。目前，國內(nèi)外文獻主要是針對堆位分配進行研究，以減少分段進出場時引起的阻擋分段臨時移動。文獻[2]首次研究了分段堆場調(diào)度對提高堆場利用率及減少無效勞動的重要意義，文獻[3—5]將分段堆場優(yōu)化調(diào)度過程建立數(shù)學(xué)模型，研究了進場分段堆位選擇策略和阻擋分段臨時移動策略。文獻[6]將BP神經(jīng)網(wǎng)絡(luò)用于預(yù)測周期內(nèi)進出場分段的數(shù)量。文獻[7—8]考慮了分段形狀和尺寸的差異性對場地利用率的影響。此外，文獻[9]研究了分段進場時的堆位選擇評價函數(shù)，并提出針對堆位選擇的禁忌搜索算法，文獻[10]提出平板車在堆場中可以直角轉(zhuǎn)彎以選擇阻擋分段更少的路徑，并用最短路算法求解小規(guī)模堆場調(diào)度；文獻[11]在此基礎(chǔ)上考慮了分段進場時間不確定和路徑變化對堆場調(diào)度的影響，另外，文獻[12—13]將分段在多車間的調(diào)度轉(zhuǎn)換成并行機調(diào)度問題，文獻[14]結(jié)合運輸能力限制和堆場面積約束，提出了分段兩階段多車間調(diào)度模型，文獻[15]針對總組平臺提出分段調(diào)度模型。

現(xiàn)有文獻大多針對單個堆場上的調(diào)度問題進行分析和求解，沒有考慮實際應(yīng)用中多堆場的并行調(diào)度，而針對多車間調(diào)度的研究也沒有和分段堆場上堆位調(diào)度問題結(jié)合起來考慮。另外，沒有結(jié)合分段的實際尺寸考慮同一堆位上放置多個小分段的情況。針對以上問題，本文考慮了分段尺寸大小和分段堆位偏好，提出面向工藝流程的多堆場調(diào)度模型，分析基于網(wǎng)格的多分段并存的移動度表達和堆位搜索方法，并針對阻擋分段提出堆位調(diào)整算法，實現(xiàn)阻擋分段再調(diào)度，降低當前調(diào)整對后續(xù)任務(wù)的影響，最后結(jié)合船廠的實際數(shù)據(jù)對模型進行了實例驗證。

1 問題描述

圖1左側(cè)為一船廠內(nèi)分段堆場和各個工藝階段的建造車間的分布示例。堆場上堆位采用網(wǎng)格式劃分，由于廠區(qū)布局的限制，分段堆場的尺寸和形狀不同，圖1右側(cè)為5×8的分段堆場。

圖1 船廠堆場布局示例Fig.1 Example of block stockyard in shipyards

在滾動作業(yè)計劃下，獲取當期各堆場上的堆存信息，根據(jù)當前調(diào)度期內(nèi)的分段調(diào)度需求，為各分段選擇合適的堆場并為其在堆場中分配合理的堆位，同時基于分段的進出場移動路徑和堆場布局，確定阻擋方段的移動策略，使得分段移動度最小。

調(diào)度周期內(nèi)執(zhí)行分段任務(wù)所產(chǎn)生的總移動度最小的目標函數(shù)如下：

Minimize

(1)

式(1)的約束條件如下：

1≤ti≤T,

(2)

(3)

(4)

(5)

(6)

(7)

式(2)約束任務(wù)分段的執(zhí)行時間在調(diào)度周期內(nèi)；式(3)約束同一時間只執(zhí)行1個任務(wù)；式(4)約束堆位上分段面積的總和小于堆位面積；式(5)約束1個分段只能放置在1個堆位上；式(6)約束分段進出堆場的路徑為移動度最小路徑；式(7)保證分段優(yōu)先放在與分段類型對應(yīng)的偏好堆位。

2 求解算法

2.1 基于工藝流程的多堆場堆位調(diào)度方法

船舶生產(chǎn)是典型的拉式生產(chǎn)方式，基于任務(wù)分解的思想[16]，根據(jù)船舶工藝流程，分段的流向服從脫胎—預(yù)舾裝—沖砂—涂裝—總組，結(jié)合分段的搭載順序和各工藝流程的標準周期，確定分段在當前調(diào)度周期內(nèi)的作業(yè)時間需求，如圖2所示。

圖2 基于工藝流程的多堆場調(diào)度方法Fig.2 Multi-stockyard scheduling method based on technological process

2.2 分段移動度最小的堆位搜索算法

1)分段移動度分析

圖3對應(yīng)圖1的堆場信息。

圖3 分段堆場的數(shù)字化表達Fig.3 Mathematical express of block stockyard

圓圈表示堆位，有標號的圓圈表示該堆位上有分段，圓圈左下方的橢圓表示堆位編號，道路的編號為0，圓圈內(nèi)堆位信息分2行：第1行數(shù)字代表分段編號，第2行以“|”為分隔，分別代表分段的進場時間和出場時間，其中“-1”表示當前調(diào)度周期前該分段已在場。如14(1|4)表示14號分段是當前調(diào)度周期的第1天入場、第4天出場。

在選擇分段進、出場路徑時，將堆位看作節(jié)點，節(jié)點狀態(tài)“2”，“1”和“0”分別表示堆位上分段的個數(shù)，相鄰堆位由帶權(quán)重的邊連接，權(quán)重的大小與移動度對應(yīng)。設(shè)遇到1個阻擋分段和1個空堆位的移動度分別為α和β。因為移動阻擋分段的成本很大，α取值應(yīng)遠大于β，如取α=1，β=0.001?？紤]到1個堆位上放置2個分段的情況，將與狀態(tài)為“2”和“1”的堆位相鄰邊的權(quán)重定為1和0.5，如圖4所示。

圖4 堆位節(jié)點距離圖
Fig.4 Distance between stockyard nodes

2)堆位搜索流程

根據(jù)船廠堆場上每個堆位對不同工藝流程的分段偏好，該流程有偏好地選擇放置堆位。結(jié)合分段的尺寸，將可放置堆位分為兩大類，即空堆位集C1和非空堆位集C2。在得到候選堆位集C1和C2后，首先在堆位候選集C2中選擇出場時間與任務(wù)分段出場時間一致的堆位，通過Dijkstra算法計算分段從起始位置到達候選堆位的最短路徑并計算移動度；在候選堆位集C1中計算分段從起始位置到達候選堆位的最短路徑并計算移動度，具體流程見圖5。

2.3 阻擋分段移動算法

圖6為分段移動路徑上遇到阻擋分段時的調(diào)度算法。阻擋分段在正常的任務(wù)分段的移動任務(wù)執(zhí)行過程中產(chǎn)生，其移動為正常分段移動任務(wù)的衍生任務(wù)，會增加額外的成本。對于已經(jīng)產(chǎn)生的阻擋分段，移動的目的首先要不再產(chǎn)生新的阻擋分段，同時進一步改善堆場布局，降低后續(xù)分段移動的成本。

3 算法應(yīng)用

本文算法結(jié)合上海某大型船廠分段堆場調(diào)度的實際情況予以實現(xiàn)。由于涉及多個堆場的若干個堆位和分段，故僅列舉部分數(shù)據(jù)：表1為堆場堆位的初始狀態(tài)，即堆場上已有分段及其預(yù)計出場時間；表2為當前調(diào)度任務(wù)信息；表3為各堆場堆位尺寸、空間位置、對應(yīng)的工藝階段偏好，堆位ID的編碼采用字母和數(shù)字組合的方式，如“P7104”。參數(shù)α=1， β=0.001。

圖5 分段堆位搜索流程Fig.5 Searching flow for block storage location

圖6 阻擋分段移動策略框架Fig.6 Frame of moving strategy for obstructive blocks

分段ID堆位ID預(yù)計出場時間分段ID堆位ID預(yù)計出場時間110P7102第3天103P6416第3天100P6403第1天104P6412第4天101P6404第1天105P6413第5天102P6408第2天106P6414第1天………………

表2 分段調(diào)度任務(wù)列表

表3 各分段堆場上堆位的信息

通過本文算法確定的分段調(diào)度結(jié)果如表4所示，對于每一條分段移動任務(wù)，算法給出其在堆場內(nèi)移動的路徑。所謂堆場內(nèi)的移動路徑，是由一個個相鄰的堆位序列來表示的，其中每一條路徑的第1個位置點為該分段的初始停放位置，而最后一個位置點則為該分段的終止停放位置。如果位置在堆場上，則會給出對應(yīng)的堆場變化；如位置在某個工藝流程的車間，則給出對應(yīng)的車間名字即可?！?R-”表示該分段移動任務(wù)要求分段先從初始堆場或車間出來，再進入另一個堆場或車間，“-R-”前后的路徑分別表示該分段出堆場和進堆場的路徑。

在實際生產(chǎn)中，分段堆場調(diào)度主要是依靠調(diào)度人員的經(jīng)驗，目前只能做到每半天做1次調(diào)度計劃，而且還得安排人員隨時跟進現(xiàn)場實際情況進行調(diào)整，需要匹配大量的人力、物力和時間成本。利用本文所研究的方法，可以對分段在多堆場/車間之間以及在堆場內(nèi)部的移動進行統(tǒng)一規(guī)劃，以獲得較優(yōu)的調(diào)度方案，結(jié)合分段的工藝階段和分段尺寸，充分利用堆場資源，提高作業(yè)效率，并且可以實現(xiàn)1周以上的滾動作業(yè)計劃，大大提高實際作業(yè)的計劃性和可實施性。

表4 多堆場分段調(diào)度方案

4 結(jié) 語

基于實際情況，對船舶建造過程中的分段堆場調(diào)度進行了研究，考慮了分段所處工藝階段以及多堆場中各堆位相對于分段工藝階段的偏好，結(jié)合一個堆位可放置超過一個小分段以提高空間利用率的需求，提出面向建造工藝流程的多堆場調(diào)度模型，分析了基于網(wǎng)格的多分段并存的移動度表達和堆位搜索方法，并針對阻擋分段提出堆位調(diào)整算法。后期研究將考慮采用智能算法對堆位選擇與阻擋分段調(diào)整進一步優(yōu)化，以獲得更好的結(jié)果。此外，實際情況中的不確定因素、對未來堆場作業(yè)的預(yù)見性也是需要進一步研究的內(nèi)容。

[1] 陶寧蓉. 船舶分段建造過程中的資源調(diào)度優(yōu)化研究[D]. 上海：上海交通大學(xué), 2013. TAO Ningrong. Research on Resource Scheduling Problems during Ship Block Assembly Process[D]. Shanghai: Shanghai Jiao Tong University, 2013.

[2] PARK C, SEO J, KIM J. Assembly block storage location assignment at a shipyard: A case of hyundai heavy industries[J]. Production Planning & Control, 2007, 18(3): 180-189.

[3] PARK C, SEO J. Assembly block storage location assignment problem: Revisited[J]. Production Planning & Control, 2009, 20(3): 216-226.

[4] PARK C, SEO J. Mathematical modeling and solving procedure of the planar storage location assignment problem[J]. Computers & Industrial Engineering, 2009, 57(3):1062-1071.

[5] PARK C, SEO J. Comparing heuristic algorithms of the planar storage location assignment problem[J]. Transportation Research Part E Logistics & Transportation Review, 2010, 46(1):171-185.

[6] 周鍵, 曹瑞霞, 汪雄. 分段堆場預(yù)測調(diào)度研究[J].計算機工程與應(yīng)用, 2013, 49(23): 221-227. ZHOU Jian, CAO Ruixia, WANG Xiong. Shipbuilding yards predictable scheduling approach[J]. Computer Engineering and Applications, 2013, 49(23): 221-227.

[7] 張志英, 楊克開, 于瑾維. 面向船體分段建造的二維不規(guī)則空間調(diào)度方法[J].上海交通大學(xué)學(xué)報, 2012, 46(4): 651-656. ZHANG Zhiying, YANG Kekai, YU Jinwei. Two-dimensional irregular spatial scheduling method for hull block construction in shipbuilding[J]. Journal of Shanghai Jiao Tong University, 2012, 46(4): 651-656.

[8] 陸春霞. 船體不規(guī)則分段的動態(tài)空間調(diào)度及場地堆放問題研究[D]. 鎮(zhèn)江：江蘇科技大學(xué), 2013. LU Chunxia. Research on Irregular Block Dynamic Spatial Scheduling and Stacking Problem in Shipbuilding Industry[D]. Zhenjiang: Jiangsu University of Science and Technology, 2013.

[9] TAO Ningrong, JIANG Zuhua, QU Shipeng. Assembly block location and sequencing for flat transporters in a planar storage yard of shipyards[J]. International Journal of Production Research, 2013, 51(14): 4289-4301.

[10]張志英, 申鋼, 劉祥瑞. 基于最短路算法的船舶分段堆場調(diào)度[J]. 計算機集成制造系統(tǒng), 2012, 18(9): 1982-1990. ZHANG Zhiying, SHEN Gang, LIU Xiangrui. Block storage yard scheduling of shipbuilding based on shortest-path algorithm[J]. Computer Integrated Manufacturing Systems, 2012, 18(9): 1982-1990.

[11]陳凱, 蔣祖華, 劉建峰, 等. 帶有進場時間窗的船舶分段堆場調(diào)度研究[J]. 上海交通大學(xué)學(xué)報, 2016, 50(9): 1390-1398. CHEN Kai, JIANG Zuhua, LIU Jianfeng, et al. Shipbuilding yard scheduling with block inbound time window[J]. Journal of Shanghai Jiao Tong University, 2016, 50(9): 1390-1398.

[12]ROH M, CHA J. A block transportation scheduling system considering a minimization of travel distance without loading of and interference between multiple transporters[J]. International Journal of Production Research, 2011, 49(11): 3231-3250.

[13]PARK C, SEO J. A GRASP approach to transporter scheduling and routing at a shipyard[J]. Computers & Industrial Engineering, 2012(63): 390-399.

[14]代乙君, 張志英, 王維澤. 運輸能力有限的分段兩階段多車間調(diào)度問題[J]. 計算機工程與應(yīng)用, 2016, 52(7): 222-235. DAI Yijun, ZHANG Zhiying, WANG Weize. Block two-stage and multi-workshop scheduling with transportation consideration[J]. Computer Engineering and Applications, 2016, 52(7): 222-235.

[15]李敬花, 樊付見, 余峰. 求解船體分段堆場調(diào)度問題的改進遺傳算法[J]. 計算機集成制造系統(tǒng), 2012, 18(12): 2674-2682. LI Jinghua, FAN Fujian, YU Feng. Improved genetic algorithm for ship block yard scheduling problem[J]. Computer Integrated Manufacturing Systems, 2012, 18(12): 2674-2682.

[16]魏妮妮,宋翌. 基于任務(wù)分解的時間均衡度算法[J].河北科技大學(xué)學(xué)報, 2013, 34(6): 559-564. WEI Nini, SONG Yi. A time-balancing scheduling algorithm based on task decomposition[J]. Journal of Hebei University of Science and Technology, 2013, 34(6): 559-564.

Multi-stockyard scheduling problem considering technological process of hull blocks

TAO Ningrong1， JIANG Zuhua2,3， LIU Jianfeng4， SUN Xiaojun4， ZHU Yulong4， LI Juntao1

(1.College of Engineering, Shanghai Ocean University, Shanghai 201306, China; 2.School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China; 3. Collaborative Innovation Center for Advanced Ship and Deep-Sea Exploration, Shanghai 200240, China; 4. Shanghai Waigaoqiao Shipbuilding Company Limited, Shanghai 200137, China)

In order to effectively solve the current status of logistics congestion in shipbuilding process, the technological process of blocks, block size and block stockyard layout are considered. With the objective to minimize block move degree, a multi-stockyard scheduling algorithm based on technological process of blocks is proposed, and an adjustment algorithm for obstructive blocks is given. The application of the method in a shipbuilding company in Shanghai shows that the method can obtain optimal scheduling scheme and improve operation efficiency.

logistics systems management; block stockyard; technological process of blocks; block move degree; obstructive block

1008-1534(2017)01-0012-06

2016-10-31;

2016-11-21；責(zé)任編輯：馮 民

國家自然科學(xué)基金(71501125)；上海高校青年教師培養(yǎng)資助計劃(ZZHY14031)；工業(yè)和信息化部項目(工信部聯(lián)裝[2014]507號)

陶寧蓉(1983—)，女，江蘇鹽城人，講師，博士，主要從事生產(chǎn)計劃、物流管理、調(diào)度優(yōu)化等方面的研究。

E-mail: nrtao@shou.edu.cn

TP391;U673

A

10.7535/hbgykj.2017yx01003

陶寧蓉，蔣祖華，劉建峰,等.考慮工藝流程的船體分段多堆場調(diào)度問題研究[J].河北工業(yè)科技,2017,34(1):12-17. TAO Ningrong，JIANG Zuhua，LIU Jianfeng,et al.Multi-stockyard scheduling problem considering technological process of hull blocks[J].Hebei Journal of Industrial Science and Technology,2017,34(1):12-17.