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

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

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

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

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

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

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

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

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

　　1 模型

　　1.1 問(wèn)題描述

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

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

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

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

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

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

　　1.2 負(fù)載均衡

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

　　1.3 模型建立

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

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

　　2 算法設(shè)計(jì)

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

　　2.1 算法流程

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

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

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

　　3 算例分析

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

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

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

　　4 結(jié) 論

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

　　參考文獻(xiàn):

　　[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ī)則分段的動(dòng)態(tài)空間調(diào)度算法[J].運(yùn)籌與管理, 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] 鄭俊麗, 江志斌, 陳強(qiáng), 等. 典型工藝和特殊布位約束下的船舶模塊空間調(diào)度算法[J]. 上海交通大學(xué)學(xué)報(bào), 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] 陶寧蓉, 蔣祖華, 劉建峰. 帶時(shí)間窗約束的船體分段空間調(diào)度問(wèn)題[J]. 計(jì)算機(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)載請(qǐng)注明來(lái)自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///dzlw/30067.html