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