符昊，葛洪偉，邵長魯，朱亮

江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫 214122

造船監(jiān)理員調(diào)度模型和混合遺傳算法求解

符昊，葛洪偉，邵長魯，朱亮

江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫 214122

有效快速地調(diào)度不同專業(yè)的造船監(jiān)理員至不同廠區(qū)進(jìn)行監(jiān)理工作可以提高船舶建造效率，確保船只建造質(zhì)量。針對我國造船監(jiān)理公司監(jiān)理員調(diào)度方面缺乏通用模型和調(diào)度手段落后的問題，建立起帶有一系列硬性約束和軟性約束的數(shù)學(xué)模型。隨后針對該數(shù)學(xué)模型采用了基于模擬退火遺傳算法的混合遺傳算法進(jìn)行求解。模擬仿真實(shí)驗(yàn)表明該模型與算法取得了理想效果。

造船監(jiān)理員調(diào)度；船舶建造；人員調(diào)度；混合遺傳算法；NP問題

1 引言

我國作為全球最大的造船國，據(jù)初步統(tǒng)計(jì)，在2011年度中國全年造船完工量約為6 800萬載重噸，占全球份額的42.5%。這為我國造船業(yè)下一步技術(shù)創(chuàng)新和產(chǎn)業(yè)升級打下了良好的基礎(chǔ)。由于船舶建造的工藝復(fù)雜，耗資巨大，施工的周期長，對其建造過程進(jìn)行監(jiān)理就成為必不可少的環(huán)節(jié)[1]。通常船東會委托監(jiān)理公司進(jìn)行船舶建造的監(jiān)理工作以確保船舶建造質(zhì)量。監(jiān)理人員涵蓋船舶建造中所涉及的各類專業(yè)，分別有船體、船機(jī)、船電和特殊專業(yè)工程技術(shù)人員，這里的特殊專業(yè)工程技術(shù)人員是根據(jù)船舶的主要工作性能來決定的[2]。為滿足不同廠區(qū)在船舶建造過程中對不同專業(yè)造船監(jiān)理員需求的變更，監(jiān)理公司需要在船舶建造的每個(gè)階段對公司內(nèi)的各專業(yè)監(jiān)理員重新合理調(diào)度。每個(gè)廠區(qū)對各專業(yè)監(jiān)理員數(shù)量的需求和調(diào)度開銷少這些硬性約束是每次調(diào)度應(yīng)當(dāng)滿足的。為實(shí)現(xiàn)調(diào)度的人性化，監(jiān)理員之間的默契程度以及他們對廠區(qū)的偏好這些軟性約束也應(yīng)予以關(guān)注。因此造船監(jiān)理員調(diào)度問題是較為復(fù)雜的組合優(yōu)化問題，屬NP問題。

迄今為止，監(jiān)理公司調(diào)度監(jiān)理員的方式依舊是傳統(tǒng)的手工調(diào)度。這樣調(diào)度效率較低，人工成本高，考慮的方面有限，往往不能很好地滿足實(shí)際的需求；尤其是在待調(diào)度人員人數(shù)多、調(diào)度情況復(fù)雜的時(shí)候，人工調(diào)度難以實(shí)施；所以利用計(jì)算機(jī)實(shí)現(xiàn)自動化調(diào)度是未來發(fā)展的目標(biāo)。關(guān)于人員分配和調(diào)度的組合優(yōu)化的問題，國外起步較早，研究較多。近年來，如Sabar、Montreuil和Frayret對裝配中心員工調(diào)度的研究[3-4]、Ozgur等人對產(chǎn)業(yè)部門人員分配的探究[5]以及Ruibin等人對護(hù)士排班問題的研究[6-7]等等已研制出多種基于軟計(jì)算的方法。但國外為相關(guān)問題建立的模型有較強(qiáng)的西方國家特點(diǎn)，與國內(nèi)管理存在差異。我國對這方面問題的研究起步較晚。直到近年國內(nèi)才出現(xiàn)例如任守綱等人從我國軟件開發(fā)企業(yè)角度針對軟件項(xiàng)目人力資源調(diào)度的研究[8]；沈吟東等人針對護(hù)士排班問題采用貼合實(shí)際護(hù)士排次類型和排班約束建立適應(yīng)中國國情的問題模型[9-10]等。但他們考慮的問題較為簡單，算法執(zhí)行效率也有待改進(jìn)。

針對造船監(jiān)理員調(diào)度的研究至今國內(nèi)、外鮮有報(bào)道。對于造船業(yè)，有獨(dú)特的行業(yè)特殊性，如果只是簡單地套用其他行業(yè)的相關(guān)研究則難以滿足企業(yè)需求。本文通過對國內(nèi)造船業(yè)現(xiàn)狀的了解分析，考慮了對于造船業(yè)具有普遍適應(yīng)性的監(jiān)理員調(diào)度問題。在同時(shí)考慮硬性和軟性約束的基礎(chǔ)上，建立了一個(gè)適應(yīng)我國造船監(jiān)理公司監(jiān)理員調(diào)度問題的整數(shù)規(guī)劃（ILP）模型。并針對此問題采用了模擬退火遺傳算法進(jìn)行仿真實(shí)驗(yàn)求解，實(shí)現(xiàn)了對模型和求解算法的驗(yàn)證。

2 造船監(jiān)理員調(diào)度問題描述

本文研究的造船監(jiān)理員調(diào)度問題是指：給定一個(gè)調(diào)度周期內(nèi)的全部可調(diào)度的造船監(jiān)理員及每名監(jiān)理員掌握的專業(yè)；給定在該周期內(nèi)全部廠區(qū)對各專業(yè)監(jiān)理員的需求數(shù)目。要求在基本滿足所有廠區(qū)所需監(jiān)理員數(shù)目的情況下（考慮到現(xiàn)實(shí)中臨時(shí)員工的存在，允許出現(xiàn)需求數(shù)目超出可調(diào)度監(jiān)理員數(shù)目的情況），編制出一個(gè)最有效（即滿足硬性約束和軟性約束）的造船監(jiān)理員調(diào)度方案。為了方便管理并且考慮到“一人多?！钡那闆r，要對不同專業(yè)的監(jiān)理員進(jìn)行統(tǒng)一調(diào)度，因此使得該問題變得復(fù)雜。

根據(jù)船舶建造監(jiān)理的普遍特性，本文設(shè)定：

每名監(jiān)理員在一個(gè)調(diào)度周期內(nèi)只允許調(diào)度一次；每名監(jiān)理員掌握的專業(yè)在一個(gè)調(diào)度周期內(nèi)是固定不變的；對每名監(jiān)理員的調(diào)度都應(yīng)以滿足廠區(qū)對特定專業(yè)監(jiān)理員數(shù)量需求為前提；調(diào)度應(yīng)考慮每名監(jiān)理員的地域偏好和他們之間的人際關(guān)系。

假設(shè)一個(gè)調(diào)度周期為一個(gè)月，對于給定n名造船監(jiān)理員的一個(gè)調(diào)度方案可以用一張二維表格表示（見表1）。其中第一行表示監(jiān)理員的編號，第二行表示該監(jiān)理員被派遣去往的廠區(qū)編號。

表1 2012年5月XX船舶建造監(jiān)理公司員工調(diào)度方案

如表1中的方案滿足設(shè)定的要求，則為可行方案，否則為不可行方案。同時(shí)，要找出可行方案中開銷最少的最佳方案。

3 造船監(jiān)理員調(diào)度問題建模

針對上述從實(shí)際工作中提煉出的造船監(jiān)理員調(diào)度問題，首先建立一個(gè)考慮硬性約束的整數(shù)規(guī)劃（ILP）模型，然后建立更人性化的擴(kuò)展模型，使其能夠反映造船監(jiān)理員間配合默契程度以及他們對工作地點(diǎn)的偏好。

假設(shè)在一個(gè)調(diào)度周期內(nèi)共有n位造船監(jiān)理員，掌握μ類專業(yè)，共含有m個(gè)廠區(qū)。記E={1，2，…，n}表示造船監(jiān)理員集合。F={1，2，…，m}表示該船舶建造公司擁有的廠區(qū)的集合。njk表示第j號廠區(qū)對掌握第k號專業(yè)造船監(jiān)理員的需求數(shù)量。T是一個(gè)n×m的矩陣，tij代表第i號造船監(jiān)理員前往第j號工廠所耗差旅費(fèi)；O是表示造船監(jiān)理員所屬專業(yè)的矩陣，oij=1表示造船監(jiān)理員i掌握第j號專業(yè)，否則等于0。調(diào)度決定變量xij定義為：

基于以上的記號，建立造船監(jiān)理公司監(jiān)理員調(diào)度問題的ILP模型如下：

在組合優(yōu)化問題中，采用罰函數(shù)和獎勵函數(shù)是一種可行且非常流行的方法。這種方法的思想是將有約束的優(yōu)化問題通過在目標(biāo)函數(shù)中引入罰函數(shù)或者獎勵函數(shù)來對破壞約束的情形進(jìn)行懲罰或者對滿足約束的情形進(jìn)行獎勵，從而將原目標(biāo)問題轉(zhuǎn)化成沒有約束的組合優(yōu)化問題。轉(zhuǎn)化后的目標(biāo)函數(shù)格式一般為：

其中λ是與懲罰函數(shù)或獎勵函數(shù)相關(guān)的系數(shù)，φ(gπ(X))用來評判破壞約束或者滿足約束的程度。因此，對于本文要研究的問題中的硬性約束，可以使用獎勵函數(shù)解決。

即要研究的只考慮硬性約束時(shí)的目標(biāo)函數(shù)。由于每名監(jiān)理工將作為特定單一專業(yè)工種的單位進(jìn)行調(diào)度以滿足實(shí)際需求，所以在求解本目標(biāo)函數(shù)過程中對于掌握多種專業(yè)技能的監(jiān)理員會自動淘汰其不大滿足調(diào)度需求的專業(yè)，保留其最佳專業(yè)進(jìn)行調(diào)度。

為了使得調(diào)度人性化，下面將進(jìn)一步考慮監(jiān)理員之間默契程度和監(jiān)理員對工作地點(diǎn)的偏好，建立一個(gè)造船監(jiān)理員調(diào)度問題擴(kuò)展模型。

在日常生活工作中，監(jiān)理員之間的默契程度并非一致。有些監(jiān)理員之間配合默契，工作效率高；相反，有些監(jiān)理員之間關(guān)系不佳，在一起共事可能會造成不必要的損失。監(jiān)理員間配合默契程度是衡量不同監(jiān)理員分配在同一廠區(qū)工作時(shí)相互合作的效率和服務(wù)質(zhì)量的指標(biāo)。相應(yīng)管理人員可以針對實(shí)際情況（例如根據(jù)實(shí)際的利潤和損失等）對某些監(jiān)理員之間的默契關(guān)系進(jìn)行量化，對默契程度特別佳的給定一個(gè)正值，對默契程度尤為不好的給定一個(gè)負(fù)值，而對其他默契程度不突出的設(shè)為0。在極端的情況，監(jiān)理員兩兩之間默契程度都不為0，這時(shí)候監(jiān)理員之間默契程度用一個(gè)n×n的矩陣R表示；對于一般情況，表示造船監(jiān)理員間默契程度的R是一個(gè)稀疏矩陣。從而對于任意調(diào)度方案，都可以對每個(gè)廠區(qū)計(jì)算分配到該廠區(qū)監(jiān)理員之間默契程度的總和，再匯總求和計(jì)算出該調(diào)度方案下默契總值p。

造船監(jiān)理員對工作地點(diǎn)（即廠區(qū)）的偏好是指允許監(jiān)理員根據(jù)自己的身體狀況、家庭狀況、作息習(xí)慣和風(fēng)俗習(xí)慣等多方面因素，自行確定對工作地點(diǎn)（廠區(qū)）的偏好，以供制作調(diào)度方案時(shí)參考。監(jiān)理員對于廠區(qū)的偏好程度也分為正值、0和負(fù)值。表示監(jiān)理員對廠區(qū)的偏好程度的是一個(gè)n×m的矩陣，用L來表示。

監(jiān)理員之間默契程度和他們對工作地點(diǎn)的偏好程度這兩個(gè)約束屬于軟性約束，考慮上述約束將有助于提高他們工作的積極性和質(zhì)量。為了不降低獲得可行解的機(jī)會，它們將被轉(zhuǎn)化到目標(biāo)函數(shù)中：用目標(biāo)函數(shù)式（6）替代式（5）。于是得到一個(gè)擴(kuò)展的造船監(jiān)理員調(diào)度問題模型。

其中l(wèi)ij表示第i名監(jiān)理員對第j個(gè)廠區(qū)的偏好程度；α和β分別為造船監(jiān)理員對工作地點(diǎn)偏好和造船監(jiān)理員間默契程度的權(quán)重系數(shù)，其值由相應(yīng)管理人員根據(jù)實(shí)際情況賦值。

4 基于模擬退火遺傳算法的問題求解

4.1 模擬退火遺傳算法

遺傳算法（Genetic Algorithms）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法[11-12]。遺傳算法廣泛應(yīng)用于傳統(tǒng)搜索方法難以解決的高度復(fù)雜的非線性領(lǐng)域，且在組合優(yōu)化方面展示了良好的優(yōu)越性。因此，將遺傳算法應(yīng)用于本文研究的問題是可行的。

雖然遺傳算法是一種通用的全局優(yōu)化算法，但是遺傳算法局部搜索能力卻較差。而遺傳算法中每一代群體的優(yōu)良度直接影響后代的優(yōu)良度與整個(gè)算法的效率。大量的研究表明遺傳算法性能可以通過結(jié)合局部搜索步驟進(jìn)行改善。這樣的算法通常被稱作“混合算法”[11]。模擬退火算法（Simulated Annealing）是基于Monte Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于固體物理退火過程與組合優(yōu)化之間的相識性，模擬退火算法由某一較高溫度開始，利用具有概率突跳特性的Metropolis抽樣策略在解空間中進(jìn)行隨機(jī)搜索，伴隨溫度不斷下降重復(fù)抽樣過程。固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小，模擬退火算法是一種局部搜索能力很強(qiáng)的算法[13]。將模擬退火的思想引入遺傳算法，對交叉和變異后的個(gè)體實(shí)施Boltzmann接受策略，不但增強(qiáng)了遺傳算法的全局收斂性，并且使遺傳算法在進(jìn)化后期有較強(qiáng)的爬山性能，加快了進(jìn)化后期的收斂速度，形成模擬退火遺傳算法，可以有效緩解遺傳算法的壓力[14-15]。針對本文研究的問題，將遺傳算法與模擬退火算法結(jié)合起來，使用模擬退火遺傳算法，以提升遺傳算法局部搜索能力，從而對性能進(jìn)行改善。

4.2 基于模擬退火遺傳算法的問題求解流程

本文采用實(shí)值編碼方式，個(gè)體長度為待調(diào)度的造船監(jiān)理員人數(shù)，其中個(gè)體中每個(gè)元素的值表示該監(jiān)理員被派往的廠區(qū)。這樣的編碼方式可以自動滿足約束式（2）。

本文研究的問題一個(gè)主要方面是差旅費(fèi)開銷。根據(jù)實(shí)際情況，在一次調(diào)度前可以知道上一個(gè)調(diào)度周期所有待調(diào)度監(jiān)理員所處的廠區(qū)和此次調(diào)度周期廠區(qū)對監(jiān)理員相應(yīng)需求情況。根據(jù)這些數(shù)據(jù)，用計(jì)算機(jī)可以快速計(jì)算出哪些廠區(qū)對哪些專業(yè)監(jiān)理員需求人數(shù)超出已有人數(shù)（即本次調(diào)度前已在此廠區(qū)的相關(guān)監(jiān)理員人數(shù)），而這些廠區(qū)的相應(yīng)監(jiān)理員是無需調(diào)度到其他廠區(qū)的。這樣在不考慮軟性約束時(shí)事先確定哪些造船監(jiān)理員不必要調(diào)度到其他廠區(qū)，從而能生成讓這些監(jiān)理員原地待命的初始群體。同時(shí)為保證初始群體的多樣性，隨機(jī)生成其他監(jiān)理員所派往的廠區(qū)編號。并且為更好地考慮到軟性約束，隨機(jī)選取任意“原地待命”的監(jiān)理員，隨機(jī)生成他們所派往的廠區(qū)。這樣啟發(fā)式生成初始種群的優(yōu)勢是能生成性能較好的個(gè)體，提高算法的進(jìn)化速率。雖然啟發(fā)式生成初始種群可能會增大運(yùn)行開銷，但是實(shí)驗(yàn)表明，這部分開銷在研究的問題整體規(guī)模中是極小的且可接受的。

一般來說，遺傳算法中適應(yīng)度計(jì)算最費(fèi)時(shí)間，而且需要不斷產(chǎn)生新一代，每一代又有若干個(gè)體，提高遺傳算法的運(yùn)行速度顯得尤為重要。由于遺傳算法的內(nèi)在并行機(jī)制，并行處理將有效地改善遺傳算法的性能。遷移（migration）是并行遺傳算法引入一個(gè)新的算子并在進(jìn)化過程中使子群體互相交換個(gè)體的過程[14]。本文將使用遷移策略將子群體中最好的個(gè)體發(fā)給其他的子群體，通過遷移可以加快較好個(gè)體在群體中的傳播。算法流程如下：

步驟1輸入監(jiān)理員數(shù)量n、廠區(qū)個(gè)數(shù)m；輸入差旅費(fèi)矩陣T、專業(yè)矩陣O，人際關(guān)系矩陣R及地點(diǎn)偏好矩陣L內(nèi)元素的值。

步驟2啟發(fā)式方法生成初始群體；輸入遺傳算法配置參數(shù)；設(shè)定初始溫度tmax終止溫度tmin，溫度下降率ν，t=tmax以及局部搜索參數(shù)w等運(yùn)行參數(shù)。

步驟3采用遺傳算法對種群進(jìn)行交叉、變異、非線性排序和選擇。

步驟4對于種群中的每個(gè)個(gè)體調(diào)用模擬退火算法。

步驟5更新溫度if(t＞tmin)thent=t*ν；否則算法結(jié)束，輸出調(diào)度結(jié)果。

步驟6轉(zhuǎn)到步驟3。

5 實(shí)驗(yàn)結(jié)果及分析

仿真環(huán)境的運(yùn)行平臺為Matlab，在Core i5 2.3 GHz的CPU和4 GB RAM的PC上運(yùn)行。為了方便說明和驗(yàn)證，選用一組規(guī)模較小并且典型的數(shù)據(jù)進(jìn)行測試。假設(shè)共有15名造船監(jiān)理員，掌握5個(gè)不同的專業(yè)，其中一位監(jiān)理員同時(shí)掌握兩個(gè)專業(yè)；共有5個(gè)廠區(qū)。設(shè)定在調(diào)度前15名監(jiān)理員平均分配到5個(gè)廠區(qū)。根據(jù)現(xiàn)實(shí)中機(jī)票價(jià)格，設(shè)定表示15名監(jiān)理員的差旅費(fèi)矩陣T為：

表示監(jiān)理員之間默契程度的矩陣R為15×15的矩陣，令r1，15=-1，其他元素都為0；表示15名監(jiān)理員地點(diǎn)偏好的矩陣L為15×5的矩陣，其中l(wèi)10，4=l11，4=1，l12，1=-1，其他元素值為0；表示監(jiān)理員掌握專業(yè)的矩陣O為：

本文使用的算法運(yùn)行參數(shù)如表2和表3。

表2 求解過程中基本遺傳算法使用的參數(shù)

表3 求解過程中有關(guān)子種群和遷移使用的參數(shù)

從算法描述中可以看出，算法外循環(huán)執(zhí)行次數(shù)與tmax，tmin和ν有直接聯(lián)系。一般來說，tmax要取得足夠大，使得能夠接受劣解的概率比較大，在初始時(shí)能幾乎100%的概率接受劣解。但由于本次實(shí)驗(yàn)數(shù)據(jù)規(guī)模較小，經(jīng)過多次實(shí)驗(yàn)，最后采用的有關(guān)模擬退火參數(shù)如表4。

表4 求解過程中有關(guān)模擬退火相關(guān)參數(shù)

表5 仿真實(shí)驗(yàn)調(diào)度結(jié)果

從以上的參數(shù)和實(shí)驗(yàn)數(shù)據(jù)描述可以看出，第14名監(jiān)理員同時(shí)掌握第4和第5號專業(yè)；而所有廠區(qū)對第5號專業(yè)監(jiān)理員的需求是2，對第3和第4號專業(yè)的需求為4，對其他專業(yè)需求人數(shù)都為3；第1號表示不愿與第15號監(jiān)理員共事；第10號監(jiān)理員和第11號監(jiān)理員更偏好第4號廠區(qū)，而第12號監(jiān)理員不愿去第1號廠區(qū)。在接下來的仿真實(shí)驗(yàn)中將著重考察這些要求是否滿足。

運(yùn)行20次，平均耗時(shí)為3.57 s。圖1給出了隨機(jī)某次實(shí)驗(yàn)過程中最優(yōu)解的變化，可以看出在較少的迭代次數(shù)內(nèi)就可以獲得較理想最優(yōu)解。注意圖中最優(yōu)解的值只是本模型和算法得出的用于量化的值，并非真實(shí)費(fèi)用開銷。

圖1 實(shí)驗(yàn)過程中最優(yōu)目標(biāo)函數(shù)解的變化

隨機(jī)選取5次運(yùn)行結(jié)果，實(shí)驗(yàn)結(jié)果（即調(diào)度結(jié)果）如表5所示。

從以上實(shí)驗(yàn)結(jié)果可以看出，對于硬性約束要求，調(diào)度結(jié)果都很好滿足了廠區(qū)對各專業(yè)監(jiān)理員人數(shù)的需求且沒有出現(xiàn)“應(yīng)留守卻被調(diào)離”等這樣的無意義調(diào)度；同時(shí)總差旅費(fèi)是最少的，例如對于第6號監(jiān)理員，如若人工調(diào)度可能憑感覺做出將第6號監(jiān)理員繼續(xù)留在第2號廠區(qū)的決定，但仿真實(shí)驗(yàn)結(jié)果表明，第6號監(jiān)理員調(diào)度至第3號廠區(qū)并將第2號和第9號監(jiān)理員分別調(diào)度至第2號和第4號廠區(qū)更加節(jié)省調(diào)度開銷。除表5中第二個(gè)調(diào)度結(jié)果對第1號監(jiān)理員與第15號監(jiān)理員默契程度沒有考慮周到外，其余調(diào)度結(jié)果都較好滿足了有關(guān)人性化的軟性約束要求，體現(xiàn)了調(diào)度人性化，如第10號至第12號監(jiān)理員對特定廠區(qū)的偏好等要求都被充分滿足。最優(yōu)實(shí)驗(yàn)解和最差實(shí)驗(yàn)結(jié)果相比偏差約為0.635%，算法有較好的穩(wěn)定性。

為驗(yàn)證系統(tǒng)的實(shí)用性，繼續(xù)根據(jù)某監(jiān)理公司實(shí)際情況進(jìn)行仿真實(shí)驗(yàn)，每次調(diào)度的監(jiān)理員人數(shù)達(dá)到百人。實(shí)驗(yàn)參數(shù)和變量因問題規(guī)模的增大而相應(yīng)變大。實(shí)驗(yàn)取得理想結(jié)果。

6 結(jié)束語

本文是對我國造船監(jiān)理公司監(jiān)理人員調(diào)度問題的一個(gè)初步研究，旨在探討一種系統(tǒng)解決針對實(shí)際造船監(jiān)理公司監(jiān)理人員調(diào)度問題的思路與方法。根據(jù)我國船舶建造監(jiān)理的實(shí)際情況，歸納出一系列硬性約束和軟性約束，并建立了一個(gè)較通用的造船監(jiān)理人員調(diào)度的數(shù)學(xué)模型。同時(shí)所建立模型有較好的可塑性和可擴(kuò)展性，不同的船舶建造監(jiān)理公司可以依據(jù)實(shí)際情況將自身的獨(dú)特要求以軟硬約束的形式融入模型中。

在數(shù)學(xué)模型的基礎(chǔ)上，宏觀采用遺傳算法對該問題求解，通過啟發(fā)式生成種群和引入遷移策略改進(jìn)算法效率，并引入模擬退火算法改進(jìn)遺傳算法的局部搜索能力。仿真實(shí)驗(yàn)驗(yàn)證了模型有效且算法有較好的執(zhí)行效率和魯棒性，具有一定的實(shí)用價(jià)值和經(jīng)濟(jì)效益。在未來的研究中，將進(jìn)一步改善模型和算法。

[1]張瑩.淺談船舶監(jiān)造的管理方法[J].中國水運(yùn)，2010，10（8）：10-11.

[2]李海平.船舶建造工程的監(jiān)理工作[J].中國水運(yùn)：學(xué)術(shù)版，2010，6（2）：42-44.

[3]Sabar M，Montreuil B，F(xiàn)rayret J M.A multi-agent-based approach for personnel scheduling in assembly centers[J]. Engineering Applications of Artificial Intelligence，2009，22（7）：1080-1088.

[4]Sabar M，Montreuil B，F(xiàn)rayret J M.An agent-based algorithm for personnel shift-scheduling and rescheduling in flexible assembly lines[J].Journal of Intelligent Manufacturing，2012，23（6）：2623-2634.

[5]Kabak O，Ulengin F，Aktas E，et al.Efficient shift scheduling in the retail sector through two-stage optimization[J]. European Journal of Operational Research，2008，184（1）：76-90.

[6]Bai Ruibin，Burke E K，Kendall G，et al.A hybrid evolutionary approach to the nurse rostering problem[J].IEEE Transactions on Evolutionary Computation，2010，14（4）：580-590.

[7]Lu Zhipeng，Hao Jinkao.Adaptive neighborhood search for nurse rostering[J].European Journal of Operational Research，2012，218（3）：865-876.

[8]任守綱，徐煥良，李相全.基于遺傳算法的軟件項(xiàng)目人力資源調(diào)度研究[J].計(jì)算機(jī)應(yīng)用研究，2008，25（12）：3563-3567.

[9]沈吟東，陳名暉，鄧婕.利用矩陣向量化變換求解護(hù)士排班問題[C]//中國控制與決策會議論文集，2008：1019-1022.

[10]沈吟東，蘇光輝.帶約束的護(hù)士排班模型和基于變換規(guī)則的優(yōu)化算法[J].計(jì)算機(jī)工程與科學(xué)，2010，32（7）：99-103.

[11]Krasnogor N，Smith J E.A tutorial for competent mimetic algorithms：model，taxonomy and design issues[J].IEEE Trans on Evol Comput，2005，9（5）：474-488.

[12]葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2008，25（10）：2911-2916.

[13]曹云健，董晶.基于模擬退火遺傳算法的服務(wù)選擇[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（10）：3507-3510.

[14]Potts J C.The development and evaluation of an improved genetic algorithm based on migration and artificial selection[J].IEEE Trans on SMC，1994，24（1）：73-86.

[15]王銀年，葛洪偉.求解TSP問題的改進(jìn)模擬退火遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（5）：44-47.

FU Hao,GE Hongwei,SHAO Changlu,ZHU Liang

School of Internet of Things Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China

Quickly and effectively scheduling members of shipbuilding supervision of different majors to specific shipyards improves the efficiency of shipbuilding and ensures the constructional quality.Because lack of general models and effective scheduling means for above-mentioned issue in China,this paper establishes mathematical models with a series of hard constraints and soft constraints to solve this problem.Followed by the models,a hybrid genetic algorithm based on simulated-annealing genetic algorithm is applied to solving this problem.Simulated experiments verify that the model and the algorithm are feasible and effective.

scheduling shipbuilding inspectors;construction of ships;personnel scheduling;hybrid genetic algorithm;NPproblem

A

TP302.1

10.3778/j.issn.1002-8331.1212-0055

FU Hao,GE Hongwei,SHAO Changlu,et al.Models and hybrid genetic algorithm for scheduling shipbuilding inspectors.Computer Engineering and Applications,2014,50（21）：238-242.

符昊（1991—），男，本科，主要研究方向?yàn)槿斯ぶ悄?；葛洪偉?967—），男，博士，教授/博士生導(dǎo)師，主要研究方向?yàn)槟Ｊ阶R別、人工智能和算法分析；邵長魯（1988—），男，碩士研究生，主要研究方向?yàn)橄到y(tǒng)開發(fā)、資源調(diào)度；朱亮（1991—），男，本科。E-mail：haofu@ucdavis.edu

2012-12-05

2013-03-19

1002-8331（2014）21-0238-05

CNKI出版日期：2013-03-29，http://www.cnki.net/kcms/detail/11.2127.TP.20130329.1540.014.html