汪慧玲,譚子健,張韌(. 咸寧職業(yè)技術學院工學院,湖北 咸寧 4700;. 華中師范大學數(shù)學與統(tǒng)計學學院,湖北 武漢 40079;. 武漢華夏理工學院,湖北 武漢 40)

?

基于有條件隨機分配下的時間表優(yōu)化問題
——以學校課表與某風電場工作排班表的制定為例

汪慧玲1,譚子健2,張韌3
(1. 咸寧職業(yè)技術學院工學院,湖北 咸寧 437100;2. 華中師范大學數(shù)學與統(tǒng)計學學院,湖北 武漢 430079;3. 武漢華夏理工學院,湖北 武漢 430223)

時間表的優(yōu)化問題廣泛應用于各種社會生產(chǎn)活動中，但由于具體任務受制于具體的約束條件而難以周全地制定符合約束的工作時間表.本文中著眼于一般化的有條件約束下的隨機分配特征，基于數(shù)學建模及相關軟件的程序模擬，建立符合約束的目標函數(shù)與約束式，進行相關運算，并給出科學可行的執(zhí)行時間表，以保證工作的有效完成.以學校課表安排與工作排班表的制定為例，論述解答有條件隨機分配下的時間表優(yōu)化問題，給出最終可操作工作流程及其效能評價.結論可應用于工程調(diào)度、時間編排、人員分配等方面，廣泛涉及到眾多相關行業(yè)，具有較大的應用價值.關鍵詞：數(shù)學建模；時間表；課表制定；工作表安排；Lingo

在現(xiàn)如今的社會生活中，能夠快速有效地制訂得到可執(zhí)行的符合約束條件的具體安排規(guī)劃，是創(chuàng)造出效益最優(yōu)化的前提.但事實上，由于各項工程事物建立在特定背景的框架下，對于約束條件的把握與針對此背景下的實際規(guī)劃操作就顯得并不容易.筆者基于運籌學理論，針對實際案例的一般性約束情形，試圖分別列出其對應的目標函數(shù)(有些可能無明確目標函數(shù))與約束條件式，通過計算機優(yōu)化模擬運算，得出具體安排的數(shù)學化表達，最終制定出明確的計劃時間表.本文中例舉關于學校課程表的安排與企業(yè)工作表的制定方案規(guī)劃，這兩個問題具有普遍代表性.我們在此僅考慮針對這兩類問題中一般的約束性條件，使得問題具有普適性，對于一般的問題都有一定的啟發(fā)性和有效的借鑒價值.

1 基于有條件隨機分配下的時間表優(yōu)化問題

對于一般性的時間表規(guī)劃問題[1]，我們可以將其歸結于基于如下背景的表述：

目標函數(shù)：一般的無明確目標函數(shù)，或可根據(jù)進一步優(yōu)化目標提出多目標函數(shù)；

約束條件：一般的具有如下約束限制：

1) 時間閾值：在規(guī)定的時間內(nèi)完成既定任務；

2) 對象明確：在既定的可用對象中分配相應任務與執(zhí)行時刻；

3) 沖突避免：針對某一時刻或某一時間段的人員沖突避免；

4) 任務閾值：根據(jù)實際需求，完成全部既定任務或可選性既定目標；

5) 效益約束：對于可能出現(xiàn)的多種可行方案下，選取綜合效益最優(yōu)的方案；

6) 其他約束條件.

對于有條件下的隨機分配模型，可能存在多種并行的可行方案，一般地，這些方案在單一的完成既定任務(不考慮額外效益)的情況下，均是可行的有效規(guī)劃.我們將在如上的框架下，具體研究相應的時間表優(yōu)化問題[2].以上則給出了我們考慮此類問題的一般性問題的提出，并可結合實際，得到符合具體問題的問題背景與建模步驟.

2 基于有條件隨機分配的課表制定問題

2.1 課表制定的主要難點 課表的制定，是要依據(jù)某學校一學期班級所需學習的全部課程，為各位授課教師，在每周均有課程的前提下，安排恰當?shù)氖谡n學習時間，使得如期完成本學期全部授課學習任務.在這其中，主要為了避免關于同一教師/學生同一時間段不同教室的沖突與同一教師/學生不可用時間段的規(guī)避.

2.2 課表制定的一般性問題求解

2.2.1 課表制定一般性問題的背景 某大學學院辦公室需要為該學院某年級的兩個平行班級制定該學期每周的課程表.該兩平行班級中，除去數(shù)學和體育課之外，兩個平行班級的其余各門課程的任課教師均相同.在此大學中，每節(jié)課時長為45分鐘，課間10分鐘.為簡便計，我們不妨將一個上課周期記為2個小時(即包含小課間的兩個課時).此外，同一個班級中的各個學生均需要參加相同課程的學習.

表1 各教師為各班級每周授課節(jié)數(shù)

該大學每周的課程安排為周一至周五，每個上課周期的具體時段分布分別為：8:00—10:00，10:05—12:05,14:00—16:00,16:05—18:05.

表1列出了該學院每個老師每周需要為此兩個班所上的課程節(jié)數(shù)詳情.此外，根據(jù)教務處統(tǒng)一安排，這兩個班級的體育課程統(tǒng)一安排至每周四下午的14:00—16:00時段.每周一鑒于全校統(tǒng)一活動安排，8:00—10:00的第一個上課周期將保留空置，不作授課安排.Mr Gao老師由于在另一所學校兼職任教，故每周一上午不能來本院授課，需為此安排另外時段.Mrs Li老師每周三全天也因故不能來授課，需另擇它時.最后，為了避免學生的課業(yè)疲勞，我們規(guī)定單日單科盡可占用一個授課時段.

問題提出：請為該學院兩平行班級授課教師制定每周的課程表，以滿足該學期全部授課任務.

以上問題即為典型的有條件的隨機分配時間表優(yōu)化問題.

由此，我們可通過Lingo 12.0計算得出符合規(guī)劃的問題優(yōu)化解.

2.2.3 課表制定一般性問題的結論 我們由此得出課表制定的一個結果，此結果如下所示：

表2 該學院1班課程表

表3 該學院2班課程表

此課表制定結果有多個平行的可行解.

3 基于有條件隨機分配的工作排班表問題

3.1 工作表排班的主要難點 本案例的主要難點類似于上一案例，只是此處更加著重的凸顯了排班在滿足要求下的隨機性與各工作人員分班的均勻性，以保證排班的公平，并適當合理可預留出機動的人員與時間[4].

表4 本節(jié)變量表

表5 風電場全年人員值守/維護排班表

3.2 工作表排班的一般性問題求解

3.2.1 工作表排班一般性問題的背景 在某風電場中，已先后進行了一期、二期建設，現(xiàn)有風機124臺，總裝機容量約20萬kW.為安全生產(chǎn)的需要，各風機每年需進行兩次停機維護，且兩次維護之間風機不得連續(xù)工作超過270天.每次維護需要一組維修人員連續(xù)工作2天，同時為了應對突發(fā)情況，風電場每天需要有一組維護人員值班[5].現(xiàn)該風電場有4組維護人員可從事值班或維修任務，且每組人員的連續(xù)工作時長不超過6天.則我們據(jù)此背景制定維修人員的排班方案與風機維護計劃，使得各組維修人員的工作任務相對均衡，且風電場具有較好經(jīng)濟效益[6].

3.2.2 工作表排班一般性問題的求解我們將待解決的問題歸納為以下約束條件

：1) 我們僅安排值班和維護人員表格，對于條件中的“每臺風機每年需在270天內(nèi)維護至少兩次”，我們根據(jù)計算得出，一年中約有42周(共52周)時間需安排每周至少6天維修方可完成任務，故除去節(jié)假日和某些不可控等因素，我們近似認為基本每周都有人員參與維護與值守任務，故本問題關鍵在于處理好“人員連續(xù)工作不超過6天”的約束條件，并合理均衡的安排班次；

2) 若某天某組人員值守，則此組人員在未來6天不可能連續(xù)值班；

3) 若某天及次日某組人員維護，則此組人員在未來6天不可能連續(xù)維護；

4) 值守任務與維護任務同一天不可能為同一組人員；

5) 每天至少有一組人員值守，且至少兩組人員維護；

6) 某天某組人員是否值守/維護，設為一0-1變量處理.

本節(jié)中涉及的變量有：

相應的約束條件為：

3. ?j∈days,k∈groups：zhibanjk+weihujk≤1-值守與維護不得沖突；

6. ?j∈days,k∈groups:zhibanjk,weihujk∈{0,1}-0-1變量.則我們最終將給出一個完整具體的4組人員全年值守/維護排班表.

3.2.3 工作表排班一般性問題的結論經(jīng)過相應運算，我們得出了全年該風電場基于已知條件下的可行的人員排班表，如表5所示(僅以1月為例)，按此表排班，即可完成全年值班與維護任務，且人員安排較為均衡；風電場由此可正常安全進行生產(chǎn)生活，且使得具有盡可能多的經(jīng)濟效益，符合案例訴求.

4 結束語

排班表問題的優(yōu)化求解，是實際工作生活中重要的應用方面.我們根據(jù)不同的要求和現(xiàn)實的背景，制定出切實可行的目標函數(shù)與約束條件，并利用計算機相關軟件進行線性與非線性優(yōu)化計算，得出最終的排班結果.要求我們對于普遍的工作人員來安排的工作任務量較為均勻，使之工作地位和分量均等，從而體現(xiàn)出公平合理的排班原則.

[1] 趙東方.數(shù)學模型與計算[M].北京:科學出版社,2007.

[2] 黃干平，姚自珍，張軼靜.使用模擬退火算法解課表問題[J].武漢大學學報(自然科學版),2000,46(5):559-563.

[3] Christelle Gueret,Christian Prins，Marc Sevaux.運籌學案例[M].北京林森科技發(fā)展有限公司(譯),2006.

[4] 熊偉清，魏平，趙杰煜.用遺傳算法求解時間表問題[J].中國衛(wèi)生質量管理,2001,1(5):29-32.

[5] 杜實,趙金路.多跑道進場航班調(diào)度研究[J].科技和產(chǎn)業(yè),2013,13(4):135-139.

[6] 劉朝暉,俞文鮆.關于工件組的兩機自由作業(yè)時間表問題[J].華東理工大學學報，2000，26(6):665-669.

(責任編輯 趙燕)

Timetable optimization based on conditional random allocation: a case study of school schedule and work schedule of a wind farm

WANG Huiling1,TAN Zijian2,ZHANG Ren3

(1. College of Engineering, Xianning Vocational and Technical College, Xianning 437100, China；2. School of Mathematics & Statistics, Central China Normal University, Wuhan 430079, China；3. Wuhan Huaxia Institute of Technology, Wuhan 430223,China)

The schedule optimization problem is widely used in various social production activities, however, due to specific tasks are subject to specific constraints, it is difficult to develop a comprehensive schedule of work in line with constraints. In this paper, we focused on the generalized stochastic distributions under conditional constraints. Based on the mathematical modeling and the simulation of the related software, we established the objective function and constraint type according to the constraint, and carried out the correlation operation, and give a scientific and feasible execution schedule. To ensure the effective completion of the work. We take the school schedule and work schedule as an example to illustrate the schedule under the conditions of random distribution optimization problem, give the final operable work process and its effectiveness evaluation.the results can be applied to engineering scheduling, time scheduling, personnel distribution and so on. It has wide application value in many related industries.Key words: mathematical modeling; timetable; class schedule; work schedule; Lingo

2017-02-26

湖北省自然科學基金(2016CFC747)資助

汪慧玲(1981-)，女，講師；張韌，通信作者，講師，E-mail:43862746@qq.com

1000-2375(2017)03-0253-05

O221.2

A

10.3969/j.issn.1000-2375.2017.03.008