本文摘要：摘 要：為研究考慮人力資源以及人的非理性因素的船舶分段加工時空規劃調度問題，本文依據前景理論，提出了一種新的優化模型方法。首先綜合考慮多個場地之間空間和人力資源負載均衡、工期以及分段延誤等多個優化目標，將時間、空間和人力資源限制等作為約束條件，構建多
摘 要：為研究考慮人力資源以及人的非理性因素的船舶分段加工時空規劃調度問題，本文依據前景理論，提出了一種新的優化模型方法。首先綜合考慮多個場地之間空間和人力資源負載均衡、工期以及分段延誤等多個優化目標，將時間、空間和人力資源限制等作為約束條件，構建多目標優化模型，并將人的非理性心理在人力資源負載均衡中加以考慮。其次，提出了一種結合左下角填充與搜索插空填充的分段時空規劃的高效算法。最后，實際和仿真運行表明該模型方法能夠在數秒之內得到上百塊的規劃方案，充分驗證了其實用性和高效性。該研究結果將為船舶分段的時空規劃調度效率提升提供有效的理論和方法支持。
關鍵詞：人力資源;船舶分段;時空規劃;負載均衡;前景理論;非理性;多目標優化;啟發式算法
船舶制造屬于勞動密集型產業，除了占用大量的時間和空間資源外，人力資源也是不可忽視的重要因素。據了解，建造一艘 7.5 萬噸級的散貨船，中國需要近 100 完工時，一個年造船能力在 140 萬載重噸左右的船廠，需要生產作業工人 5000 名左右。近幾年，由于地理環境艱苦等因素，造船廠人員流失情況加重，給船舶制造產業帶來嚴峻的挑戰。船舶分段加工作為船舶制造產業的重要環節之一，同樣受人力資源的影響較大。考慮工作區域的時間、空間和人力資源的限制，實現對船舶分段加工調度的有效管理，往往是提高造船廠生產力的關鍵措施。
然而，人力資源不同于其他設備資源，他們的主觀或非理性心理會影響工作的調度安排。因此，有必要對考慮非理性人力資源的船舶分段加工時空規劃調度問題進行優化研究，以提高船舶制造的生產效率。Lee 等[1]首次開始研究船舶分段加工調度問題，將船舶分段的時空規劃問題運用三維裝箱理論進行描述和求解。自此，船舶分段加工調度逐漸引起了諸多學者的長期關注。當前船舶分段調度的研究重點主要在于如何提高時間和空間等資源的利用效率。在時間資源上主要研究如何縮短工期[2]或降低分段的延誤情況;
對空間資源的研究主要分為兩類，單加工場地旨在提高空間利用率[4]，而對于多加工場地來說則是多場地之間的工作量均衡[5]。由于該類問題是 NP-hard[6]，對該類問題的求解主要聚焦于智能優化方法和基于優先規則的啟發式構造方法。大部分研究運用禁忌搜索[7]和遺傳算法[2,8-11]等智能算法來求解船舶分段調度問題。
遺傳算法等智能優化算法的優點是可以很有效地處理多目標優化，但同時也會因為算法復雜度太高、內部規則不透明而導致無法在生產實踐中展開應用。基于優先規則的船舶分段調度是當前的研究熱點，多數文獻綜合考慮分段加工時間、分段最早開始時間、分段最遲完工時間以及分段后續加工數量等各項指標[2,5,6]作為分段排序的依據，常用的填充規則包括左下角填充規則[12]、時空相似規則[13]、對角填充規則[14]等。
然而，上述優先規則主要考慮未加工分段的時空特點，而沒有考慮已加工完成的分段對加工空間的擴充。綜上所述，當前對船舶分段加工調度問題的研究主要集中于對時間和空間資源的規劃，缺少人力資源約束對船舶分段調度優化的研究，尤其缺少人的非理性因素對船舶分段調度優化的影響分析。另外，在調度優先規則上主要聚焦于未加工分段的時空特點，而沒有考慮已完成分段移除后對時空規劃的影響。
基于此，本文針對船舶分段加工多場地調度優化問題展開研究。主要創新點如下：首先，綜合考慮空間資源、時間資源以及人力資源，構建船舶制造過程中的分段加工調度的多目標優化模型;其次，運用前景理論在模型目標中將人力資源的非理性心理下的主觀損失有效表達出來;最后基于分段優先規則、左下角填充規則和搜索插空填充規則設計一種改進的混合啟發式構造算法，對船舶分段加工調度問題進行高效快速求解。該模型方法不僅可以為現實中的船舶分段加工時空規劃調度問題提供有效的輔助決策支持，也對船舶空間調度優化相關理論方法進行了有效補充。
1 模型
1.1 問題描述
當前船舶制造還無法完全實現智能化制造，因此分段加工過程不僅需要懸臂起重機等專業設備，還需要人工的輔助才能完成。每一個分段加工場地可以看作是一個二維空間。一般情況下，分段和加工場地的形狀大多為矩形或不規則多邊形，本文假設分段和加工場地形狀為矩形;分段可旋轉 0 度或 90 度放置。
本文的多場地船舶分段加工調度問題可以定義為指定各分段的加工場地、加工順序、加工方位，使其在滿足加工時間、空間和人力資源約束的前提下，達到所有加工場地的空間負載均衡偏差最小、人力資源負載均衡偏差最小、總工期最短、分段延誤數量最少的優化目標。空間負載均衡偏差是指每個加工場地的單位空間承擔的的工作量與平均單位空間工作量之間的差別。人力資源負載均衡偏差是指在考慮人員主觀損失的前提下，每個加工場地之間單位人員任務量分配與平均值之間的差別。
空間和人力資源負載均衡的表示方法。工期是指最后一個分段加工完成的時刻。延誤分段是指實際完工時刻晚于最遲完工時刻的分段。船舶分段加工調度問題的約束限制分別介紹如下：首先，時間約束包括：
1)各分段實際開始加工時刻不能早于最早開始加工時刻;2)各分段實際完工時刻不能晚于最遲完工時刻，否則認定為該分段加工出現延誤;3)各分段加工過程不能出現中斷。其次，空間約束包括：1)每個分段只能處于一個加工場地;2)各分段不能超出加工場地的邊界;3)各分段之間在二維空間不能重疊;4)各分段不能隨意放置，只能旋轉 0度或 90 度;5)各分段在加工過程中不能出現移動。
人力資源約束是指在每個加工時段，各分段需要的工人數量不能超過該加工空間提供的工人數量。在一個矩形的加工場地中，需要調度 5 個矩形分段。 給出了各個分段的規格大小、加工時間、需要的工人數量、最早開始時刻以及最遲完工時刻。該加工空間大小為 10×10，工人組數的限制是 5。
分段 1 在第一天開始加工;分段 2 和分段 3 在第 2 天開始加工;由于工人數量的限制，分段 4 無法按照最早開始時刻在第 3 天開始加工，只能在第 4 天開始加工，同時由于加工場地的空間約束，分段 4 旋轉之后可以放入加工場地;由于工人數量和空間的限制，分段 5 無法按照最早開始時刻在第 3 天開始加工，只能在第 5 天開始加工，實際完工時刻為第 8 天，晚于分段 5 的最遲完工時刻，因此出現延誤分段。最后在第 8 天結束，所有的分段加工完畢。
1.2 負載均衡
在加工過程中，不僅要考慮空間任務量的均衡，還要考慮人力資源工作量的均衡。考慮到人在面對不同的負載差別時，會有自己的主觀判斷。因此本文用前景理論的若干個特征[15,16]來描述人力資源負載均衡偏差：1)人力資源的主觀損失或收益是相對于參考點來說的，本文將所有場地的平均人力資源負載作為參考點;2)相對收益來說，人們對損失更敏感，本文假設：若某個場地的人力資源負載高于平均負載，則該場地的人力資源會承擔損失，否則，會獲得收益;3)人們對在面對損失和收益時分別會產生風險追尋和風險規避的傾向。綜合以上特征，我們給出各場地的單位人員負載均衡偏差表達式。該表達式的值越小，表明各場地的人員負載越均衡。
1.3 模型建立
本文建立了一個非線性規劃模型，對考慮人力資源的船舶分段加工的時空規劃調度優化問題進行具體描述。模型是以左下角為原點，在加工空間上建立平面直角坐標系，利用坐標數值表示分段的放置位置。
約束(14)保證每個分段都不能在最早開始時間之前開始加工;約束(15)和 (16)表示如果分段在最遲完工時刻之后仍在加工，則出現了延誤;約束(17)保證了在每個加工時間段，工人數都可以滿足加工需求;約束(18)是為了保證每個加工時間段加工空間的面積是充足的;約束(19)和約束(20)確保每個分段在加工時不越界，其中也包含了分段的旋轉情況;約束(21)和 (22)是對兩端點坐標之差的具體計算規則;約束(23)是表述分段在空間上不重疊;約束(24)和 (25)保證分段在加工過程中不能移動;約束(26)-(31)對模型的決策變量進行了定義。
2 算法設計
考慮到非線性優化模型的復雜性，本文基于現實中分段加工的優先規則和搜索插空填充算法，對傳統的左下角填充搜索算法進行改進，設計了改進的混合啟發式構造算法。
2.1 算法流程
本文算法的具體流程，首先，計算各分段的優先度，按照優先規則對分段進行分組，并對每個分段分配場地。然后，按照優先序依次對各場地內的分段進行操作，對于每個場地內未加工完成的分段，依次在各個時間判斷分段所處的狀態，并在合適的加工空間擺放。直到最后，所有的分段擺放完成，算法結束。
2.2 分段的場地分配本文考慮所有分段的最遲完工時間和最早開始時間對它們 進行排序， 將排好序的 分段分成round(1/2)組，將每個組的分段分到每個加工場地，本文采取空間負載均衡偏差和人力資源負載均衡偏差的比重各占 50%的方式，進行場地的分段分配。本文涉及到的分段位置，均指該物分段的左下角坐標。2.3 分段放置分段的放置以天為時間單位，在移除已加工完成的分段時，需要記錄下“空缺位”，為后續的分段擺放提供搜索依據。
(1)分段移除：若分段放入時間和加工時間之和等于當前時間，則將分段移除，即該分段加工完畢。此時該位置標記為一個“空缺位”。(2)分段填充：如果工人數還有剩余，就按照分段排序遍歷所有分段，對于最早開始時間等于當前時間的分段，進行插入擺放操作：首先遍歷所有“空缺位”，考慮旋轉的情況下檢驗此分段是否可以放入。若無法放入則執行順序擺放操作：首先確定該分段的橫坐標值，然后根據重疊規則確定縱坐標值。循環執行上述操作，當所有的分段都加工完畢，則總任務完成，該時間即為總工期。
3 算例分析
本文設計了兩組算例分析，進行優化模型方法的分析驗證。第一組算例為來源于某船廠的實際算例[13]，第二組算例是隨機產生的測試數據。實驗環境為運行在 Windows 10(64 位)操作系統下的Intel(R) Core(TM)i7-4510U CPU @ 2.00GHz (8GRAM) 筆記本，并采用 MATLAB(版本 R2016a)軟件編制程序。
當分段規模為 5 時，CPLEX 和啟發式構造算法得出的結果相差不大，但是在程序運行效率上，本文的算法更占優勢。當分段規模達到 25 及更大時，CPLEX 商業軟件無法得到非線性規劃的優化結果。而本文的算法僅在 2 秒左右就可以得到 100 多塊分段的時空調度優化方案。
為了驗證考慮人力資源以及人的非理性對模型優化結果的影響，將本文的模型方法與兩種標桿方法進行對比，標桿方法 1 在分段規劃時不考慮人力資源的負載均衡，標桿方法 2 是在規劃時雖然考慮人力資源的負載均衡，但是忽略人的非理性心理。雖然由本文的模型方法得到的空間負載均衡值差于標桿方法 1，但是工人負載均衡偏差明顯優于標桿方法 1，并且空間和工人負載均衡平均偏差也優于標桿方法 1，尤其當分段規模較大時，平均值呈現出量級上的差別。與工人負載均衡偏差類似，當分段規模較大時，工期和分段延誤數量也顯著優于標桿方法 1。與標桿方法 2 相比，在分段規模較大時，本文的模型方法的優勢也能體現出來。
4 結 論
本文針對考慮人力資源的船舶分段時空規劃調度優化問題，重點在以下三個方面取得了一定研究成果。首先，基于最小化多個場地之間的空間、人力資源負載均衡偏差、工期和分段延誤數量構建多目標優化模型，其次將前景理論用于模型中人員的非理性描述，最后設計了結合分段優先規則、左下角填充規則和搜索插空填充規則的一種啟發式構造算法，在 2 秒左右就可以得到滿足時間、空間以及人力資源約束的所有分段時空規劃方案。該研究突破了以往僅考慮船舶調度時間和空間規劃的現狀，設計出兼顧人力資源非理性的船舶分段時空規劃模型方法。本文的研究成果可以為船舶制造過程中的分段加工時空規劃調度問題的解決提供有效的輔助決策支持。未來可以聚焦不規則分段時空規劃以及多勞多得的激勵機制下的工人損失和收益劃分等問題進一步研究。
參考文獻:
[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] 馬少輝, 陸春霞. 船體不規則分段的動態空間調度算法[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] 鄭俊麗, 江志斌, 陳強, 等. 典型工藝和特殊布位約束下的船舶模塊空間調度算法[J]. 上海交通大學學報, 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] 陶寧蓉, 蔣祖華, 劉建峰. 帶時間窗約束的船體分段空間調度問題[J]. 計算機集成制造系統, 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.
作者：胡玉真, 張首昊, 李修橋, 張聳
轉載請注明來自發表學術論文網：http://www.zpfmc.com/dzlw/30067.html
