圖力資源的船舶分段加工時空規(guī)劃方法

　　摘 要：為研究考慮人力資源以及人的非理性因素的船舶分段加工時空規(guī)劃調(diào)度問題，本文依據(jù)前景理論，提出了一種新的優(yōu)化模型方法。首先綜合考慮多個場地之間空間和人力資源負載均衡、工期以及分段延誤等多個優(yōu)化目標(biāo)，將時間、空間和人力資源限制等作為約束條件，構(gòu)建多目標(biāo)優(yōu)化模型，并將人的非理性心理在人力資源負載均衡中加以考慮。其次，提出了一種結(jié)合左下角填充與搜索插空填充的分段時空規(guī)劃的高效算法。最后，實際和仿真運行表明該模型方法能夠在數(shù)秒之內(nèi)得到上百塊的規(guī)劃方案，充分驗證了其實用性和高效性。該研究結(jié)果將為船舶分段的時空規(guī)劃調(diào)度效率提升提供有效的理論和方法支持。

　　關(guān)鍵詞：人力資源;船舶分段;時空規(guī)劃;負載均衡;前景理論;非理性;多目標(biāo)優(yōu)化;啟發(fā)式算法

　　船舶制造屬于勞動密集型產(chǎn)業(yè)，除了占用大量的時間和空間資源外，人力資源也是不可忽視的重要因素。據(jù)了解，建造一艘 7.5 萬噸級的散貨船，中國需要近 100 完工時，一個年造船能力在 140 萬載重噸左右的船廠，需要生產(chǎn)作業(yè)工人 5000 名左右。近幾年，由于地理環(huán)境艱苦等因素，造船廠人員流失情況加重，給船舶制造產(chǎn)業(yè)帶來嚴(yán)峻的挑戰(zhàn)。船舶分段加工作為船舶制造產(chǎn)業(yè)的重要環(huán)節(jié)之一，同樣受人力資源的影響較大�？紤]工作區(qū)域的時間、空間和人力資源的限制，實現(xiàn)對船舶分段加工調(diào)度的有效管理，往往是提高造船廠生產(chǎn)力的關(guān)鍵措施。

　　然而，人力資源不同于其他設(shè)備資源，他們的主觀或非理性心理會影響工作的調(diào)度安排。因此，有必要對考慮非理性人力資源的船舶分段加工時空規(guī)劃調(diào)度問題進行優(yōu)化研究，以提高船舶制造的生產(chǎn)效率。Lee 等[1]首次開始研究船舶分段加工調(diào)度問題，將船舶分段的時空規(guī)劃問題運用三維裝箱理論進行描述和求解。自此，船舶分段加工調(diào)度逐漸引起了諸多學(xué)者的長期關(guān)注。當(dāng)前船舶分段調(diào)度的研究重點主要在于如何提高時間和空間等資源的利用效率。在時間資源上主要研究如何縮短工期[2]或降低分段的延誤情況;

　　對空間資源的研究主要分為兩類，單加工場地旨在提高空間利用率[4]，而對于多加工場地來說則是多場地之間的工作量均衡[5]。由于該類問題是 NP-hard[6]，對該類問題的求解主要聚焦于智能優(yōu)化方法和基于優(yōu)先規(guī)則的啟發(fā)式構(gòu)造方法。大部分研究運用禁忌搜索[7]和遺傳算法[2,8-11]等智能算法來求解船舶分段調(diào)度問題。

　　遺傳算法等智能優(yōu)化算法的優(yōu)點是可以很有效地處理多目標(biāo)優(yōu)化，但同時也會因為算法復(fù)雜度太高、內(nèi)部規(guī)則不透明而導(dǎo)致無法在生產(chǎn)實踐中展開應(yīng)用。基于優(yōu)先規(guī)則的船舶分段調(diào)度是當(dāng)前的研究熱點，多數(shù)文獻綜合考慮分段加工時間、分段最早開始時間、分段最遲完工時間以及分段后續(xù)加工數(shù)量等各項指標(biāo)[2,5,6]作為分段排序的依據(jù)，常用的填充規(guī)則包括左下角填充規(guī)則[12]、時空相似規(guī)則[13]、對角填充規(guī)則[14]等。

　　然而，上述優(yōu)先規(guī)則主要考慮未加工分段的時空特點，而沒有考慮已加工完成的分段對加工空間的擴充。綜上所述，當(dāng)前對船舶分段加工調(diào)度問題的研究主要集中于對時間和空間資源的規(guī)劃，缺少人力資源約束對船舶分段調(diào)度優(yōu)化的研究，尤其缺少人的非理性因素對船舶分段調(diào)度優(yōu)化的影響分析。另外，在調(diào)度優(yōu)先規(guī)則上主要聚焦于未加工分段的時空特點，而沒有考慮已完成分段移除后對時空規(guī)劃的影響。

　　基于此，本文針對船舶分段加工多場地調(diào)度優(yōu)化問題展開研究。主要創(chuàng)新點如下：首先，綜合考慮空間資源、時間資源以及人力資源，構(gòu)建船舶制造過程中的分段加工調(diào)度的多目標(biāo)優(yōu)化模型;其次，運用前景理論在模型目標(biāo)中將人力資源的非理性心理下的主觀損失有效表達出來;最后基于分段優(yōu)先規(guī)則、左下角填充規(guī)則和搜索插空填充規(guī)則設(shè)計一種改進的混合啟發(fā)式構(gòu)造算法，對船舶分段加工調(diào)度問題進行高效快速求解。該模型方法不僅可以為現(xiàn)實中的船舶分段加工時空規(guī)劃調(diào)度問題提供有效的輔助決策支持，也對船舶空間調(diào)度優(yōu)化相關(guān)理論方法進行了有效補充。

　　1 模型

　　1.1 問題描述

　　當(dāng)前船舶制造還無法完全實現(xiàn)智能化制造，因此分段加工過程不僅需要懸臂起重機等專業(yè)設(shè)備，還需要人工的輔助才能完成。每一個分段加工場地可以看作是一個二維空間。一般情況下，分段和加工場地的形狀大多為矩形或不規(guī)則多邊形，本文假設(shè)分段和加工場地形狀為矩形;分段可旋轉(zhuǎn) 0 度或 90 度放置。

　　本文的多場地船舶分段加工調(diào)度問題可以定義為指定各分段的加工場地、加工順序、加工方位，使其在滿足加工時間、空間和人力資源約束的前提下，達到所有加工場地的空間負載均衡偏差最小、人力資源負載均衡偏差最小、總工期最短、分段延誤數(shù)量最少的優(yōu)化目標(biāo)�？臻g負載均衡偏差是指每個加工場地的單位空間承擔(dān)的的工作量與平均單位空間工作量之間的差別。人力資源負載均衡偏差是指在考慮人員主觀損失的前提下，每個加工場地之間單位人員任務(wù)量分配與平均值之間的差別。

　　空間和人力資源負載均衡的表示方法。工期是指最后一個分段加工完成的時刻。延誤分段是指實際完工時刻晚于最遲完工時刻的分段。船舶分段加工調(diào)度問題的約束限制分別介紹如下：首先，時間約束包括：

　　1)各分段實際開始加工時刻不能早于最早開始加工時刻;2)各分段實際完工時刻不能晚于最遲完工時刻，否則認定為該分段加工出現(xiàn)延誤;3)各分段加工過程不能出現(xiàn)中斷。其次，空間約束包括：1)每個分段只能處于一個加工場地;2)各分段不能超出加工場地的邊界;3)各分段之間在二維空間不能重疊;4)各分段不能隨意放置，只能旋轉(zhuǎn) 0度或 90 度;5)各分段在加工過程中不能出現(xiàn)移動。

　　人力資源約束是指在每個加工時段，各分段需要的工人數(shù)量不能超過該加工空間提供的工人數(shù)量。在一個矩形的加工場地中，需要調(diào)度 5 個矩形分段。 給出了各個分段的規(guī)格大小、加工時間、需要的工人數(shù)量、最早開始時刻以及最遲完工時刻。該加工空間大小為 10×10，工人組數(shù)的限制是 5。

　　分段 1 在第一天開始加工;分段 2 和分段 3 在第 2 天開始加工;由于工人數(shù)量的限制，分段 4 無法按照最早開始時刻在第 3 天開始加工，只能在第 4 天開始加工，同時由于加工場地的空間約束，分段 4 旋轉(zhuǎn)之后可以放入加工場地;由于工人數(shù)量和空間的限制，分段 5 無法按照最早開始時刻在第 3 天開始加工，只能在第 5 天開始加工，實際完工時刻為第 8 天，晚于分段 5 的最遲完工時刻，因此出現(xiàn)延誤分段。最后在第 8 天結(jié)束，所有的分段加工完畢。

　　1.2 負載均衡

　　在加工過程中，不僅要考慮空間任務(wù)量的均衡，還要考慮人力資源工作量的均衡�？紤]到人在面對不同的負載差別時，會有自己的主觀判斷。因此本文用前景理論的若干個特征[15,16]來描述人力資源負載均衡偏差：1)人力資源的主觀損失或收益是相對于參考點來說的，本文將所有場地的平均人力資源負載作為參考點;2)相對收益來說，人們對損失更敏感，本文假設(shè)：若某個場地的人力資源負載高于平均負載，則該場地的人力資源會承擔(dān)損失，否則，會獲得收益;3)人們對在面對損失和收益時分別會產(chǎn)生風(fēng)險追尋和風(fēng)險規(guī)避的傾向。綜合以上特征，我們給出各場地的單位人員負載均衡偏差表達式。該表達式的值越小，表明各場地的人員負載越均衡。

　　1.3 模型建立

　　本文建立了一個非線性規(guī)劃模型，對考慮人力資源的船舶分段加工的時空規(guī)劃調(diào)度優(yōu)化問題進行具體描述。模型是以左下角為原點，在加工空間上建立平面直角坐標(biāo)系，利用坐標(biāo)數(shù)值表示分段的放置位置。

　　約束(14)保證每個分段都不能在最早開始時間之前開始加工;約束(15)和 (16)表示如果分段在最遲完工時刻之后仍在加工，則出現(xiàn)了延誤;約束(17)保證了在每個加工時間段，工人數(shù)都可以滿足加工需求;約束(18)是為了保證每個加工時間段加工空間的面積是充足的;約束(19)和約束(20)確保每個分段在加工時不越界，其中也包含了分段的旋轉(zhuǎn)情況;約束(21)和 (22)是對兩端點坐標(biāo)之差的具體計算規(guī)則;約束(23)是表述分段在空間上不重疊;約束(24)和 (25)保證分段在加工過程中不能移動;約束(26)-(31)對模型的決策變量進行了定義。

　　2 算法設(shè)計

　　考慮到非線性優(yōu)化模型的復(fù)雜性，本文基于現(xiàn)實中分段加工的優(yōu)先規(guī)則和搜索插空填充算法，對傳統(tǒng)的左下角填充搜索算法進行改進，設(shè)計了改進的混合啟發(fā)式構(gòu)造算法。

　　2.1 算法流程

　　本文算法的具體流程，首先，計算各分段的優(yōu)先度，按照優(yōu)先規(guī)則對分段進行分組，并對每個分段分配場地。然后，按照優(yōu)先序依次對各場地內(nèi)的分段進行操作，對于每個場地內(nèi)未加工完成的分段，依次在各個時間判斷分段所處的狀態(tài)，并在合適的加工空間擺放。直到最后，所有的分段擺放完成，算法結(jié)束。

　　2.2 分段的場地分配本文考慮所有分段的最遲完工時間和最早開始時間對它們 進行排序， 將排好序的 分段分成round(1/2)組，將每個組的分段分到每個加工場地，本文采取空間負載均衡偏差和人力資源負載均衡偏差的比重各占 50%的方式，進行場地的分段分配。本文涉及到的分段位置，均指該物分段的左下角坐標(biāo)。2.3 分段放置分段的放置以天為時間單位，在移除已加工完成的分段時，需要記錄下“空缺位”，為后續(xù)的分段擺放提供搜索依據(jù)。

　　(1)分段移除：若分段放入時間和加工時間之和等于當(dāng)前時間，則將分段移除，即該分段加工完畢。此時該位置標(biāo)記為一個“空缺位”。(2)分段填充：如果工人數(shù)還有剩余，就按照分段排序遍歷所有分段，對于最早開始時間等于當(dāng)前時間的分段，進行插入擺放操作：首先遍歷所有“空缺位”，考慮旋轉(zhuǎn)的情況下檢驗此分段是否可以放入。若無法放入則執(zhí)行順序擺放操作：首先確定該分段的橫坐標(biāo)值，然后根據(jù)重疊規(guī)則確定縱坐標(biāo)值。循環(huán)執(zhí)行上述操作，當(dāng)所有的分段都加工完畢，則總?cè)蝿?wù)完成，該時間即為總工期。

　　3 算例分析

　　本文設(shè)計了兩組算例分析，進行優(yōu)化模型方法的分析驗證。第一組算例為來源于某船廠的實際算例[13]，第二組算例是隨機產(chǎn)生的測試數(shù)據(jù)。實驗環(huán)境為運行在 Windows 10(64 位)操作系統(tǒng)下的Intel(R) Core(TM)i7-4510U CPU @ 2.00GHz (8GRAM) 筆記本，并采用 MATLAB(版本 R2016a)軟件編制程序。

　　當(dāng)分段規(guī)模為 5 時，CPLEX 和啟發(fā)式構(gòu)造算法得出的結(jié)果相差不大，但是在程序運行效率上，本文的算法更占優(yōu)勢。當(dāng)分段規(guī)模達到 25 及更大時，CPLEX 商業(yè)軟件無法得到非線性規(guī)劃的優(yōu)化結(jié)果。而本文的算法僅在 2 秒左右就可以得到 100 多塊分段的時空調(diào)度優(yōu)化方案。

　　為了驗證考慮人力資源以及人的非理性對模型優(yōu)化結(jié)果的影響，將本文的模型方法與兩種標(biāo)桿方法進行對比，標(biāo)桿方法 1 在分段規(guī)劃時不考慮人力資源的負載均衡，標(biāo)桿方法 2 是在規(guī)劃時雖然考慮人力資源的負載均衡，但是忽略人的非理性心理。雖然由本文的模型方法得到的空間負載均衡值差于標(biāo)桿方法 1，但是工人負載均衡偏差明顯優(yōu)于標(biāo)桿方法 1，并且空間和工人負載均衡平均偏差也優(yōu)于標(biāo)桿方法 1，尤其當(dāng)分段規(guī)模較大時，平均值呈現(xiàn)出量級上的差別。與工人負載均衡偏差類似，當(dāng)分段規(guī)模較大時，工期和分段延誤數(shù)量也顯著優(yōu)于標(biāo)桿方法 1。與標(biāo)桿方法 2 相比，在分段規(guī)模較大時，本文的模型方法的優(yōu)勢也能體現(xiàn)出來。

　　4 結(jié) 論

　　本文針對考慮人力資源的船舶分段時空規(guī)劃調(diào)度優(yōu)化問題，重點在以下三個方面取得了一定研究成果。首先，基于最小化多個場地之間的空間、人力資源負載均衡偏差、工期和分段延誤數(shù)量構(gòu)建多目標(biāo)優(yōu)化模型，其次將前景理論用于模型中人員的非理性描述，最后設(shè)計了結(jié)合分段優(yōu)先規(guī)則、左下角填充規(guī)則和搜索插空填充規(guī)則的一種啟發(fā)式構(gòu)造算法，在 2 秒左右就可以得到滿足時間、空間以及人力資源約束的所有分段時空規(guī)劃方案。該研究突破了以往僅考慮船舶調(diào)度時間和空間規(guī)劃的現(xiàn)狀，設(shè)計出兼顧人力資源非理性的船舶分段時空規(guī)劃模型方法。本文的研究成果可以為船舶制造過程中的分段加工時空規(guī)劃調(diào)度問題的解決提供有效的輔助決策支持。未來可以聚焦不規(guī)則分段時空規(guī)劃以及多勞多得的激勵機制下的工人損失和收益劃分等問題進一步研究。

　　參考文獻:

　　[1] LEE K J, LEE J K, CHOI S Y. A spatial scheduling system andits application to shipbuilding: DAS-CURVE[J]. Expertsystems with applications, 1996, 10(3/4): 311-324.

　　[2] DIXIT V, VERMA P, RAJ P, et al. Resource and timecriticality based block spatial scheduling in a shipyard underuncertainty[J]. International journal of production research,2018, 56(22): 6993-7007.

　　[3] 馬少輝, 陸春霞. 船體不規(guī)則分段的動態(tài)空間調(diào)度算法[J].運籌與管理, 2014, 23(6): 281-287.MA Shaohui, LU Chunxia. A dynamic spatial scheduling algorithmfor irregular blocks in shipbuilding[J]. Operations research andmanagement science, 2014, 23(6): 281-287.

　　[4] ZHANG Zhiying, CHEN Jie. Solving the spatial schedulingproblem: a two-stage approach[J]. International journal ofproduction research, 2012, 50(10): 2732-2743.

　　[5] 鄭俊麗, 江志斌, 陳強, 等. 典型工藝和特殊布位約束下的船舶模塊空間調(diào)度算法[J]. 上海交通大學(xué)學(xué)報, 2009, 43(12): 1962-1967.ZHENG Junli, JIANG Zhibin, CHEN Qiang, et al. A spatialmodule scheduling algorithm with typical constraints oftechnology and location[J]. Journal of Shanghai Jiao Tonguniversity, 2009, 43(12): 1962-1967.

　　[6] ZHENG Junli, JIANG Zhibin, CHEN Qiang, et al. Spatialscheduling algorithm minimising makespan at block assemblyshop in shipbuilding[J]. International journal of productionresearch, 2011, 49(8): 2351-2371.

　　[7] 陶寧蓉, 蔣祖華, 劉建峰. 帶時間窗約束的船體分段空間調(diào)度問題[J]. 計算機集成制造系統(tǒng), 2010, 16(12): 2674-2679.TAO Ningrong, JIANG Zuhua, LIU Jianfeng. Spatial schedulingproblem with time window constraint for block assembly inshipbuilding[J]. Computer integrated manufacturing systems,2010, 16(12): 2674-2679.

　　[8] TAO Ningrong, JIANG Zuhua，ZHEN Lu. Spatial schedulingand workforce assignment problem in block assembly shop ofshipbuilding [J]. Asia-pacific journal of operational research，2014，31(1): 1-19.

　　作者：胡玉真, 張首昊, 李修橋, 張聳

轉(zhuǎn)載請注明來自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///dzlw/30067.html