基於圖著色的事務調度算法的製作方法
2023-10-11 04:40:09 1
專利名稱：基於圖著色的事務調度算法的製作方法
技術領域：
本發明涉及圖論中的圖著色領域，是一種基於圖著色的事務調度算法。
背景技術：
在實際生活中存在著在時間上或者處理程序上具有衝突的一系列事務，如何合理安排這些事務，形成事務時間表，是活動中常見的困難工作。在每一個時段內，事務時間表的安排既受到不同事務參與者可得性的限制，也受到事務執行場地可得性的限制。圖論為事務時間表問題提供了描述工具，來解決事務時間表安排問題。在現實生活中使用圖論、邊著色等方式解決相關事務處理的算法思想比較廣泛，例如在計算機網絡文件傳輸中，每臺計算機X有一個有限的數f(X)的溝通埠。對於每一個對電腦有大量的文件而被轉移計算機之間的配對的情況下，如何安排的文件轉移，以儘量減少對整體轉讓過程的總時間。另外，大學排課系統的優化問題、考試的考場的安排問題、商務會議時間的安排問題等等都可以在規定了某些特定條件後歸結成為使用圖論、著色問題來進行處理， 以達到最佳的事務安排的結果。
發明內容
本發明的目的在於提出了基於圖論的事務調度算法，通過使用對圖中衝突節點著色得到解決衝突事務的調度方案。此算法能自動、快捷地排定優化的事務時間表，極大地方便企事業單位的活動安排。本發明為了解決其技術問題所採用了如下技術方案1.建立模型通過問題轉換將處理的事務與圖中的頂點和邊按照一定的約定對應起來，以此建立基本的事務處理模型，具體說明如下(1)形成事務集給定事務集預定要完成的任務，給定構成事務的元素集合分別 % A1, A2, ...，An。事務集合T是T1, T2，…，Tn的笛卡爾積為=T1XT2X…XTn = Kt1, t2，…， tn) Iti e Ti, i = 1,2,…，η}。事務集合T (T1, T2,…，Tn)，其中的一個事務為V，V e T表示V是集合T的一個η 元組。V[Ti]則表示元組V中相應於屬性Ai的一個分量。每個事務是笛卡爾集的一個η元組，即是從構成事務的元素集合的笛卡兒集中選取元素，形成事務。多個事務的集合可以完成預定的任務，因而對於一項需完成的任務則轉化得到一個滿足預定任務的事務集Τ。(2)將事務設定為圖中的頂點，即一個頂點表示一個事務集中的事務。將任一對安排在同一時間段中有衝突的頂點作一條無向邊，而在同一時間段內沒有衝突的頂點不連接。將完成預定任務的事務集轉化為一張無向圖。設無向圖G = ，V = Iv1J2, -,vn i = 1,2, -,η},E = {ei;e2, -,eji=1,2,…，η}，邊 ei = (Vi, Vj) e E, Vi> Vj e V。其中每個頂點vi對應(1)中的事務V，V e T，表示V是集合T的一個η元組。V」 Vj是事務集中具有衝突的事務。按照對圖中節點和邊的定義，事務集以及事務集之間的關係如說明書附圖1所示。在同一時間段有無衝突作為定義邊的依據，將事務以及關係轉換成圖。(3)對於事務的處理在確定了基本的圖的表示以後，使用對節點進行著色的方式來安排有衝突事務的處理，那麼著色節點集合說明如下設無向圖G =〈V，E>，C = Ici = VjI Vj e V, 1 ^ i ^ m, 1 ^ j ^ η}其中Vi表示圖中節點，即事務集中的一個事務。對於著色節點集中的著色點的數量的上限值m是事務所需用資源S的個數和。2.圖著色的過程圖著色的主要思想是按照圖中邊的設定關係，將出現衝突的節點使用不同的顏色標記出來。設定預計給節點著色的總數目，使用不同顏色進行標記，即對於出現衝突的節點，每一個點對應一種不同的顏色。以顏色代表衝突節點。為建立的事務模型得到的無向圖進行著色。(1)對每個頂點著色，著色的要求是每一頂點都著相同一種顏色。由於頂點代表的是事務集中的具體事務，初始時不考慮邊，即不考慮衝突情況，將顏色統一。(2)針對衝突情況考慮邊，任意一對有邊連接的頂點改著不同顏色。選從哪些邊優先開始對頂點處理很重要，從實際角度來看，事務的安排，對於出現衝突的情況應該按照重要程度進行處理，因為越往後越難處理，如果再與其他必要條件衝突，就有可能無法安排。統計圖中邊的數量m，以及統計每個節點的度數，首先針對度數較大的節點開始考慮。其次引入權的思想，從帶權圖來看，權重高的邊對應的頂點應該儘早著色；如果權相同，則可根據邊所連接的頂點未處理情況排序。因此，選擇正確的邊即衝突情況優先處理可以提高算法成功率。在帶權圖中，將邊按權大小降序排列即按照衝突的情況的重要程度進行排序Eff = Iei I ei e E，1彡i彡m}(帶權位排序的邊的集合)(3)實現能滿足預定任務的特殊著色要求。得到可行的著色方案，每一個可行的著色方案對應對事務集的一個可行的安排方案。3.事務調度算法的詳細步驟設無向圖G = ，V = Iv1J2, ...，vn}，E = {ei，e2，…，ej，λ (Vi) = c 表示給頂點著色為c，具體的算法如下(1)令c = 1，對圖中所有的頂點著色c，即λ (Vi) = 1(1 ^ i ^n)；(2)令i = 1，統計圖中邊的總數為m，在邊信息中引入q，記錄權位數據並將邊集按照q的降序進行排列；統計圖中各個節點的度，按照圖G中的各節點度數的降序對節點進行排列，假設個數為k(l < k < η)；(3)取ei e Ε，比較與ei連接兩個頂點取度數較低的頂點著色即c的值自增1，並將頂點進入著色頂點集合N(Vi)；(4) i的值自增1，若i < m，則轉移到(3)；(5)著色完成，根據著色方案得到事務集的一個安排方案。
由現實的事務時間安排問題等價轉化得到的圖著色問題除了要求有邊連接的頂點必須著色不同外，還有其他的硬性要求。這些要求主要是在實際問題中提出的事務與事務所佔資源的之間的問題。事務調度算法必須將這些約定考慮到處理中，這樣所得的事務調度方案才合理，具有實際推廣意義。
圖1示出了事務及關係的轉換。圖2示出了事務調度算法的流程。
具體實施例方式選取考試考場安排問題為例，將考試考場安排轉化的圖著色問題。對於監考，每個事務都由(教師，班級)二元組構成，所使用的資源就是考場即教室。由於同一時間段內可得教室的數量是有限的，那麼對應的可著色的顏色數量的上限是確定的。若著同一顏色的監考單元的數量超過此顏色代表的時間段可得教室的總數，就意味著部分監考單元在這個時間段內找不到教室可用，這個要求是硬性的，在調度中必須考慮。解決這些額外的要求可以通過衝突解決規定來調節衝突實現算法的可行性和合理性。也就是說，對於額外的硬性要求，在算法中設置相應的參數進行體現，或者作為判別是否著色的條件，使算法更符合實際需求。對於監考安排，每個頂點即事務都由(教師，班級)二元組構成，所使用的資源就是考場即教室。那麼同一時間段內可得教室的數量是有限的，那麼對應的可著色的顏色數量的上限是確定的。(1)令c = 1，對圖中所有的頂點(教師，班級)二元組進行著色C，即λ (Vi)= 1(1 ^ i ^ η)；( 令i = 1，按照(教師、班級)二元組與教室之間的衝突連接生成邊，統計圖中教室衝突的總數為m，在邊信息中引入q，記錄權位數據並將邊集按照q的序進行排列； 統計圖中各個節點的度，按照圖G中的各節點度數的降序對節點進行排列，假設個數為 k(l ^ k^ η)；(3)取ei e Ε，比較與ei連接兩個頂點取度數較低的頂點(即教室資源衝突較少的)著色即C的值自增1，並將頂點進入已經著色頂點集合N(Vi),表示已經安排好(教師、 班級)二元組的監考教室；(4) c的值自增1，若i < m，則轉移到(3)；(5)著色完成，根據完成著色的顏色數值c與教室資源的數量比較，若合理則根據著色方案得到事務集的一個安排方案；否則此著色方案重新調整。
權利要求
1.一種基於圖著色的事務調度算法，其特徵在於按照圖中邊的設定關係，將出現衝突的節點使用不同的顏色標記出來；設定預計給節點著色的總數目，使用不同顏色進行標記，即對於出現衝突的節點，每一個點對應一種不同的顏色；以顏色代表衝突節點；為建立的事務模型得到的無向圖進行著色。本發明的有益效果是提出了基於圖論的事務調度算法，通過使用對圖中衝突節點著色得到解決衝突事務的調度方案；此算法能自動、快捷地排定優化的事務時間表，極大地方便企事業單位的活動安排。
2.一種基於圖著色的事務調度算法，其特徵在於該基於圖著色的事務調度算法的具體步驟如下無向圖G = ，頂點(即事務)V= {Vi，v2，…，Vn}，邊(即衝突)E= Ie1, e2，…， en}，λ (Vi) = c表示給頂點著色為c，具體的算法如下(1)令c= 1，對圖中所有的頂點著色c，即λ (Vi) = 1(1 ^ i ^n)；(2)令i= 1，統計圖中邊的總數為m，在邊信息中引入q，記錄權位數據並將邊集按照 q的降序進行排列；統計圖中各個節點的度，按照圖G中的各節點度數的降序對節點進行排列，假設個數為k(l彡k彡η)；(3)取eie Ε，比較與ei連接兩個頂點取度數較低的頂點著色即c的值自增1，並將頂點進入著色頂點集合N(Vi)；(4)i的值自增1，若i彡m，則轉移到(3)；(5)著色完成，根據著色方案得到事務集的一個安排方案。
全文摘要
本發明公開了一種基於圖著色的事務調度算法，其特徵在於按照圖中邊的設定關係，將出現衝突的節點使用不同的顏色標記出來；設定預計給節點著色的總數目，使用不同顏色進行標記，即對於出現衝突的節點，每一個點對應一種不同的顏色；以顏色代表衝突節點；為建立的事務模型得到的無向圖進行著色。本發明的有益效果是提出了基於圖論的事務調度算法，通過使用對圖中衝突節點著色得到解決衝突事務的調度方案；此算法能自動、快捷地排定優化的事務時間表，極大地方便企事業單位的活動安排。
文檔編號G06Q10/06GK102426677SQ20111021631
公開日2012年4月25日 申請日期2011年7月29日 優先權日2011年7月29日
發明者劉智珺, 彭雲 申請人:武漢生物工程學院科技處