[發明專利]約束粒度可控的排課方法及系統

在審

• 申請號: 201611220114.2
• 申請日: 2016-12-26
• 公開（公告）號: CN106846193A
• 公開（公告）日: 2017-06-13
• 發明（設計）人: 楊衛東;高澤民;王珂;陳文;秦鵬;王亞飛;徐振強;肖樂;徐溢凡
• 申請（專利權）人: 河南工業大學
• 主分類號: G06Q50/20
• 分類號: G06Q50/20
• 代理公司: 鄭州睿信知識產權代理有限公司41119
• 代理人: 崔旭東

1.約束粒度可控的排課方法，其特征在于，該方法包括以下步驟：

1)計算課元組的空閑時間，當空閑時間的空余周課時大于課元組的周課時，查找最優的排課時間；

2)在最優排課時間BT內計算最合適的排課教室，若存在最合適的排課教室，則課元組排課成功；

3)否則，對課元組進行沖突處理，若沖突處理成功，則課元組排課成功，否則，將該課元組排課失敗；

4)當所有課元組排課完成后，對排課失敗課元組，調整約束粒度返回步驟1)重新排課或進行手動調整。

2.根據權利要求1所述約束粒度可控的排課方法，其特征在于，所述最優排課時間的計算方法包括以下步驟：

A)計算課元組的上課性質CP、周課時CT及一周內的排課次數N；

B)在全局設置中查找符合屬性(CP,CT,N)的課元組最優排課時間序列BT′＝[(D1,H1),(D2,H2),…,(DN,HN)]，(D1，D2，…，DN)為一周內上課天數的最優序列，(H1,H2,…,HN)為一天內上課節數的最優序列；

C)若時間片(D1,H1)包含在空閑時間內，計算在該時間片下，上課教師和上課班級的時間均勻分布程度，當時間均勻分布程度高于預設值，則獲得最優排課時間BT＝(D1,H1)，查找結束；若時間片(D1,H1)不在空閑時間內或時間均勻程度低于預設值，判斷下一個時間片是否為最優排課時間。

3.根據權利要求1所述約束粒度可控的排課方法，其特征在于，所述最合適的排課教室的計算方法包括以下步驟：

a)計算課元組的上課校區CA、上課教室類型CL及上課教室大小CS；

b)查找符合課元組屬性(CA,CL,CS)的教室列表，從教室列表中選取優先級最高的教室，計算該教室在課元組的上課起始周內的空閑時間表，當空閑時間表與最優排課時間邏輯與后等于最優排課時間，則該教室為最合理的上課教室，否則，判斷下一個教室是否為最合理的上課教室。

4.根據權利要求1所述約束粒度可控的排課方法，其特征在于，步驟3)中對課元組進行沖突處理的方法包括以下步驟：

Ⅰ)將需要沖突處理的課元組壓入堆棧，并查找該課元組的相關課元組，將相關課元組按優先級從低到高加入到隊列Queue，并記錄需要沖突處理的課元組為相關課元組的父課元組；

Ⅱ)取隊列Queue中的首課元組，將其進行重新排課，排課成功，對其父課元組進行重排，排課成功，則沖突處理成功；否則，將首課元組的相關課元組加入隊列Queue，將首課元彈出隊列并壓入堆棧；

Ш)重復步驟Ⅱ)，當父課元組出棧且重排成功，則沖突處理成功。

5.根據權利要求1所述約束粒度可控的排課方法，其特征在于，所述初始輸入數據包括全局設置、班級信息、教室信息、教師信息、課元組信息、課程信息、教室約束、教師約束和課元組約束。

6.約束粒度可控的排課系統，其特征在于，該系統包括自動排課單元及調整單元，所述自動排課單元包括最優排課時間計算模塊、最合適排課教室計算模塊、沖突處理模塊；所述調整單元包括重新調整約束粒度模塊或手動調整模塊；

所述自動排課單元用于按優先級高低對課元組排序，根據初始輸入數據，從優先級最高的課元組開始依次進行排課；

所述最優排課時間計算模塊用于計算課元組的空閑時間，當空閑時間的空余周課時大于課元組的周課時，查找最優的排課時間；

所述最合適排課教室計算模塊用于在最優的排課時間BT內計算最合適的排課教室；

所述沖突處理模塊用于對課元組進行沖突處理。

7.根據權利要求6所述約束粒度可控的排課系統，其特征在于，所述最優排課時間計算模塊的計算方法包括以下步驟：

A)計算課元組的上課性質CP、周課時CT及一周內的排課次數N；

B)在全局設置中查找符合屬性(CP,CT,N)的課元組最優排課時間序列BT′＝[(D1,H1),(D2,H2),…,(DN,HN)]，(D1，D2，…，DN)為一周內上課天數的最優序列，(H1,H2,…,HN)為一天內上課節數的最優序列；

C)若時間片(D1,H1)包含在空閑時間內，計算在該時間片下，上課教師和上課班級的時間均勻分布程度，當時間均勻分布程度高于預設值，則獲得最優排課時間BT＝(D1,H1)，查找結束；若時間片(D1,H1)不在空閑時間內或時間均勻程度低于預設值，判斷下一個時間片是否為最優排課時間。