資源優(yōu)化調度問(wèn)題研究

2011年第31期科技冒向導<>高教論述<資源優(yōu)化調度問(wèn)題研究胡3(空軍勤務(wù)學(xué)院后勤指揮系江蘇徐州21000)[摘要]資源優(yōu)化調度問(wèn)題是 一個(gè)廣泛存在的復雜系統問(wèn)題.以物流配遞和排課問(wèn)題等的一奧資源優(yōu)化調度的典型問(wèn)題,由其難解性引起了較為廣泛的關(guān)注。本文以排課問(wèn)題為例,提出了基于不等式方法的多目標遺傳算法解決方案,對排課問(wèn)題的研究具有重要的現實(shí)意義。[關(guān)鍵詞]資源優(yōu)化調度問(wèn)題;排課問(wèn)題1.資源優(yōu)化調度問(wèn)題概述不等式特征。由于排課問(wèn)題存在目標和約束的復雜性。相對于一般多資源優(yōu)化調度問(wèn)題是工程領(lǐng)域的一個(gè)普遍問(wèn)題,在T程實(shí)踐中，目標問(wèn)題， 排課問(wèn)題在處理約束函數時(shí)表現為更復雜的關(guān)聯(lián)約束關(guān)資源的優(yōu)化調度關(guān)系到整體的效率和效益.具有很高的研究和應用價(jià)系 ,進(jìn)一步增加了排課問(wèn)題的復朵度。因此,把排課問(wèn)題作為這類(lèi)資源值。資源優(yōu)化調度般涉及的變量較多,屬于帶約束的多月標優(yōu)化問(wèn)優(yōu)化調度問(wèn)題的典 型例子具有一定的代表性。題,而物流配送等的- 類(lèi)問(wèn)題區別于-般的多目標優(yōu)化問(wèn)題,具有以3.排課問(wèn)題概述排課問(wèn)題是學(xué)校教務(wù)管理中最重要，也是最復雜的問(wèn)題之一。課(1)這類(lèi)資源優(yōu)化調度問(wèn)題是帶約束的多月標優(yōu)化向題并且這程 表編排主要分為兩個(gè)部分, -是根據各專(zhuān)業(yè)、不同年級授課任務(wù)確些約東既包含常規約束，也包含動(dòng)態(tài)約東.常規約束確定解的可行區定各班課程, 二是根據每周的課時(shí)數、課室進(jìn)行課程表的編排.班級的城,動(dòng)態(tài)約束則確定解的折中與妥協(xié)空間。課表由班主任或主管老師根據教學(xué)大綱進(jìn)行編持,這個(gè)過(guò)程通過(guò)手工(2)這類(lèi)資源優(yōu)化調度問(wèn)題在求解過(guò)程中,可行解不- -定是合理操作也可以完成。 教務(wù)管理部( 1的工作人員通過(guò)提前收集各校區,二的,最后尋求的更多是滿(mǎn)意解。如在排課問(wèn)題中,有一門(mén)課是一一周上兩 級學(xué)院系的開(kāi)課情況.然后統- -進(jìn)行處理,確定哪此課是- -定要開(kāi)次的,在解中.兩次課剛好連在-一起,這也是不合理的。的,那些課叮以做機動(dòng)處理.然后統- -安排學(xué)校的開(kāi)課計劃,再按照開(kāi)(3)這類(lèi)資甌優(yōu)化調度問(wèn)題在應用遺傳算法求解的過(guò)程中.其基課計劃進(jìn)行排課。 所以對于第二階段的課程編排，涉及到的變量主要因存在唯.一性,X別于一般的遺傳算法應用問(wèn)題。如貨物配送地點(diǎn)與包括時(shí)間 .教師，班級、課室.課程校區院系.課室類(lèi)型,以及一些其貨物需求量的組合，課程與教師班級的組合,這些都是唯一的。它特殊要求等要求。在課室和教師資源極大充分的條件下.學(xué)校的課(4)這類(lèi)資源優(yōu)化調度問(wèn)題在資源的組合優(yōu)化方而具有一-定的可程安排 叮以交由各院系進(jìn)行，各院系直接統籌本院系的教師和課室資調整空間。因為這類(lèi)問(wèn)題涉及時(shí)間和人員等,所以在資源調度過(guò)界中，源， 進(jìn)行統一調度 就可以完成，這樣，排課的復雜性也就相對降低了?？梢酝ㄟ^(guò)適當地增加或減少少量的時(shí)間或人員方面的資瀕達到資源但是 .大多數情況下,由于學(xué)校招生規模的擴大,課室很多情況下都成的充分和有效利用.從而提高效率和效益。為排課問(wèn)題中的緊缺資源.所以,爭收課室資源的最大利用率就成為2.資源優(yōu)化調動(dòng)問(wèn)題的描述排課問(wèn)題的關(guān)鍵。這種情況下,學(xué)校資源的統安排通常是手I難以多目標優(yōu)化問(wèn)題(MOP)-般采用如下定義:很好地完成，需要協(xié)調各個(gè)內素.實(shí)現資源的優(yōu)化配置。目前,在資源一般MOP由n個(gè)決策變量參數.k個(gè)日標雨數和m個(gè)約束條件組優(yōu)化問(wèn)題 t.本要采用的萬(wàn)法有貪婪算法，規劃論和遺傳算法。成,目標函數約束條件與決策變量滿(mǎn)足-定的關(guān)系。 最優(yōu)化問(wèn)題如下:4.現有排課問(wèn)題的解決方寨Minimize =(=()=()(...(x))在現行高校的排課問(wèn)題上,主要有兩種模式, -種是沿用全校性.(ax(.()+e...(.)-O的統-排課,另.種是分權排課統管理。 各個(gè)學(xué)?？梢愿鶕?shí)際問(wèn)其中，xx,而...x)eX題,采用不同的模式。如果學(xué)校規模比較小，可以考慮仝校性的統一排課方法如果學(xué)校規模比較大,涉及的學(xué)生班級.課程教師等因索比y=0rjx..*y.)eY這里,x表示決策變量,y表示目標向量,X表示決策向量x形成較多,而且有較多的約束條件.則可以考慮采用分權的模式進(jìn)行排課。的決策空間,Y表示日標向量y形成的目標空間.約束條件e∞)≤0確全校性的統一排課 也就是我們前面講到的由學(xué)校統- -管理的院系統一上.報教學(xué)計劃.然后由教務(wù)管理部( ]統-安排教學(xué)任務(wù)和課種。而定決策向量的可行取俏范圍。分權排課模式就是首先對學(xué)校有限的資源進(jìn)行劃分,根據院系的教學(xué)通常多目標優(yōu)化問(wèn)題的日標隔數具有線(xiàn)性或者非線(xiàn)性性質(zhì),優(yōu)化規模分配一定的教學(xué)資源，然后由院系根據所分配的資源安排本院系函數是將決策向量X映射到日標向量y.記作FA- +A的課程,教務(wù)管理部1 ]可以隨時(shí)查看排課情況。并進(jìn)行統一調度。 這樣物流配送 和排課等類(lèi)資源優(yōu)化滿(mǎn)度問(wèn)題作為多目標問(wèn)題,在其 的好處 就是把問(wèn)題化簡(jiǎn),分而治之。特別是對于動(dòng)態(tài)約束條件比較多定義中也包括了日標向量,決策向量和約束條件,這類(lèi)資源優(yōu)化調度的情況，這種排課模式是比較叮取的。在實(shí)際的排課過(guò)程中,這種系統問(wèn)題是在多準則決策中尋求相互沖突的多月標聞的折衷與平衡，敏終雖然能實(shí)現分而治之的效果.但是實(shí)際君來(lái)，大部分學(xué)校采用此系統獲得叫題的滿(mǎn)意解。結合多日標優(yōu)化問(wèn)題的措述,對于由。個(gè)決策變進(jìn)行排課時(shí)，由 于院系規模比較小.動(dòng)態(tài)約束比較多.所以大部分的院量參數、個(gè)目標商數和m個(gè)約束條件組成。目標函數約束條件與決系實(shí)際 上:都是采用人工排課的方法實(shí)現。策變量滿(mǎn)足- -定的 關(guān)系的資源優(yōu)化調度問(wèn)題, -般情況可以用以下的5.小結數學(xué)公式進(jìn)行描述:本文在闡述物流配送，排課等-類(lèi)資源優(yōu)化調度問(wèn)題的特點(diǎn)的基y-中(閑)≥0礎上,結合多日標優(yōu)化問(wèn)題的描述,對這類(lèi)資源優(yōu)化調度問(wèn)題作了-3.C(x)≤0般描述,并把相應的排課問(wèn)題-般描述作 了介紹。在此基礎上對現有中(中比1(:(...0”CGaxEflE.B...... .xeF。排課問(wèn)題的解決方案進(jìn)行綜述,特別是廣東省大部分高校所采用的排山)為目標函數向量C(x)為約束條件,，為決策向量,F為所有資課系統作 了比較詳細的分析.為后面提出基于不等式方法的多目標遺源組合n的集合。相應地,在排課問(wèn)題中,中()即為排課問(wèn)題必須滿(mǎn)足的多個(gè)月標，傳算法的應用提供了現實(shí)依據。G()確定排課問(wèn)題決策間量的叮行范圍,x為決策向量,F為所有課程[參考文獻]n的集合。[1]馬永，基于遺傳算法求解排課問(wèn)題的研究州建電腦2008.排課問(wèn)題是求約束條件C()確定的可行范圍內滿(mǎn)足月標函敷φ [2朝文件中國煤化工系統應用2008.()的排課方案,排課問(wèn)題的描述充分體現了排課問(wèn)題的多日標特性及[3]辛延4出版社,2006.YHCNMHG作者簡(jiǎn)介:胡丑(1986- -), 男,研究生學(xué)員,江蘇省徐州市空軍勤務(wù)學(xué)院研究生管理大隊41隊學(xué)員。32