基于Excel和OpenSolver的排班優(yōu)化教學(xué)輔助工具

鄭自然　張鴻雁

摘 要：為了建立教學(xué)環(huán)境下簡易且獨立的教學(xué)輔助工具，文章基于Excel平臺和OpenSolver插件，建立了一個人員排班問題的模型展示和求解工具。該工具主要包含問題的建模和解的展示界面。教師可以使用該工具較為清晰地向?qū)W生展示問題的結(jié)構(gòu)和建模過程。學(xué)生可以借助該工具提供的思路和方法建立自己的模型。該工具包含一個具體的源自實際生活中的排班問題，且能夠求解較大規(guī)模的問題實例，目前已經(jīng)在山東師范大學(xué)的優(yōu)化相關(guān)課程中使用。反饋結(jié)果表明該工具能夠幫助學(xué)生更好地學(xué)習(xí)和理解排班優(yōu)化相關(guān)知識。

關(guān)鍵詞：人員排班;整數(shù)規(guī)劃;Excel;OpenSolver

中圖分類號：C93-03 ? ? ? 文獻標(biāo)志碼：A ? ? ? ? ?文章編號：1673-8454（2021）02-0092-05

一、引言

人員排班是一類重要、常見且較為復(fù)雜的優(yōu)化問題，近年來一直受到學(xué)術(shù)界的關(guān)注[1][2]。從教授運籌學(xué)和優(yōu)化相關(guān)課程的角度來說，人員排班也是一類具有代表性的優(yōu)化問題。通過對該類問題的講授，學(xué)生可以了解針對實際問題的建模過程，掌握常見的整數(shù)規(guī)劃約束的建立方法，并進一步學(xué)習(xí)優(yōu)化問題的求解方法。

作為一種復(fù)雜的優(yōu)化問題，對該問題的求解需要用到多個軟件平臺和工具的組合，例如高級語言集成開發(fā)環(huán)境、優(yōu)化求解器、建模工具包及其他相關(guān)的工具。在課堂講授環(huán)境中，利用這些軟件組合來講授優(yōu)化問題具有一定的不便性。首先，大部分軟件都不是免費的，有些軟件的教育版本學(xué)生并不方便申請。其次，這些軟件大都建立在高級編程語言基礎(chǔ)之上，學(xué)生在能夠求解和理解問題之前需要具備一定的代碼閱讀和編程能力，這對于初學(xué)者或是沒有高級語言背景的學(xué)生產(chǎn)生了一定的阻礙。另外，安裝和配置相關(guān)的軟件組合較為復(fù)雜，學(xué)生和教師在配置的過程中需要花費較多的精力，因而造成無法將主要精力集中在問題的講述和理解上。因此，獨立且輕量級的教輔工具更適合課堂環(huán)境的使用。

Microsoft Excel作為一種常用的表格計算和統(tǒng)計軟件，不僅可以作為多功能的表格呈現(xiàn)和計算工具[3-7]，近年來在課堂教學(xué)環(huán)境中也開始扮演重要角色。越來越多的教育工作者將電子表格軟件作為一種輕量級的計算平臺進行輔助講授[8-11]。國內(nèi)相關(guān)研究目前還比較少，如丁以中[12]以趕工問題為實例，探討了Spreadsheet教學(xué)法的優(yōu)勢。作為對于該領(lǐng)域的補充，同時為了解決本單位教學(xué)輔助的問題，本研究使用Microsoft Excel 2016及OpenSolver 2.9.0，設(shè)計了一個基于電子表格的人員排班優(yōu)化軟件工具，既可以作為實際問題的求解器，同時也能夠展示優(yōu)化問題的模型和建模過程。

二、排班問題模型描述

1.排班問題的描述和決策變量

排班問題形式較多，根據(jù)不同的情況有不同的變化。作為教輔工具考慮到問題的一般性和具體性，本工具采用了一個較為簡單但擴展性較強的問題進行展示。當(dāng)學(xué)生對該模型熟悉后，可以使用類似的模型來描述更為復(fù)雜的問題。假設(shè)一個時間段內(nèi)包含多天，工作單位需要在一天的時間內(nèi)對不同的員工分配班次。該問題可以用來描述一大類問題，例如護士排班問題、呼叫中心排班問題或者其他種類的多班次的排班問題。這里用I={1，2，…，|I|}來表示員工的集合;K={1，2，…，|K|} 來表示班次的集合;J={1，2，…，|J|}來表示天的集合（其他問題中也可為其他時間單位，例如小時或者周）。則決策變量xijk可以定義如下：

xijk=1，如果班次k在時間j分配給員工i0，其他

大部分的人員排班問題具有軟約束和硬約束。在優(yōu)化過程中軟約束包含一些來自單位和員工的偏好，這類約束需要盡可能地滿足;而硬約束則來自一些資源限制和硬性要求，這類約束需要必須滿足，否則解為不可行性解。人員排班問題的建模是圍繞不同的軟硬約束進行建模。下面介紹這個問題的具體模型，包括約束條件和目標(biāo)函數(shù)。

2.排班問題的數(shù)學(xué)模型

由于在課堂上一般需要介紹具體的問題實例，因此問題的參數(shù)采用固定的數(shù)值;教師和學(xué)生可以進行相應(yīng)的改變來講授自己需要的問題實例。模型中用到的符號如下：

I ?員工的下標(biāo)集合： I={1，2，…，5}，|I|=5;

K ?班次的下標(biāo)集合： K={1（白班），2（晚班），3（夜班），4（休息）};

J ?時間下標(biāo)單位集合;這里時間單位采用天，且總時間段為兩周： J ={1，2，…，14}，|J |=14;

dji ? 在第j天需要班次k的數(shù)量，即某天的班次需求（具體數(shù)值在表格中設(shè)置）;

wmax 在總時間段內(nèi)為一個員工的總工作天數(shù)的上限： wmax= 10;

nmax ?在總時間段內(nèi)為一個員工的總夜班天數(shù)的上限： nmax= 3;

問題的數(shù)學(xué)優(yōu)化模型定義如下：

模型中的約束（2-4）為硬約束，（5-6）為軟約束。其中，約束（2）要求對于總時間段的某一天，為所有員工分配的班次要滿足當(dāng)天的班次需求。約束（3）確保某個員工在某一天只能被分配一個班次。約束（4）描述了當(dāng)某個員工被分配到夜班時，下一天則需要分配休息。約束（5）確保了在總時間段內(nèi)，某個員工的工作天數(shù)不能超過工作上限，這里采用了松弛變量將該約束構(gòu)造成為一個軟性約束。約束（6）原理同（5），確保夜班的天數(shù)盡可能地不超過上限。約束（7-8）為決策變量和松弛變量的定義域。

注意到松弛變量si（和ti）刻畫的是某個員工實際工作（夜班）天數(shù)和規(guī)定工作（夜班）天數(shù)上限的差，因此，模型的目標(biāo)函數(shù)則定義為盡可能地減少這兩個變量的值，即目標(biāo)函數(shù)（1）的定義。

三、軟件使用介紹

1.OpenSolver簡介

盡管Excel軟件中內(nèi)嵌一個線性規(guī)劃的求解器，但是該求解器的完整版并不免費。試用版本有變量的限制（可變單元格不能超過200個），這對于稍大規(guī)模的問題或者約束為指數(shù)級的問題則無法求解。對于上節(jié)闡述的問題，僅主要決策變量xijk的數(shù)量就為280，因此無法使用自帶的線性優(yōu)化求解器來求解。

本軟件采用了OpenSolver[9]工具箱來代替默認(rèn)求解器進行排班問題的建模和求解。該工具是一個基于開源求解引擎的Excel第三方插件。該插件開源，免費且易安裝，因此較為適合基于Excel的優(yōu)化問題的展示和求解。由于其使用的求解引擎本身也是免費的，因此理論上并沒有變量的限制。圖1為該插件的主要操作界面，該界面的結(jié)構(gòu)與Excel默認(rèn)的求解器結(jié)構(gòu)相似。在圖示指示的框中可添加相應(yīng)的單元格地址來設(shè)置模型的目標(biāo)函數(shù)、決策變量和約束。任何具備線性規(guī)劃基礎(chǔ)知識的學(xué)生都可以很快熟悉該插件界面的使用。

2.輔助工具界面描述

本研究建立的輔助工具界面如圖2所示。為了方便構(gòu)造約束條件，在該區(qū)域需要存放相應(yīng)的表達式單元格。圖2中，該區(qū)域中sum（k）所在的行，即為j取某個值時，xijk變量基于下標(biāo)k的加和，也是某個員工在某一天所有班次的和。這個表達式可以通過Excel自帶的函數(shù)公式表示。該單元格用來構(gòu)造模型中的約束（3），即某個員工在某一天只能分配一個班次。圖3展示了一個該約束構(gòu)造的示例。

圖3 中，“D3”到“D6”單元格為j=1時的決策變量的值。當(dāng)構(gòu)造模型時，OpenSolver可以將已添加的區(qū)域進行高亮。單元格“D7”的內(nèi)容為“=SUM（D3：D6）”，即D7單元格的值為D3—D6單元格值的和。在OpenSolver的界面中，則可以設(shè)置單元格“D7”等于1。

其他的約束類似，均使用表達式單元格來進行描述。例如圖2中決策變量下方為人員需求區(qū)域。圖4為該區(qū)域的部分截圖，第32、34和36行為在某一天的某個班次k的需求數(shù)值，用req.標(biāo)識。這里我們使用D表示白班，L表示晚班，N表示夜班。如圖4所示，在E列，對于白班的人員需求是2。第33、35和37行則計算的是所對應(yīng)的決策變量的和。利用這個區(qū)域可以實現(xiàn)描述模型中的約束（2）。圖4中的高亮邊界單元格為添加“E32”等于“E33”后的狀態(tài)。

在圖2的下方是解的顯示區(qū)域。這里我們用相應(yīng)的符號來填寫排班表的值。該區(qū)域同樣可以通過Excel的函數(shù)來實現(xiàn)。這里我們采用了Choose函數(shù)和Match函數(shù)結(jié)合決策變量的判斷來填寫排班表。整體的表格建立盡可能地對齊相關(guān)的維度以便觀察和函數(shù)的賦值。圖5為添加完所有決策變量，約束和目標(biāo)函數(shù)值后的單元格的示例。能夠看出通過OpenSolver的高亮功能，可以較為清楚地觀察已經(jīng)添加的變量和約束及參數(shù)之間的關(guān)系。

盡管由于考慮教學(xué)的因素采用的問題規(guī)模較小，使用者可以根據(jù)該結(jié)構(gòu)任意擴沖單元格的數(shù)量并添加相應(yīng)的變量和約束來求解更大規(guī)模的問題。另外，由于對問題的表達形式并不唯一，在使用該工具時我們鼓勵學(xué)生在理解了方法后采用自己的方式來對問題進行單元格的安排和建模。另外，該表格沒有用到任何VBA（Visual Basic for Applications）代碼，進一步降低了使用該工具的背景知識需求。對于該問題，求解器的求解時間約為0.1秒。

四、學(xué)生對軟件的評價調(diào)查

本工具已經(jīng)被應(yīng)用到本單位2018—2019學(xué)年信息管理本科二年級《大數(shù)據(jù)概論》與優(yōu)化相關(guān)章節(jié)的講授中。該章節(jié)的主要目的為介紹基本和部分高階的優(yōu)化領(lǐng)域的理論和算法。在整數(shù)規(guī)劃一節(jié)，教師在講解一些實際生活中的整數(shù)規(guī)劃實例，即這里所提供的人員排班優(yōu)化問題過程中采用了該工具。該課程大部分的學(xué)生具備線性規(guī)劃的知識背景，但不具備復(fù)雜整數(shù)規(guī)劃模型建立的知識，且對于一般優(yōu)化軟件平臺并不熟悉。另一個考慮是在該階段，采用中等規(guī)模問題作為過渡能夠降低學(xué)生接觸更為復(fù)雜的問題的學(xué)習(xí)曲線。主要教學(xué)方法是當(dāng)教師講授完課本數(shù)學(xué)模型后，輔助使用該工具進行模型的建立和求解。

為了得到學(xué)生對該工具以及相應(yīng)教學(xué)方式的反饋，課后我們對學(xué)生進行了問卷調(diào)查。問卷包含了10個評價項目，分?jǐn)?shù)范圍為1至5。32名學(xué)生參與并回復(fù)了問卷。由于學(xué)生在實驗課中也使用過該工具，因此評價項目中也包含對該工具的使用評價。項目的評價平均值見表1。

問卷10項的整體平均分為4.20，表明了該工具作為一種優(yōu)化模型輔助工具的易用性和適用性。其中最高分為第8項，即學(xué)生認(rèn)為該工具能夠幫助他們理解和學(xué)習(xí)人員排班問題。最低分是第4項。其主要原因是部分學(xué)生沒有用過Excel本身的線性求解器，進而對OpenSolver的界面并不熟悉。然后在課堂和課后的實驗過程中，經(jīng)過簡單的解釋，大部分學(xué)生能夠很快掌握方法，且所有學(xué)生均能夠使用該軟件完成實驗任務(wù)。

其中，項目1至3是關(guān)于工具的界面設(shè)計，這些項目的分?jǐn)?shù)均高于4分，證明該工具的界面安排合理并易于使用;項目5是關(guān)于工具的建模操作，該項目的分?jǐn)?shù)高于4分，證明使用該工具的建模操作步驟易于理解; 項目7是針對約束添加方式，該項目分?jǐn)?shù)相對較低，主要原因在于部分學(xué)生是第一次使用Excel表達式的方式對約束條件進行刻畫，而對于一些Excel表達式也不夠熟悉。另外，該模型涉及一定的0-1規(guī)劃建模知識，而學(xué)生只是具備一般線性規(guī)劃模型的背景知識。項目8至10是關(guān)于該工具對于整體教學(xué)效果的評價。項目分?jǐn)?shù)均大于4.30，證明該軟件作為輔助教學(xué)工具能夠幫助學(xué)生學(xué)習(xí)和理解人員排班問題，即一般性的整數(shù)規(guī)劃模型。

五、結(jié)論

電子表格作為一種學(xué)生和教師都比較熟悉且易于獲得的軟件工具，其較強的計算和可視化功能使其越來越多地在工業(yè)應(yīng)用和教學(xué)環(huán)境中扮演重要的角色。本研究建立的輔助工具提供了一種教學(xué)環(huán)境下利用電子表格來呈現(xiàn)和求解整數(shù)規(guī)劃模型的思路和方法。憑借免費的Excel插件OpenSolver，該工具不僅可以更加清晰地呈現(xiàn)建模過程，同時也可以作為求解器來求解實際規(guī)模的問題實例。從反饋結(jié)果可以看出學(xué)生能夠接受并肯定其相關(guān)的教學(xué)方式。該方式不依賴復(fù)雜的優(yōu)化軟件平臺和軟件包，不需要高級語言編程能力，對于非計算機背景的學(xué)生或者還不具備高級語言編程的初學(xué)者來說，有利于教學(xué)活動的開展和相關(guān)知識的學(xué)習(xí)。

在后續(xù)的工作中，筆者擬對以下幾個方面進行研究：首先該工具當(dāng)前的目標(biāo)主要集中在模型建立方面，而求解方法采用的是默認(rèn)的整數(shù)規(guī)劃引擎進行求解。對于排班問題目前有更為復(fù)雜和高級的算法，例如列生產(chǎn)算法[13]。因此如何使用Excel并結(jié)合VBA語言建立更為復(fù)雜的算法及展示平臺是后續(xù)的工作方向之一。其次，針對不同的特點員工排班問題，可以使用多種建模方式進行刻畫，例如基于圖的方式[14]能夠避免較多的約束條件，從而加速求解過程。如何使用該工具實現(xiàn)其他方式的建模并予以展示是另一個研究方向。最后，借助Excel平臺實現(xiàn)啟發(fā)式或者元啟發(fā)式算法來求解困難的組合優(yōu)化或離散優(yōu)化問題，從而建立一個綜合性的優(yōu)化問題求解教輔工具，是后續(xù)的主要研究方向之一。

參考文獻：

[1]Jorne Van den Bergh，Jeroen Beli？觕n，Philippe De Bruecker，et al.Personnel scheduling：A literature review[J].European Journal of Operational Research， 2013，226（3）：367-385.

[2]Philippe De Bruecker，Jorne Van den Bergh，Jeroen Beli？觕n，et al.Workforce planning incorporating skills： State of the art[J].European Journal of Operational Research，2015，243（1）：1-16.

[3]喻靖，朱峰，夏瑞杰.基于Excel VBA實現(xiàn)油田報表自動化設(shè)計[J].價值工程，2020，39（9）：193-194.

[4]顏曉佳，張勝.基于Excel軟件的成績管理系統(tǒng)設(shè)計與開發(fā)[J].教學(xué)與管理，2020（7）：15-17.

[5]李道西，勝志毫.基于Excel規(guī)劃求解的泵站加壓灌溉管網(wǎng)優(yōu)化設(shè)計研究[J].中國農(nóng)村水利水電，2020（1）：36-38.

[6]何明宇.EXCEL在配送路徑優(yōu)化中的應(yīng)用[J].價值工程，2019，38（27）：216-218.

[7]G. Erdo ?an. An open source Spreadsheet Solver for Vehicle Routing Problems[J].Computers & Operations Research，2017（84）：62-72.

[8]John Baker and Stephen J. Sugden. Spreadsheets in education–The first 25 years[J].Spreadsheets in Education，2003（1）：18-43.

[9]S. Demir，M. Demir，et al.An MS Excel tool for water distribution network design in environmental engineering education[J].Computer Applications in Engineering Education，2018，26（2）：203-214.

[10]S. Fernandez，J.A. Orosa，J.J. Galan.A new methodology to teach numerical methods with MS Excel[J].Journal of Maritime Research，2012（9）：29-32.

[11]A.J. Mason.OpenSolver-an open source add-in to solve linear and integer programs in excel[C].Operations research proceedings 2011， Springer，2012：401-406.

[12]丁以中.在管理科學(xué)教學(xué)中運用Spreadsheet教學(xué)法的探討[J].上海海運學(xué)院學(xué)報，2002，23（1）：76-81.

[13]Jonathan F. Bard and Hadi.W. Purnomo.Preference scheduling for nurses using column generation[J].European Journal of Operational Research，2003，164（2）：510-534.

[14]D.S.W. Lai，J.M.Y. Leung，W. Dullaert，et al.A graph-based formulation for the shift rostering problem[J].European Journal of Operational Research，2020，284（1）：285

-300.

（編輯：魯利瑞）