王芳芳，包振強(qiáng)，丁泉?jiǎng)?，?成，張惠秋

（揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇 揚(yáng)州 225127）

在生產(chǎn)過程中，由于生產(chǎn)資源、生產(chǎn)時(shí)間、技術(shù)等多種因素的限制，生產(chǎn)部門接到的生產(chǎn)任務(wù)有時(shí)不可能全部完成，須要將生產(chǎn)任務(wù)的一部分外包給供應(yīng)鏈上的其他協(xié)作伙伴，于是產(chǎn)生了協(xié)作計(jì)劃.目前，對(duì)協(xié)作計(jì)劃優(yōu)化問題的研究雖有很大進(jìn)展，但多數(shù)協(xié)作計(jì)劃模型中協(xié)作資源的開工時(shí)間被視為確定的值，并且任務(wù)不可分.［1］事實(shí)上，在實(shí)際應(yīng)用中存在著許多不確定因素，協(xié)作資源在任務(wù)請(qǐng)求的計(jì)劃周期內(nèi)給出的開工時(shí)間往往不是一個(gè)確定時(shí)間，而是提供一個(gè)時(shí)間窗口［2］；而且在實(shí)際協(xié)作生產(chǎn)中，有一部分任務(wù)是可以任意拆分的，而另外的部分任務(wù)卻是有條件拆分的［3］.為此，本文針對(duì)上述問題，提出基于時(shí)間窗口的任務(wù)可拆分協(xié)作計(jì)劃模型，采用合同網(wǎng)的協(xié)作機(jī)制［4］，解決時(shí)間窗口約束下任務(wù)可拆分的協(xié)作計(jì)劃問題，以降低協(xié)作成本；另外，結(jié)合粒子群算法［5］在求解連續(xù)性最優(yōu)化問題方面的優(yōu)勢和遺傳算法的選擇、變異機(jī)制，設(shè)計(jì)了求解該模型的進(jìn)化算法.

1 協(xié)作計(jì)劃模型

協(xié)作計(jì)劃問題可進(jìn)行如下描述：在由多個(gè)有時(shí)序關(guān)系的任務(wù)構(gòu)成項(xiàng)目中，每個(gè)任務(wù)可由一個(gè)執(zhí)行部門或多個(gè)執(zhí)行部門合作完成，每個(gè)部門以已知執(zhí)行時(shí)間區(qū)域及給定的資源需求為特征，當(dāng)本部門所能支配的資源不足以完成當(dāng)前的計(jì)劃任務(wù)集時(shí)，如何選擇各任務(wù)的完成模式以及安排各活動(dòng)的開始時(shí)間，使得活動(dòng)網(wǎng)絡(luò)的時(shí)間資源消耗最少和總成本最低.對(duì)協(xié)作計(jì)劃模型作如下簡化假設(shè)：協(xié)作任務(wù)不容許轉(zhuǎn)包；協(xié)作者對(duì)協(xié)作任務(wù)的報(bào)價(jià)與任務(wù)招投標(biāo)順序無關(guān)；假設(shè)資源需求在任務(wù)使用范圍內(nèi)為均勻分布模式以及單位時(shí)間內(nèi)任務(wù)對(duì)資源的需求為常數(shù)；系統(tǒng)有足夠多的協(xié)作資源，異地資源具有相同的效用.

上述問題可表述為下列規(guī)劃模型.

在協(xié)作計(jì)劃系統(tǒng)項(xiàng)目中，假定任務(wù)集為J.設(shè)Qi為任務(wù)ji的生產(chǎn)量；為任務(wù)ji單件產(chǎn)品最低的競標(biāo)價(jià)格；為任務(wù)ji單件產(chǎn)品的計(jì)劃價(jià)格；xi為本部門自己加工任務(wù)ji的百分比；ti為任務(wù)ji的外協(xié)部門執(zhí)行時(shí)間；是本部門執(zhí)行任務(wù)ji的單件成本；是外協(xié)部門m執(zhí)行任務(wù)ji的單件成本.

模型約束條件如下：

4）總工期約束.max｛Fj≤T｝.

在協(xié)作系統(tǒng)項(xiàng)目計(jì)劃中，假定產(chǎn)生競標(biāo)方案的任務(wù)集為J.設(shè)Qi為任務(wù)ji的生產(chǎn)量；為計(jì)劃期內(nèi)能提供的自有資源的加工能力；Ri，j為任務(wù)ji的單件產(chǎn)品對(duì)j類資源的能力需求；為任務(wù)ji生產(chǎn)單件產(chǎn)品最低的競標(biāo)價(jià)格；為任務(wù)ji生產(chǎn)單件產(chǎn)品的計(jì)劃價(jià)格；xi為本部門自己加工任務(wù)ji的百分比；ti為任務(wù)ji的外協(xié)部門執(zhí)行時(shí)間；是任務(wù)ji的外協(xié)部門m 最早執(zhí)行時(shí)間；是任務(wù)ji的外協(xié)部門m最遲執(zhí)行時(shí)間；T表示項(xiàng)目的交貨期；ti是任務(wù)ji本部門的執(zhí)行時(shí)間；是任務(wù)ji本部門的最早執(zhí)行時(shí)間；是任務(wù)ji本部門的最遲執(zhí)行時(shí)間；Fi是任務(wù)ji的結(jié)束時(shí)間是本部門執(zhí)行任務(wù)ji的單件成本；是外協(xié)部門m執(zhí)行任務(wù)ji的單件成本.

2 基于協(xié)作模型的混合粒子群算法

2.1 適應(yīng)度函數(shù)和選擇機(jī)制

協(xié)作計(jì)劃模型中時(shí)間和成本是不同量綱的參數(shù)［6］.為此，將時(shí)間先進(jìn)行無量綱的標(biāo)準(zhǔn)化處理，再根據(jù)對(duì)時(shí)間和成本的要求分別確定其加權(quán)系數(shù).將多目標(biāo)函數(shù)轉(zhuǎn)化成單目標(biāo)函數(shù).無量綱標(biāo)準(zhǔn)化量化的公式如下：

根據(jù)時(shí)間和成本的要求確定權(quán)系數(shù)w＝（w1，w2）利用線性加權(quán)的綜合，

本文選用比例計(jì)算生存概率，即pi＝fi／∑fi，采用輪盤賭［7］進(jìn)行選擇.

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

1）初始化算子.在初始化范圍內(nèi)對(duì)粒子群進(jìn)行隨機(jī)初始化，產(chǎn)生m個(gè)n維向量.向量的維數(shù)n與活動(dòng)網(wǎng)的活動(dòng)個(gè)數(shù)相同；m作為這個(gè)種群的大小，在迭代過程中不變，同時(shí)隨機(jī)地產(chǎn)生初始位置和速度.初始化的粒子盡可能覆蓋整個(gè)解空間［8］.

2）約束條件的處理.本文采用懲罰函數(shù)法，設(shè)置統(tǒng)一的懲罰項(xiàng)常數(shù)H.

3）慣性權(quán)重［9］.一個(gè)由m個(gè)粒子組成的群體在n維搜索空間中以一定的速度飛行，每個(gè)粒子搜索時(shí)，在考慮到自己搜索的歷史最好點(diǎn)和群體內(nèi)其他粒子搜索的歷史最好點(diǎn)的基礎(chǔ)上進(jìn)行位置的變化.粒子的位置和速度根據(jù)下列方程進(jìn)行變換：

式中w是慣性權(quán)重.帶慣性權(quán)重的粒子群算法是基本粒子群算法的擴(kuò)展.

4）選擇操作.本研究中引用輪盤賭方法計(jì)算個(gè)體的選擇概率，產(chǎn)生新種群.采用精英保存策略，當(dāng)種群數(shù)量減少時(shí)，隨機(jī)生成粒子補(bǔ)充種群數(shù)量.

5）變異操作.粒子群算法的收斂速度較快，但容易選入局部最優(yōu)［10］.本文通過變異操作，對(duì)粒子群算法進(jìn)行改進(jìn)，使其具有更好的全局性.設(shè)置最大速度vmax，當(dāng)向量速度v的各維中含有大于或等于1的分量時(shí)，使用如下公式進(jìn)行變異操作：

圖1 計(jì)劃任務(wù)的網(wǎng)絡(luò)圖Fig.1 Active network fig

3 算例仿真

設(shè)項(xiàng)目部共有10項(xiàng)任務(wù)活動(dòng).圖1為計(jì)劃任務(wù)的網(wǎng)絡(luò)圖，其中任務(wù)10不對(duì)外招標(biāo)，與生產(chǎn)任務(wù)相關(guān)的自有資源共5種，它們?cè)谟?jì)劃期內(nèi)的能力數(shù)據(jù)及各任務(wù)對(duì)各種能力的需求（按單位產(chǎn)品計(jì)）列于表1中，各生產(chǎn)任務(wù)的生產(chǎn)量也在表1中列出.

將這10項(xiàng)任務(wù)分別向協(xié)作伙伴招標(biāo).10項(xiàng)任務(wù)中有9項(xiàng)在規(guī)定的時(shí)間內(nèi)產(chǎn)生競標(biāo)方案，J10沒有產(chǎn)生競標(biāo)方案為第i個(gè)任務(wù)的最低競標(biāo)價(jià)，設(shè)置各參數(shù)如表2中所示，招標(biāo)中獲得的數(shù)據(jù)也列于表2中.

表1 計(jì)劃期的任務(wù)數(shù)據(jù)與相關(guān)約束資源Tab.1 Task data and constraint resource in planning period

粒子群算法的運(yùn)行參數(shù)設(shè)定如下：群大小為50，變異概率為0.1，F(xiàn)i，j表示第i項(xiàng)任務(wù)外包給第j個(gè)服務(wù)提供者，終止代數(shù)為1 000，采用WIN－TC編寫程序.算法程序運(yùn)行顯示，隨著群體的進(jìn)化，目標(biāo)函數(shù)以較快的速度收斂，反復(fù)運(yùn)行程序均具有穩(wěn)定的解.

運(yùn)行算法程序，得到不同權(quán)重條件下的最優(yōu)結(jié)果，見表3.

4 結(jié)語

協(xié)作計(jì)劃優(yōu)化是供應(yīng)鏈優(yōu)化的一個(gè)重要組成部分.本文建立了一個(gè)帶時(shí)間窗口的任務(wù)可分的活動(dòng)網(wǎng)絡(luò)協(xié)作計(jì)劃模型.該模型使得企業(yè)在完善內(nèi)部資源優(yōu)化的前提下能夠更加有效地銜接外部資源，協(xié)作計(jì)劃具有更大優(yōu)化空間，供應(yīng)鏈更加靈活.帶時(shí)間窗口的約束解決了任務(wù)的開工和結(jié)束時(shí)間具有不確定性的問題，從而更加符合實(shí)際生產(chǎn)的需求.同時(shí)，本文采用能夠優(yōu)化連續(xù)問題的粒子群算法，結(jié)合遺傳算法的選擇、變異機(jī)制，建立了相應(yīng)的仿真軟件，通過算例進(jìn)行仿真運(yùn)算，證明該模型及其求解算法是可行且有效的.

表2 由招投標(biāo)過程獲得的數(shù)據(jù)Tab.2 The data of inviting and entering bids

表3 不同權(quán)重下的協(xié)作計(jì)劃及指標(biāo)Tab.3 Object and results of cooperation planning in differentweight

［1］SHAO Zhi－fang，ZHANG Tao.Study on hierarchy collaborative planning for TFT－LCD production chain［C］／／The 1st International Conference on Information Science and Engineering.Nanjing：ICISE，2009：3069－3072.

［2］衣楊，李強(qiáng)，容福麗，等.時(shí)間窗口約束資源配置的混合粒子群算法 ［J］.計(jì)算機(jī)研究與發(fā)展，2008，45（增刊）：233－238.

［3］ZHANG Jian－feng，ZHOU Lei，BAO Zhen－qiang，et al.A cooperation－planning model based on bilevel programming decision［J］.Jwuhan Univ Tech，2006，28（s3）：940－945.

［4］LAI H F，HONG J L，JENGw H.Model E－contract update by coloured activity net［C］／／Asia－Pacific Services Computing Conference.Yilan，Taiwan：APSCC，2008：488－493.

［5］黃少榮.粒子群優(yōu)化算法綜述 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（8）：1977－1980.

［6］張雪霞，陳維榮，戴朝華.帶局部搜索的動(dòng)態(tài)多群體自適應(yīng)差分進(jìn)化算法及函數(shù)優(yōu)化 ［J］.電子學(xué)報(bào)，2010，38（8）：1825－1830.

［7］王芳，邱玉輝.一種引入輪盤賭選擇算子的混合粒子群算法 ［J］.西南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，31（3）：93－96.

［8］GUOw Z，GAO F.Solution space atlases，workspace characteristics charts and joint space maps for the design of planar serial manipulators［J］.Mech Mach Theory，2010，45（3）：392－407.

［9］MO Lin，ZHENG Hua.Improved PSO algorithm with adaptive inertia weight and mutation［C］／／World Congress on Computer Science and Information Engineering.Los Angeles，California，USA：CSIE，2009，4：622－625.

［10］RATNAWEERA A，HALGAMUGE S K，WATSON H C.Self－organizing hierarchical particle swarm optimizer with time－varying acceleration coefficients［J］.IEEE Trans Evol Comput，2004，8（3）：240－255.