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

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

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

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

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

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

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

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

1 問題描述

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

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

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

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

Minimize

(1)

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

1≤ti≤T,

(2)

(3)

(4)

(5)

(6)

(7)

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

2 求解算法

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

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

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

2.2 分段移動(dòng)度最小的堆位搜索算法

1)分段移動(dòng)度分析

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

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

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

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

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

2)堆位搜索流程

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

2.3 阻擋分段移動(dòng)算法

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

3 算法應(yīng)用

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

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

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

分段ID堆位ID預(yù)計(jì)出場時(shí)間分段ID堆位ID預(yù)計(jì)出場時(shí)間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所示，對(duì)于每一條分段移動(dòng)任務(wù)，算法給出其在堆場內(nèi)移動(dòng)的路徑。所謂堆場內(nèi)的移動(dòng)路徑，是由一個(gè)個(gè)相鄰的堆位序列來表示的，其中每一條路徑的第1個(gè)位置點(diǎn)為該分段的初始停放位置，而最后一個(gè)位置點(diǎn)則為該分段的終止停放位置。如果位置在堆場上，則會(huì)給出對(duì)應(yīng)的堆場變化；如位置在某個(gè)工藝流程的車間，則給出對(duì)應(yīng)的車間名字即可?！?R-”表示該分段移動(dòng)任務(wù)要求分段先從初始堆場或車間出來，再進(jìn)入另一個(gè)堆場或車間，“-R-”前后的路徑分別表示該分段出堆場和進(jìn)堆場的路徑。

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

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

4 結(jié) 語

基于實(shí)際情況，對(duì)船舶建造過程中的分段堆場調(diào)度進(jìn)行了研究，考慮了分段所處工藝階段以及多堆場中各堆位相對(duì)于分段工藝階段的偏好，結(jié)合一個(gè)堆位可放置超過一個(gè)小分段以提高空間利用率的需求，提出面向建造工藝流程的多堆場調(diào)度模型，分析了基于網(wǎng)格的多分段并存的移動(dòng)度表達(dá)和堆位搜索方法，并針對(duì)阻擋分段提出堆位調(diào)整算法。后期研究將考慮采用智能算法對(duì)堆位選擇與阻擋分段調(diào)整進(jìn)一步優(yōu)化，以獲得更好的結(jié)果。此外，實(shí)際情況中的不確定因素、對(duì)未來堆場作業(yè)的預(yù)見性也是需要進(jìn)一步研究的內(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ù)測(cè)調(diào)度研究[J].計(jì)算機(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é)報(bào), 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ī)則分段的動(dòng)態(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]. 計(jì)算機(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]陳凱, 蔣祖華, 劉建峰, 等. 帶有進(jìn)場時(shí)間窗的船舶分段堆場調(diào)度研究[J]. 上海交通大學(xué)學(xué)報(bào), 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]代乙君, 張志英, 王維澤. 運(yùn)輸能力有限的分段兩階段多車間調(diào)度問題[J]. 計(jì)算機(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ìn)遺傳算法[J]. 計(jì)算機(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ù)分解的時(shí)間均衡度算法[J].河北科技大學(xué)學(xué)報(bào), 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)資助計(jì)劃(ZZHY14031)；工業(yè)和信息化部項(xiàng)目(工信部聯(lián)裝[2014]507號(hào))

陶寧蓉(1983—)，女，江蘇鹽城人，講師，博士，主要從事生產(chǎn)計(jì)劃、物流管理、調(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.