開(kāi)題報(bào)告--徐建祥

1、同濟(jì)大學(xué)碩士研究生學(xué)位論文選題報(bào)告及論文工作計(jì)劃課題名稱 船舶分段平面堆場(chǎng)調(diào)度與優(yōu)化方法的研究 學(xué)號(hào) 1130942 研究生 徐建祥 專業(yè)、年級(jí) 工業(yè)工程2011級(jí) 所在院、系 機(jī)械與能源工程學(xué)院 工業(yè)工程系 導(dǎo)師 張志英 副導(dǎo)師 選題時(shí)間 2012年10月 同濟(jì)大學(xué)研究生院2012 年 10 月30日一、立論依據(jù)課題來(lái)源、選題依據(jù)和背景情況、課題研究目的、理論意義和實(shí)際應(yīng)用價(jià)值1.課題來(lái)源上海市科技創(chuàng)新行動(dòng)計(jì)劃資助項(xiàng)目：面向船舶建造的協(xié)同制造關(guān)鍵技術(shù)與平臺(tái)開(kāi)發(fā)研究（項(xiàng)目代號(hào)：11DZ1121800）2. 選題依據(jù)、背景情況 從上世紀(jì)五六十年代開(kāi)始，世界船舶制造中心已經(jīng)歷多次從先行工業(yè)國(guó)家到后

2、起工業(yè)國(guó)家的轉(zhuǎn)移，目前，日本、韓國(guó)雖仍為世界造船大國(guó)，但世界船舶工業(yè)向中國(guó)轉(zhuǎn)移的趨勢(shì)已經(jīng)確立。船舶制造業(yè)的水平是一個(gè)國(guó)家的經(jīng)濟(jì)和技術(shù)實(shí)力的重要體現(xiàn)，我國(guó)船舶制造業(yè)還處在向現(xiàn)代造船模式轉(zhuǎn)換過(guò)程中，在生產(chǎn)組織和生產(chǎn)過(guò)程控制方面效率低下。這些年我國(guó)造船業(yè)取得了長(zhǎng)足的進(jìn)步，但在造船模式上與日韓兩個(gè)造船強(qiáng)國(guó)仍有一定差距。船舶分段是船體建造的基本單位，按每只船一百個(gè)分段計(jì)算，停放在廠區(qū)的分段數(shù)目多達(dá)幾百個(gè)。傳統(tǒng)造船模式中由于分段產(chǎn)品體積和重量都很大，搬遷運(yùn)輸很困難，在生產(chǎn)過(guò)程中不適宜到處搬運(yùn)。因此，一般采用堆場(chǎng)固定工位的生產(chǎn)模式。分段根據(jù)在堆場(chǎng)內(nèi)作業(yè)類型的不同分成進(jìn)場(chǎng)分段和出場(chǎng)分段。對(duì)于進(jìn)場(chǎng)分段，需要考慮

3、其放置堆場(chǎng)的位置以及相應(yīng)的最優(yōu)路徑；對(duì)于出場(chǎng)分段，則需要考慮其移出堆場(chǎng)的最優(yōu)路徑。臨時(shí)移動(dòng)分段是指由于擋道而不得不移動(dòng)的分段，其特點(diǎn)是“不得已而移之”。分段進(jìn)、出堆場(chǎng)的移動(dòng)路徑不唯一，不同的移動(dòng)路徑造成不等的臨時(shí)分段移動(dòng)量。堆場(chǎng)是船舶建造企業(yè)重要的場(chǎng)地資源，是船舶生產(chǎn)系統(tǒng)中不可或缺的部分，是分段脫胎后進(jìn)行后處理的堆放和暫存場(chǎng)所。根據(jù)功能的不同，一般堆場(chǎng)分成加工堆場(chǎng)和中轉(zhuǎn)堆場(chǎng)，加工堆場(chǎng)是分段脫胎后進(jìn)行預(yù)舾裝、檢驗(yàn)和修補(bǔ)等的作業(yè)的場(chǎng)所，而中轉(zhuǎn)堆場(chǎng)只是作為分段的臨時(shí)中轉(zhuǎn)地，不需要進(jìn)行任何作業(yè)處理。即進(jìn)入堆場(chǎng)的分段主要有四種情況：待報(bào)驗(yàn)的分段；待進(jìn)涂裝車間的分段；將要在堆場(chǎng)進(jìn)行修補(bǔ)打磨的分段；將要在堆

4、場(chǎng)預(yù)舾裝的分段。由于各種因素的影響，一方面，分段在組立部、涂裝部、搭載部之間的周轉(zhuǎn)流動(dòng)并不是“即時(shí)無(wú)縫”連接，往往需要移至堆場(chǎng)等待下游工位的需求信息。另一方面，分段完工后，要移進(jìn)堆場(chǎng)進(jìn)行報(bào)驗(yàn)、修補(bǔ)打磨、預(yù)舾裝等后續(xù)處理。直接導(dǎo)致制造完工的分段并不能及時(shí)送往船塢搭載，大大增加了對(duì)堆場(chǎng)資源的需求。實(shí)際上，堆場(chǎng)資源已成為限制船廠物流系統(tǒng)正常運(yùn)轉(zhuǎn)的瓶頸。由于不合理的調(diào)度機(jī)制，數(shù)目龐大的分段停放在廠區(qū)有限的堆場(chǎng)空間內(nèi)，因此，馬路上、通道上、廠區(qū)里凡是有空地的地方都用來(lái)存放分段，分段隨處可見(jiàn)，給生產(chǎn)帶來(lái)很多問(wèn)題：道路堵塞，影響到船廠物流系統(tǒng)的正常運(yùn)轉(zhuǎn)?；ㄙM(fèi)大量的人力和物力查找對(duì)號(hào)分段，嚴(yán)重影響了生產(chǎn)率，甚

5、至拖延工期。當(dāng)先出庫(kù)的分段堆放在里層時(shí)，需要移動(dòng)其他分段以騰出通道，這大大增加了堆場(chǎng)平板車的負(fù)荷，降低了堆場(chǎng)周轉(zhuǎn)率。堆場(chǎng)管理的目的就是根據(jù)生產(chǎn)的需要，結(jié)合船廠現(xiàn)有的設(shè)備、設(shè)施能力，合理安排分段進(jìn)出堆場(chǎng)的時(shí)間以及在堆場(chǎng)的存放位置，解決分段堆放無(wú)序的問(wèn)題。從而使運(yùn)輸車輛在完成分段移動(dòng)任務(wù)的同時(shí)，滿足臨時(shí)移動(dòng)分段數(shù)最小、堆場(chǎng)場(chǎng)地周轉(zhuǎn)率和利用率最大。目前，國(guó)內(nèi)很多船企試著尋找解決分段堆放無(wú)序問(wèn)題的方法，可是效果不盡如人意。在進(jìn)行分段堆場(chǎng)作業(yè)計(jì)劃時(shí)，往往會(huì)遇到很多難以預(yù)料的因素的影響，這就加大了計(jì)劃的難度，主要有以下幾個(gè)方面：天氣因素：堆場(chǎng)屬于室外場(chǎng)地，在雨雪天氣無(wú)法進(jìn)行作業(yè)，如修補(bǔ)打磨、預(yù)舾裝等；設(shè)備

6、因素：龍門吊等重要、關(guān)鍵設(shè)備，一旦出現(xiàn)故障，將直接導(dǎo)致外場(chǎng)工作停工；外協(xié)廠的影響：船廠在工作量超過(guò)負(fù)荷時(shí)就會(huì)把有些分段交給外協(xié)廠家來(lái)做，而外協(xié)廠家的送貨時(shí)間也是一個(gè)不確定因素；場(chǎng)地因素：由于事先無(wú)法預(yù)知的因素影響而不能使用，如船東檢驗(yàn)等。隨著船舶需求量逐年遞增及交貨期愈加緊張，船舶分段堆場(chǎng)不堪負(fù)荷，逐步成為生產(chǎn)瓶頸。因此，對(duì)船舶分段堆場(chǎng)的調(diào)度進(jìn)行研究并制定合理的堆場(chǎng)調(diào)度計(jì)劃已迫在眉睫。3.課題研究的目的及意義數(shù)目龐大的分段停放在有限的堆場(chǎng)空間內(nèi)，很容易造成堆放無(wú)序。而傳統(tǒng)的人工即時(shí)調(diào)度方法很難改變目前這種雜亂無(wú)章的局面，信息化程度低已成為堆場(chǎng)管理中的突出問(wèn)題。對(duì)比國(guó)外船廠的狀況可以發(fā)現(xiàn)，先進(jìn)的

7、堆場(chǎng)管理除擁有快速高效的運(yùn)輸硬件設(shè)備外，還應(yīng)有一套堆場(chǎng)管理支撐系統(tǒng)，而這正是解決船廠所面臨的堆場(chǎng)問(wèn)題的根本出路。堆場(chǎng)資源緊缺已成為船廠物流系統(tǒng)正常運(yùn)轉(zhuǎn)的制約因素，對(duì)堆場(chǎng)資源的合理計(jì)劃以及對(duì)分段移動(dòng)的最優(yōu)規(guī)劃迫在眉睫。因此，堆場(chǎng)計(jì)劃的信息化、系統(tǒng)化管理對(duì)船舶建造企業(yè)的健康迅速發(fā)展具有重要意義。對(duì)堆場(chǎng)管理的深入研究有助于實(shí)現(xiàn)對(duì)資源的合理規(guī)劃，使資源的利用率達(dá)到最優(yōu)，從而提高場(chǎng)地的周轉(zhuǎn)率，提高工作效率；有助于減少、甚至杜絕分段移動(dòng)過(guò)程中的無(wú)用工作，降低運(yùn)輸車輛的負(fù)荷，減少平板車的行駛距離，從而延長(zhǎng)設(shè)備設(shè)施的使用年限，減少油耗，降低生產(chǎn)成本；有助于保證物流系統(tǒng)的順暢無(wú)阻，從而及時(shí)響應(yīng)工位間的需求，縮短

8、生產(chǎn)周期，提高制造質(zhì)量；分段的有序堆放解決了交通干道堵塞的問(wèn)題，同時(shí)也消除了安全隱患；有助于企業(yè)5S工作的順利展開(kāi)?？傊瑢?duì)堆場(chǎng)作業(yè)計(jì)劃的研究將大大改善廠區(qū)的生產(chǎn)環(huán)境，對(duì)提高生產(chǎn)率、降低生產(chǎn)成本、縮短生產(chǎn)周期都有非常重要的影響。4.實(shí)際應(yīng)用價(jià)值目前，分段堆場(chǎng)的計(jì)劃都是依據(jù)調(diào)度員的經(jīng)驗(yàn)進(jìn)行的，不僅要求管理人員熟練掌握各個(gè)分段的幾何屬性，如大小、重量，還要求對(duì)生產(chǎn)流程爛熟于心，如移動(dòng)分段的上下游工位、緊后工序?qū)υO(shè)備設(shè)施的需求情況、生產(chǎn)周期等等。這種人工即時(shí)調(diào)度方法花費(fèi)了大量人力、物力以及時(shí)間，且一次只能安排一天的分段計(jì)劃，無(wú)法考慮后續(xù)的堆場(chǎng)計(jì)劃。它的局限性使得分段的堆放長(zhǎng)期處于無(wú)序狀態(tài)，很難使得利

9、用率達(dá)到最大，資源分配最優(yōu)化。利用本文所研究的方法，可以求解大規(guī)模調(diào)度問(wèn)題，一次可安排一周及以上的計(jì)劃，并且運(yùn)行算法程序可得到較優(yōu)的調(diào)度方案，充分利用堆場(chǎng)資源，提高作業(yè)效率。 二、文獻(xiàn)綜述國(guó)內(nèi)外研究現(xiàn)狀、發(fā)展動(dòng)態(tài)；所閱文獻(xiàn)的查閱范圍及手段考慮到分段堆場(chǎng)的實(shí)際情況及便于堆場(chǎng)調(diào)度問(wèn)題的研究，將堆場(chǎng)劃分為若干大小相等的正方形場(chǎng)地，即將分段用最小包絡(luò)矩形近似。分段在堆場(chǎng)中只能平面擺放，且只能朝場(chǎng)地的X、Y軸方向移動(dòng)，需要結(jié)合調(diào)度周期內(nèi)所有計(jì)劃分段進(jìn)出堆場(chǎng)的時(shí)間來(lái)安排分段在堆場(chǎng)中的停放位置，規(guī)劃其進(jìn)出堆場(chǎng)路徑。此類問(wèn)題和空間調(diào)度問(wèn)題、集裝箱堆場(chǎng)作業(yè)計(jì)劃問(wèn)題具有一定的相似性?？臻g調(diào)度問(wèn)題以空間利用率最大為

10、目標(biāo)，在空間布局的基礎(chǔ)上兼顧時(shí)間效率，綜合考慮空間因素和時(shí)間因素來(lái)安排生產(chǎn)調(diào)度計(jì)劃。針對(duì)這類問(wèn)題，目前專家學(xué)者普遍采用的解決方法是人工智能優(yōu)化算法和基于規(guī)則的啟發(fā)式方法1。在空間調(diào)度問(wèn)題中，分段在堆場(chǎng)中只能平面擺放，為研究方便通常將其的形狀假設(shè)為矩形或梯形。分段在堆場(chǎng)中要進(jìn)行加工處理，形狀會(huì)發(fā)生較大變化。針對(duì)船舶建造過(guò)程中的空間調(diào)度問(wèn)題，為了提高分段建造的場(chǎng)地利用率，同時(shí)縮短建造周期。 安排分段在堆場(chǎng)中的擺放位置和開(kāi)始加工時(shí)間，在滿足完工時(shí)間的前提下，以空間利用率最高為目標(biāo)。針對(duì)這類問(wèn)題，Lee等提出了基于船舶形狀的啟發(fā)式調(diào)度規(guī)則2；鄭俊麗等運(yùn)用形狀相似和工藝相似策略，提出了一種縮短最大完工時(shí)

11、間的船舶分段空間調(diào)度算法3；張志英等針對(duì)船體分段生產(chǎn)調(diào)度的多目標(biāo)性和動(dòng)態(tài)性，提出了一種改進(jìn)粒子群算法的動(dòng)態(tài)空間調(diào)度方法，以確定分段在加工平臺(tái)上的加工順序和空間布局位置4；陳潔等運(yùn)用運(yùn)籌學(xué)方法結(jié)合場(chǎng)地平均時(shí)空利用率指標(biāo)構(gòu)建綜合加工優(yōu)先順序、交貨期等因素的非線性規(guī)劃模型5；郭美娜等提出了一種基于樹(shù)搜索的動(dòng)態(tài)調(diào)度方法，將調(diào)度規(guī)劃周期分為調(diào)度準(zhǔn)備階段和局部調(diào)度階段來(lái)得到最優(yōu)調(diào)度6。王蕾等提出了基于分解策略的調(diào)度方法，將船體曲面分段空間調(diào)度問(wèn)題劃分為一系列分段排序和分段填空過(guò)程的算法7。在空間調(diào)度問(wèn)題中，分段都只能平面擺放，安排計(jì)劃時(shí)要充分的考慮時(shí)間和空間的相互影響、相互制約，這些特點(diǎn)與分段堆場(chǎng)調(diào)度問(wèn)題

12、很相似。但是這兩類問(wèn)題相比又存在諸多不同：1. 堆場(chǎng)中的作業(yè)場(chǎng)地規(guī)格都是相同的，進(jìn)入或出來(lái)堆場(chǎng)都只能通過(guò)固定的道路。當(dāng)分段要放置在里層的作業(yè)場(chǎng)地或從里層出來(lái)，需要移動(dòng)其他分段以騰出通道?？臻g調(diào)度問(wèn)題中，沒(méi)有劃分好的作業(yè)位置，分段可以直接從所在位置進(jìn)出場(chǎng)地；2.在空間調(diào)度問(wèn)題中，分段依據(jù)自身的形狀，再結(jié)合場(chǎng)地的空間，來(lái)選擇一個(gè)合適的放置位置，確定開(kāi)始加工時(shí)間，以實(shí)現(xiàn)整體空間調(diào)度的優(yōu)化；3. 船舶分段堆場(chǎng)調(diào)度需要規(guī)劃分段進(jìn)出堆場(chǎng)的路徑，而空間調(diào)度不考慮路徑問(wèn)題。由以上差異可看出空間調(diào)度問(wèn)題的思想可以為堆場(chǎng)調(diào)度提供很多有益的啟發(fā),但是不能直接應(yīng)用于堆場(chǎng)調(diào)度。集裝箱堆場(chǎng)作業(yè)計(jì)劃問(wèn)題以翻箱量最小、空間利

13、用率最大為目標(biāo)。集裝箱為標(biāo)準(zhǔn)化的長(zhǎng)方體，作業(yè)過(guò)程形狀不發(fā)生變化。集裝箱可以分層碼放于各貝位中，以龍門吊為主要搬運(yùn)工具，在堆場(chǎng)中可以往X、Y和Z軸方向移動(dòng)。針對(duì)集裝箱的翻箱量問(wèn)題，有學(xué)者通過(guò)建立最小生成樹(shù)模型，并運(yùn)用動(dòng)態(tài)規(guī)劃方法和啟發(fā)式算法求解模型確定最小翻箱量1-4。文獻(xiàn)5考慮集裝箱碼放順序的全序關(guān)系，設(shè)計(jì)單箱碼放算法求解動(dòng)態(tài)碼放模型。集裝箱堆場(chǎng)作業(yè)中箱位分配和翻箱量類似于船舶堆場(chǎng)中的分段停放位置和臨時(shí)移動(dòng)的分段數(shù)量，但兩者的碼放規(guī)則不同，前者屬于分層碼放，而后者是平面堆放。分段堆場(chǎng)調(diào)度問(wèn)題屬于NP-hard問(wèn)題。文獻(xiàn)16以最小化翻箱率為目標(biāo)，建立兩階段優(yōu)化模型，研究集中到達(dá)和分散到達(dá)兩種進(jìn)場(chǎng)

14、模式下的優(yōu)化效果，并進(jìn)行仿真模擬。文獻(xiàn)17運(yùn)用啟發(fā)式算法討論了考慮集裝箱重量等級(jí)的翻箱量最小化問(wèn)題。文獻(xiàn)18建立考慮集裝箱重量的出口箱區(qū)堆存模型并利用搜索技術(shù)求解該模型。文獻(xiàn)19以圖搜索和模式識(shí)別技術(shù)為基礎(chǔ)建立了出口箱混合順序作業(yè)堆場(chǎng)貝優(yōu)化模型。集裝箱堆場(chǎng)調(diào)度與分段堆場(chǎng)調(diào)度相似，但主要區(qū)別有：場(chǎng)地分配策略不同：由于船舶分段形狀不規(guī)則，不能壘放，只能平面堆放；而集裝箱多為長(zhǎng)方體，為避免場(chǎng)地浪費(fèi)，通常采用分層壘放。物體在堆場(chǎng)中的移動(dòng)方式不同：船舶分段通常體積龐大，重達(dá)幾百噸，不適合使用龍門吊從空中直線搬運(yùn)，而只能采用平板車從地面上運(yùn)輸分段。因此，分段在堆場(chǎng)中通常只能沿著場(chǎng)地的x軸或y軸方向平面移動(dòng)

15、(路徑可以是“z”字型)。目標(biāo)分段在堆場(chǎng)中的移動(dòng)路徑并不唯一，不同路徑產(chǎn)生的臨時(shí)分段移動(dòng)數(shù)量不等，從而存在著路徑的優(yōu)化問(wèn)題。而集裝箱相對(duì)重量比較輕，體積小，通常采用龍門吊將其直線運(yùn)輸?shù)侥康牡?。因此，集裝箱堆場(chǎng)作業(yè)計(jì)劃問(wèn)題的研究方法對(duì)船舶分段堆場(chǎng)的調(diào)度有一定啟發(fā)作用但不能套用。目前，國(guó)內(nèi)外針對(duì)船舶建造過(guò)程中的堆場(chǎng)調(diào)度問(wèn)題的研究較少。Changkyu等以臨時(shí)分段移動(dòng)量最少為目標(biāo)建立優(yōu)化模型，提出遺傳算法和改進(jìn)動(dòng)態(tài)啟發(fā)式算法對(duì)模型進(jìn)行求解47-48。然而這些方法都是在假定堆場(chǎng)場(chǎng)地固化(場(chǎng)地上用于騰空擺放分段的設(shè)施缺乏柔性)的生產(chǎn)環(huán)境中進(jìn)行，從而限定分段在堆場(chǎng)中的移動(dòng)路徑，導(dǎo)致分段必須筆直地進(jìn)出堆場(chǎng)，

16、大大增加了臨時(shí)分段移動(dòng)量?？紤]到提升堆場(chǎng)場(chǎng)地柔性的必要性，申鋼等以臨時(shí)分段移動(dòng)量最小為目標(biāo)建立最短路模型，提出分支定界法和啟發(fā)式規(guī)則來(lái)確定分段的移動(dòng)路徑和停放位置49。徐建祥等提出臨時(shí)場(chǎng)地用于暫時(shí)存放臨時(shí)移動(dòng)分段，采用改進(jìn)遺傳算法選擇分段在堆場(chǎng)中停放位置的最優(yōu)方案，并構(gòu)建啟發(fā)式規(guī)則來(lái)確定分段在堆場(chǎng)中的最優(yōu)進(jìn)、出場(chǎng)路徑50。但是所有上述研究都假設(shè)分段進(jìn)出堆場(chǎng)的道路確定且唯一，脫離了生產(chǎn)實(shí)際。開(kāi)放不同數(shù)量的道路將產(chǎn)生不同的調(diào)度結(jié)果，同時(shí)所研究問(wèn)題的復(fù)雜度也將提升。所閱文獻(xiàn)的查閱范圍及手段文獻(xiàn)查閱范圍：中外學(xué)術(shù)期刊、會(huì)議論文、學(xué)位論文、圖書、專利等文獻(xiàn)查閱手段：同濟(jì)大學(xué)圖書館數(shù)據(jù)庫(kù)：中國(guó)學(xué)術(shù)期刊、萬(wàn)

17、方數(shù)字資源系統(tǒng)、維普中國(guó)科技期刊、Elsevier數(shù)據(jù)庫(kù)等 關(guān)鍵詞：遺傳算法；啟發(fā)式規(guī)則；分段堆場(chǎng)；調(diào)度 查閱年限：1985-2012參考文獻(xiàn)：1 RYU C, SHIN J G, KWON O H,et al. Development of integrated and interactive spatial planning systems of assembly blocks in shipbuildingJ. International Journal of Computer Integrated Manufacturing, 2008,21(8): 911-922. 2 LEE J

18、K, LEE K J, PARK H K, et al. Developing scheduling systems for Daewoo shipbuilding:DAS projectJ. European Journal of Operational Research, 1997,97(2): 380-395. 3 鄭俊麗，陳峰，江志斌等. 縮短最大完工時(shí)間的船舶分段空間調(diào)度算法J. 上海交通大學(xué)學(xué)報(bào)，2009,43(4): 663-668. ZHENG Junli, CHEN Feng, JIANG Zhibin, et al. A spatiotemporal scheduling

19、algorithm minimizing make spanJ. Journal of Shanghai Jiaotong University, 2009,43(4):663-668. 4 張志英，楊克開(kāi)，于瑾維，等. 改進(jìn)粒子群算法的動(dòng)態(tài)空間調(diào)度方法J. 哈爾濱工程大學(xué)學(xué)報(bào)，2009,30(12): 1344-1350. ZHANG Zhiying, YANG Kekai, YU Jinwei, et al. Dynamic spatial scheduling approach based on improved particle swarm optimization algorithm

20、J. Journal of Harbin Engineering University, 2009,30(12): 1344-1350. 5 張志英，陳潔. 空間調(diào)度問(wèn)題的非線性規(guī)劃分析求解方法J. 計(jì)算機(jī)集成制造系統(tǒng)，2010,16(6): 1272-1277. ZHANG Zhiying, CHEN Jie. Nonlinear programming approach for spatial scheduling problemJ. Computer Integrated Manufacturing Systems, 2010,16(6):1272-1277. 6 郭美娜，李波. 基于樹(shù)

21、搜索的一種動(dòng)態(tài)空間調(diào)度方法J. 計(jì)算機(jī)工程與應(yīng)用，2007,43(14): 180184.GUOMeina, LI Bo.Dynamic spatial scheduling approach based on tree-searchJ. Computer Engineering and Applications, 2007,43(14): 180-184.7 王蕾，張志英. 基于規(guī)則的船體曲面分段空間調(diào)度方法J. 上海交通大學(xué)學(xué)報(bào)，2009,43(11):1709-1714.WANGLei, ZHANG Zhiying. Research on rule-basedspatial sched

22、uling in hull curved block constructionJ. Journal of Shanghai JiaoTong University, 2009,43(11): 1709-1714. 8 PIYUSH R, RAJ IV K S. Analytical and heuristic approaches for solving t he spatial scheduling problemC/ / Proceedings of the 37t h International Conference on Computers and Industrial Enginee

23、ring. Washington, D. C., USA: IEEE, 2007:20-23.8 Kirn K H, Park Y M, Ryll K R. Deriving decision rules to locate export containers in container yards J. European Journal of Operational Research, 2000(124): 89-101.9 Canrong Zhang, Weiwei Chen, Leyuan Shi, Li Zheng. A note on deriving decision rules t

24、o locate export containers in container yards J. European Journal of Operational Research, 2010, (205):483-485.10 張維英,林焰,紀(jì)卓尚,吳毅剛.出口集裝箱堆場(chǎng)取箱作業(yè)優(yōu)化模型研究J.武漢理工大學(xué)學(xué)報(bào),2006,30(2):314-317.11 Yusin Lee, Shih-liang Chao. A neighborhood search heuristic for pre-marshalling export containers J. European Journal of

25、Operational Research, 2009, 196(2):468-475. 12 Jiang Nan, Qian Mai, Qu Hong-tao, Shi Feng. Model and algorithm of container yard operation plans J. Journal of the China Railway Society,2009,31(5):8-16.13 Zhang, C, Resources planning in container storage yard D. Department of Industrial Engineering a

26、nd Engineering Management, Hong Kong University of Science and Technology, 2000: 6199.14 楊淑芹, 張運(yùn)杰, 王志強(qiáng). 集裝箱堆場(chǎng)問(wèn)題的一個(gè)數(shù)學(xué)模型及其算法(英文) J. 大連海事大學(xué)學(xué)報(bào),2002,32(28): 115-117.15 計(jì)三有, 高悅文. 集裝箱堆場(chǎng)減少倒箱率方法研究J. 水運(yùn)工程,2006, 61(8): 53-56.16 郝聚民, 紀(jì)卓尚, 林焰. 混合順序作業(yè)堆場(chǎng)BAY優(yōu)化模型J. 大連理工大學(xué)學(xué)報(bào), 2000, 40(1): 102-105.17 Won Young Yun, Yo

27、ng Seok Choi. A simulation model for container-terminal operation analysis using an object oriented approach J. International Journal of Production Economies, 1999, 59(3):311-329.18 Chuqian Zhang, Jiyin Liu, Yat-wah wan, Katta G.Murty, Richard J. IAnn. Storage apace allocation in container terminals

28、 J. Transportation Research Part B, 2003, 37(10):429-442.19 Kap Hwan Kim, Seung Hwan Won, Jae Kook Lim, Teruo Takahashi. An architectural design of control software for automated container terminals J. Computer & Industrial Engineering, 2004, 46(4):741754.20 Yusin Lee, Nai-Yun Hsu. An optimization m

29、odel for container pre-marshalling problem J. Computers Operations Research, 2007, 34(11): 32953313.21 CAO Jin-xin, SHI QI-xin, Der-Horng Lee. A decision support method for truck scheduling and storage allocation problem at container J. Tsinghua Science and Technology, 2008, 13(S1):211-216.22 Yusin

30、Lee, Shihliang Chao. A neighborhood search heuristic for pre-marshalling export containers J. European Journal of Operational Research, 2009, 196(2):468475.23 江南,王金紅,史峰, 李寧新,梁建平.集裝箱箱號(hào)模糊查詢方法J.鐵道學(xué)報(bào),2008,30(2):78-82.24 王斌.集裝箱碼頭堆場(chǎng)的一種動(dòng)態(tài)隨機(jī)堆存方法J. 系統(tǒng)工程理論與實(shí)踐,2007,27(4):149-155.25 李建忠,丁以中,王斌.集裝箱堆場(chǎng)空間動(dòng)態(tài)配置模型J.交通

31、運(yùn)輸工程學(xué)報(bào),2007,7(3):54-59.26 Kim K H, Kim H B. The optimal determination of the space requirement and the number of transfer cranes for import containers J. Computers and Industrial Engineering, 1998, 35(3-4):427-430.27 Gambardella L M, Rizzoli A E. The role of simulation and optimization in intermodal

32、 container terminals J. Artificial Intelligence, 2000(6):9-28.28 Mastrolilli M, Fornara N, Gambardella L M, et a1. Simulation for policy evaluation, planning and decision support in an intermodal container terminal J. Artificial Intelligence, 2000(36):69-90.29 Guan Yongpei, Xiao Wenqiang, Cheung R K

33、, et a1. A multiprocessor task scheduling model for berth allocation: heuristic and worst-case analysis J. Operations Research Letters, 2002, 30: 343-350.30羅薇,吳曉,劉璐,黃園園.基于最短路模型的動(dòng)態(tài)訂貨研究及應(yīng)用J.物流技術(shù),2010,29(6):61-63.31呂勝利,李靜鉑.最短路算法在生產(chǎn)最優(yōu)化中的應(yīng)用J. 控制工程,2006,13(5):404-406.32楊建軍,龍光正,高虹霓. 啟發(fā)式最短路算法J. 空軍工程大學(xué)學(xué)報(bào),200

34、2,3(6):64-67. 33錢頌迪.運(yùn)籌學(xué)M.北京:清華大學(xué)出版社,2005,261-268.34 Vis F A I, de Koster R. Transshipment of containers at a container terminal: An overview J. European Journal of Operational Research, 2003, 147(1): 1-16.35 Ebrn K Bish. A multiple-crane-constrained scheduling problem in a container terminal J. Euro

35、pean Journal of Operational Research, 2003, 144(1): 409-417.36 Ng WC, Mak K L. Yard crane scheduling in port container terminals J. Applied Mathematical Modelling, 2005, 29(3): 263-276.37 Chen L, Bostel N, Dejax P, et. A tabu search algorithm for the integrated scheduling problem of container handli

36、ng systems in a maritime terminal J. European Journal of Operational Research, 2008, 181(1): 40-58.38 Lau Y K H, Zhao Y. Integrated scheduling of handling equipment at automated container terminals J. International Journal of Production Economics, 2008, 121(2): 665-682.39 Liu c Y, Chang S C. Schedul

37、ing flexible flow shops with sequence-dependent setup effects J. IEEE Transactions on Robotics and Automation, 2000, 16(4): 408-419.40 曾慶成, 楊忠振. 集裝箱碼頭作業(yè)調(diào)度雙層規(guī)劃模型及求解算法J. 哈爾濱工程大學(xué)學(xué)報(bào),2007,28(3): 277-281.41 IRIS F A, de KOSTER R. Transshipment of containers at a container Terminal: an overview J. European

38、 Journal of Operational Research, 2003, 147(1): 1-16.42 KIM K H, PARK Y. A crane scheduling method for port container terminals J. European Journal of Operation Research, 2004, 156(3): 752-768.43 BISH E K. A multiple-crane-constrained scheduling problem in a container terminal J. European Journal of

39、 Operational Research, 2003, 114(1): 83-107.44 Changkyu Park *, Junyong Seo. Mathematical modeling and solving procedure of the planar storage location assignment problem J. Computers & Industrial Engineering, 2009, 57: 1062-1071.45 Changkyu Park *, Junyong Seo. Comparing heuristic algorithms of the

40、 planar storage locationassignment problem J. Transportation Research Part, 2010, 46: 171-185.46 張志英, 申鋼，劉祥瑞.基于最短路算法的船舶分段堆場(chǎng)調(diào)度研究J. 計(jì)算機(jī)集成制造系統(tǒng), 2012, 46: 171-185.47 張志英, 徐建祥，計(jì)峰. 基于GA的船舶分段堆場(chǎng)調(diào)度研究J. 上海交通大學(xué), 2012.三、研究?jī)?nèi)容學(xué)術(shù)構(gòu)想與思路、主要研究?jī)?nèi)容及擬解決的關(guān)鍵技術(shù)3.1學(xué)術(shù)構(gòu)想與思路分段按其在堆場(chǎng)中的作業(yè)類型可分為進(jìn)場(chǎng)分段、出場(chǎng)分段。進(jìn)場(chǎng)分段是脫胎后，要移進(jìn)堆場(chǎng)進(jìn)行后續(xù)處理或暫存的分段；出場(chǎng)

41、分段是指在堆場(chǎng)中完成了后續(xù)處理或暫存，要及時(shí)運(yùn)往船塢搭載的分段。臨時(shí)分段是指對(duì)目標(biāo)分段進(jìn)入或移出堆場(chǎng)造成阻礙的分段。臨時(shí)場(chǎng)地是用于暫時(shí)存放臨時(shí)分段的作業(yè)場(chǎng)地。在調(diào)度過(guò)程中需要先將臨時(shí)分段移至道路或臨時(shí)場(chǎng)地上，等計(jì)劃分段到達(dá)目的位置后，再將其移回原處。分段進(jìn)、出堆場(chǎng)的移動(dòng)路徑并不唯一，不同的移動(dòng)路徑造成不等的臨時(shí)分段移動(dòng)量。本課題以調(diào)度周期內(nèi)的分段為研究對(duì)象，首先針對(duì)船舶分段移動(dòng)計(jì)劃主要依靠經(jīng)驗(yàn)以及缺乏有效調(diào)度的現(xiàn)狀，研究建立以分段移動(dòng)度最小為目標(biāo)的優(yōu)化模型，模型綜合考慮了分段在堆場(chǎng)中的停放位置及進(jìn)、出場(chǎng)路徑。通過(guò)遺傳算法選擇分段在堆場(chǎng)中停放位置的最優(yōu)方案，并構(gòu)建啟發(fā)式規(guī)則來(lái)確定分段在堆場(chǎng)中的最

42、優(yōu)進(jìn)、出場(chǎng)路徑, 從而實(shí)現(xiàn)對(duì)模型的求解。其次，以開(kāi)放四條道路、增強(qiáng)場(chǎng)地柔性為前提條件，綜合考慮道路數(shù)量、場(chǎng)地柔性及堆場(chǎng)形狀等因素，以臨時(shí)分段移動(dòng)量最少為優(yōu)化目標(biāo)，通過(guò)遺傳算法確定計(jì)劃周期內(nèi)所有分段的停放位置，運(yùn)用動(dòng)態(tài)規(guī)劃算法并結(jié)合啟發(fā)式規(guī)則對(duì)分段在堆場(chǎng)中的調(diào)度問(wèn)題進(jìn)行建模。合理安排分段進(jìn)出堆場(chǎng)順序，確定分段在堆場(chǎng)中的最優(yōu)停放位置，規(guī)劃其進(jìn)、出堆場(chǎng)的移動(dòng)路徑，從而優(yōu)化堆場(chǎng)資源的利用率，提高堆場(chǎng)周轉(zhuǎn)率。最后以某船廠實(shí)際數(shù)據(jù)為例，對(duì)模型在堆場(chǎng)調(diào)度問(wèn)題中的應(yīng)用進(jìn)行實(shí)例驗(yàn)證，并通過(guò)對(duì)模型的求解得出較優(yōu)的堆場(chǎng)作業(yè)計(jì)劃。3.2研究的主要內(nèi)容3.2.1分段在堆場(chǎng)中停放位置的選擇 堆場(chǎng)調(diào)度問(wèn)題的復(fù)雜度主要是由于

43、進(jìn)場(chǎng)分段的不同放置位置的組合造成的。進(jìn)場(chǎng)分段選擇不同的停放位置會(huì)產(chǎn)生不等的分段移動(dòng)度，并影響后續(xù)的堆場(chǎng)計(jì)劃。對(duì)某周期內(nèi)計(jì)劃分段在堆場(chǎng)中的停放位置的最優(yōu)組合方案進(jìn)行研究，并制定合理的堆場(chǎng)計(jì)劃以充分利用堆場(chǎng)資源、減少分段移動(dòng)度、降低成本。3.2.2 分段在堆場(chǎng)中移動(dòng)路徑的確定計(jì)劃分段在進(jìn)入或移出堆場(chǎng)的過(guò)程中，如果有其他分段堵塞通道，則需將臨時(shí)分段先移至道路處或臨時(shí)場(chǎng)地上，等計(jì)劃分段到達(dá)目的位置后，再將臨時(shí)分段移回原處。分段進(jìn)、出堆場(chǎng)的移動(dòng)路徑并不唯一，不同的移動(dòng)路徑造成不等的分段移動(dòng)度。確定分段的移動(dòng)路徑需經(jīng)過(guò)兩個(gè)步驟：根據(jù)啟發(fā)式規(guī)則求出需經(jīng)過(guò)最少臨時(shí)分段數(shù)的路徑，即一般最優(yōu)路徑(不唯一)。引入臨

44、時(shí)場(chǎng)地，比較每條一般最優(yōu)路徑，確定具有最小分段移動(dòng)度的最優(yōu)路徑。3.2.3 堆場(chǎng)開(kāi)放不同道路數(shù)的研究分段進(jìn)出堆場(chǎng)的道路確定但并不唯一，開(kāi)放不同數(shù)量的道路將產(chǎn)生不同的調(diào)度結(jié)果，同時(shí)所研究問(wèn)題的復(fù)雜度也將提升。道路開(kāi)放程度越高，堆場(chǎng)各場(chǎng)地離道路的距離就越近，即分段在堆場(chǎng)中受到的阻礙程度就越低。為了模型能更適應(yīng)實(shí)際的生產(chǎn)情況，必須考慮不同道路數(shù)情況下的堆場(chǎng)調(diào)度問(wèn)題。3.2.4 分段堆場(chǎng)調(diào)度過(guò)程模型的建立制定合理的調(diào)度規(guī)則，為進(jìn)場(chǎng)分段安排適合的堆場(chǎng)，恰當(dāng)?shù)耐７盼恢茫?guī)劃計(jì)劃分段在堆場(chǎng)中的移動(dòng)路線。針對(duì)堆場(chǎng)道路開(kāi)放數(shù)量不同的情況，利用遺傳算法、動(dòng)態(tài)規(guī)劃和啟發(fā)式規(guī)則等方法建立模型，從而對(duì)堆場(chǎng)調(diào)度進(jìn)行優(yōu)化。

45、3.2.5分段不確定屬性的研究在船舶企業(yè)的實(shí)際生產(chǎn)中，分段進(jìn)場(chǎng)時(shí)間、在堆場(chǎng)中加工或等待時(shí)間、出場(chǎng)時(shí)間都可能發(fā)生變化。為了保證生產(chǎn)過(guò)程正常、滿意地進(jìn)行，必須考慮存在不確定性情況下的堆場(chǎng)調(diào)度問(wèn)題，使其更能適應(yīng)實(shí)際的生產(chǎn)情況。3.2.6數(shù)值實(shí)驗(yàn) 1.分支定界法可求出最優(yōu)方案，但遍歷的特性使其只能求解小規(guī)模問(wèn)題。而智能算法由于其搜索的特性可用于研究大規(guī)模調(diào)度問(wèn)題。筆者將分枝定界法作為Benchmark對(duì)遺傳算法進(jìn)行可行性分析。2.堆場(chǎng)場(chǎng)地柔性大小以及道路數(shù)量是堆場(chǎng)的主要狀態(tài)參數(shù)。筆者將根據(jù)這兩不同的堆場(chǎng)狀態(tài)參數(shù)進(jìn)行仿真實(shí)驗(yàn),最后對(duì)不同參數(shù)的不同結(jié)果進(jìn)行分析。3.2.7模型可解性分析在船舶堆場(chǎng)調(diào)度問(wèn)題中

46、，增大堆場(chǎng)的尺寸、增加待調(diào)度分段的數(shù)量或者降低堆場(chǎng)的初始狀態(tài)的利用率(即增大初始狀態(tài)中空?qǐng)龅氐膫€(gè)數(shù))，都將會(huì)提高算法求解的難度，算法耗時(shí)也會(huì)相應(yīng)變長(zhǎng)。其中堆場(chǎng)的尺寸主要是對(duì)啟發(fā)式算法求解分段的進(jìn)出場(chǎng)路徑產(chǎn)生影響，而后兩個(gè)因素主要是增加了進(jìn)場(chǎng)分段在堆場(chǎng)中的放置位置的可行方案數(shù)，從而增大求解空間。3.2.8實(shí)例驗(yàn)證結(jié)合生產(chǎn)實(shí)際，依據(jù)分段在堆場(chǎng)中將要完成的后續(xù)作業(yè)的種類及其對(duì)堆場(chǎng)設(shè)施的要求，考慮到各個(gè)堆場(chǎng)的尺寸及相關(guān)設(shè)施，以船廠堆場(chǎng)計(jì)劃的實(shí)際數(shù)據(jù)進(jìn)行仿真。對(duì)仿真結(jié)果進(jìn)行分析評(píng)價(jià)，驗(yàn)證模型的正確性。3.3 研究擬解決的關(guān)鍵技術(shù)3.3.1 場(chǎng)地分配方法堆場(chǎng)調(diào)度問(wèn)題屬于NP-hard問(wèn)題，其復(fù)雜性主要是由

47、于進(jìn)場(chǎng)分段不同放置位置的組合造成的。近幾年各種智能算法逐漸被引入到調(diào)度問(wèn)題中，遺傳算法作為一種非確定性的擬生態(tài)隨機(jī)優(yōu)化算法在調(diào)度問(wèn)題中得到了廣泛的應(yīng)用，出于其具有不依賴于問(wèn)題模型的特性、全局最優(yōu)性、隱含并行性等特點(diǎn)，正越來(lái)越激起人們研究與應(yīng)用的興趣。本文的研究擬以分段移動(dòng)度、堆場(chǎng)利用率等為優(yōu)化目標(biāo)，運(yùn)用遺傳算法確定進(jìn)場(chǎng)分段在堆場(chǎng)中的停放位置的最優(yōu)方案。3.3.2 路徑優(yōu)化技術(shù)分段在堆場(chǎng)中的移動(dòng)路徑并不唯一，不同的路徑產(chǎn)生不同的分段移動(dòng)度。通過(guò)引入臨時(shí)場(chǎng)地存放臨時(shí)分段，減少分段移動(dòng)度，降低產(chǎn)生相同分段移動(dòng)度的路徑的概率。同時(shí)采用啟發(fā)式算法和動(dòng)態(tài)規(guī)劃并結(jié)合啟發(fā)式規(guī)則來(lái)確定分段在堆場(chǎng)中的最優(yōu)進(jìn)、出場(chǎng)

48、路徑, 從而實(shí)現(xiàn)對(duì)模型的求解。3.3.3 堆場(chǎng)調(diào)度的數(shù)學(xué)模型 針對(duì)堆場(chǎng)開(kāi)放不同道路數(shù)以及場(chǎng)地不同柔性的情況，考慮以臨時(shí)場(chǎng)地存放臨時(shí)分段，研究建立以臨時(shí)分段移動(dòng)量最少為目標(biāo)的調(diào)度模型，并采用動(dòng)態(tài)規(guī)劃、啟發(fā)式規(guī)則、智能算法等對(duì)模型進(jìn)行分析求解。 3.4研究方法、技術(shù)路線、實(shí)施方案及可行性分析3.4.1研究方法(1) 深入觀察船舶分段堆場(chǎng)調(diào)度過(guò)程，詳細(xì)了解船廠堆場(chǎng)作業(yè)的實(shí)際情況與不足；(2) 查閱及整理文獻(xiàn)資料，掌握本課題的研究現(xiàn)狀以及與該課題相似的空間調(diào)度和集裝箱堆場(chǎng)調(diào)度問(wèn)題的主要解決方法，對(duì)方法進(jìn)行比較分析，確定適合本課題的解決方法；(3) 根據(jù)堆場(chǎng)調(diào)度問(wèn)題的特點(diǎn)，定義適當(dāng)?shù)臎Q策變量，通過(guò)研究決

49、策變量之間的函數(shù)關(guān)系，確定問(wèn)題的約束以及目標(biāo)函數(shù)，運(yùn)用運(yùn)籌學(xué)、啟發(fā)式規(guī)則、遺傳算法等建立數(shù)學(xué)模型；(4) 結(jié)合遺傳算法對(duì)堆場(chǎng)調(diào)度模型進(jìn)行編碼，并通過(guò)遺傳操作，確定分段在堆場(chǎng)中停放位置的最優(yōu)組合方案；(5) 將改進(jìn)的最短路算法與遺傳算法進(jìn)行嵌套，并通過(guò)最短路算法搜尋分段在堆場(chǎng)中的最優(yōu)進(jìn)、出場(chǎng)路徑, 從而實(shí)現(xiàn)對(duì)模型的求解；(6) 依據(jù)建立的數(shù)學(xué)模型，以船廠堆場(chǎng)調(diào)度的實(shí)際數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證，運(yùn)用Visual Studio2010計(jì)算機(jī)軟件編寫程序進(jìn)行模擬，并對(duì)模擬結(jié)果進(jìn)行分析評(píng)價(jià)。3.4.2技術(shù)路線1) 確定堆場(chǎng)實(shí)際作業(yè)過(guò)程、堆場(chǎng)調(diào)度目標(biāo)、調(diào)度計(jì)劃數(shù)據(jù)等；2) 查閱和整理文獻(xiàn)，結(jié)合船舶分段堆場(chǎng)調(diào)度的特點(diǎn)，確定合適的研究方法；3) 運(yùn)用運(yùn)籌學(xué)方法、遺傳算法、啟發(fā)式規(guī)則等建立數(shù)學(xué)模型；4) 編寫算法程序求解模型；5) 通過(guò)實(shí)例驗(yàn)證，對(duì)算法結(jié)果及可行性進(jìn)行比較、分析與評(píng)價(jià)。研究的技術(shù)路線如下圖1所示。 圖1 技術(shù)路線圖3.4.3方案實(shí)施與可行性分析方案實(shí)施：(1) 查閱、收集各種資料，對(duì)本課題進(jìn)行分析總結(jié)。(2) 根據(jù)課題的具體要求及任務(wù)安排，確定課題研究的整體框架。(3) 運(yùn)用運(yùn)籌學(xué)方法、遺傳算法、啟發(fā)式規(guī)則等