（计算机软件与理论专业论文）雇员班次安排问题的算法研究.pdf

黄伟思雇员班次安排问题的算法研究中山大学硕士学位毕业论文2 0 0 5 年5 月 雇员班次安排问题的算法研究 专业：计算机软件与理论 硕士生：黄伟恩 指导教师：郭嵩山 摘要 雇员班次安排问题( 艟i n i m u ms h i f td e s i g np r o b l e m m s d ) 是劳动力资源计划 问题的核心，是提高劳动效率的一个关键。它的应用领域非常广泛，其研究成果可以 广泛应用于大型公司、大型商务中心、超市、高档酒店等大型企业的雇员班次安排 问题。在实际应用中，雇员排班问题大部分可以归结为两个因素：1 每个时段需求的 雇员数目：2 各种可供选择的上下班时间。问题的核心就是如何安排雇员在规定的时 间内工作以尽量满足每个时段的雇员数目的需求，同时使班次的数目尽量少 本论文将对m s d 问题进行深入的研究，结合前人的研究成果，把原问题抽象为 数学模型。给出规划方程并对问题的需求表特征进行分析，从而推导出从雇员需 求表特征出发进行求解的各种方法，并列出各种算法下的实验结果。 关键字：班次安排雇员需求表 黄伟恩雇员班次安捧问题的算法研究中山大学硕士学位毕业论文2 0 0 5 年5 月 r e s e a r c ho nm i n i m u ms h i f td e s i g np r o b l e m m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：w e i e nh u a n g s u p e r v i s o t ：s o n g s h a ng u o a b s t r a c t m i n l m u ms h md e s i g np r o b l e mi sak e yp r o b l e mo fl a b o rr e s o u l c e t h e , s o l u t i o no f t h i sp r o b l e mc a nh i g h l yi m p r o v et h ee f f i c i e n c yi np r o d u c t i o n i tc a l lb ew i d e l ya p p l i e dt o b i gc o m p a n i e s , b u s i n e s sc e n t e r , s u p e rm a r k e t f a c t o r i e sa n ds oo n w bc a l la b s t r a c tt w o m a i nf a c t o r sf r o mt h i sp r o b l e mi na l m o s ta l lp r a c t i c a la p p l i c a t i o n ：i ：t h en u m b e ro f e m p l o y e e sn e e d e di ne v e r yt i m es l o t ；2 ：t h es e l e c t i o no fa v a i l a b l ew o r k i n gt i m e t h ek e y p r o b l e mi sh o wt oa s s i g na sl e s ss h i f t s 鸲p o s s i b l ef o re m p l o y e e sw h i c hm a k e st h er e a l n u m b e r o f w o r kf o r c en e a ro re q u a lt h er e a ln e e di ne v e r yt i m es l o t i nt h i sp a p e r , 1w i l id oad e e p l yr e s e a r c hi nm s d p r o b l e m c o m b i n i n gt h er e s e a r c h s o 扭f 1m a k et h em a t b e m a t i c sm o d e la n dd r a wt h ee q u a t i o nf r o mt h i sp r o b l e m a f t e rt h a t , ir e s e a r c ht h ep r o b l e mw i t ht h ef e a t h e r o f e m p l o y e e - r e q u i r e m e n t - t a b l e ，a n dd e d u c et h e r e l a t e da l g o r i t h m ia l s or e s e a r c ha n dd os o m ee x p e r i m e n t sa b o u tt h ep r o b l e m a n dlw i l l s h o wt h ee x p e r i m e n tr e s u l t st oc o m p a 辩w i t ho t h e ra l g o r i t h m s k e yw o r k s ：m s d ，s h i f td e s i g n ，e m p l o y e e ，r e q u i r e m e n tt a b l e 2 黄伟恩 雇员班次安捧问题的算法研究中i l l 大学硕士学位毕业论文2 0 0 5 年5 月 引言 雇员班次安排问题( m i n i m u ms h i f td e s i g np r o b l e m m s d 问题) 是个典型的 劳动人员工作计划安排问题，它是从众多班次安排需求中高度抽象出来的。 m s d 问题是由v i c n a u n n c m i t y o f t c c h n o l o g y 和x i m e s c r o p 【6 】提出，它们需 要一种方法来实现企业的班次安排规划，通过选择合适的班次，为每个班次安排合适 的雇员数目，从而满足每个不同时段的劳动力( 雇员数目) 需求，除此之外。还要求少 班次的数目尽可能少。因此m s d 问题便具有两个独立的目标函数：1 需求表的吻合 程度；2 班次的使用数目。求解的过程就是如何使这两个目标函数的罚分达到最少。 m s d 问题已经被证明为n p - h l 州问题f 2 】，很难在有限时间内求出或者判定最优 解。因此，我们要寻找一种搜索策略来对问题求解。对于此问题，文献【1 】使用了解 空间邻域禁忌搜索算法进行求解，并取得了一定的效果。本论文将从另一种途径对 问题求解。通过分析研究劳动力需求表的特征简化问题的规模，进而求出较优解， 并通过实验与文献【1 1 的方法进行了比较。 4 黄伟恩 雇员班次安排问题的算法研究 中l j j 大学硕士学位毕业论文2 0 0 5 年5 月 第1 章简介 m s d 问题是一个偏向实际应用的算法问题，它由典型的劳动人员工作计划安排 问题抽象出来，其应用领域可以涉及到大型公司、大型商务中心、超市、高档酒店 等大型企业。 经典m s d 问题主要由两部分构成： 1 、每个时段所需要的雇员数目，即劳动力需求表，简称需求表； 2 、可供选择的上班时段，包括上班时间和上班时长。 在实际应用中，一般把可选班次划分为几种不同的班次类型，如早班、 晚班等。每种班次类型包含了最早，最迟的上班时间和最短，最长的上班 时段。 经典m s d 是一个n - h a r d 问题，它无法在多项式时间内确定和验证最优解，再 加上实际应用的数据规模比较庞大，因此必须对问题进行优化。本论文使用抽取需 求表特征的方法对问题进行优化，大大降低了问题的搜索空间。本文还根据需求表 差额的特征提出和实现了需求表差额特征搜索算法和需求表差额特征最大流算法， 并在实验中取得了较好的效果。 第2 章问题描述 2 1 典型m s d 问题的基本描述 m s d 问题是一个典型的劳动人员工作计划安排问题。一个m s d 问题一般 给定以下要素： 基本要素。 单位时段的时长i n t e r v a l 一般以分钟为单位如1 5 分钟、3 0 分钟、6 0 分钟等，并能被2 4 小时 整除。 一天共有2 4 * 6 0 皿t e r v a l 个时段。 计划排班的天数d a y 以天为单位，如1 星期为7 天。 雇员需求表 共有d a y 2 4 6 0 i n t e r v a l 项，代表从第一天的0 ：0 0 开始的每个单位时段 所蔫求的雇员数目。 班次类型表 给出若干个班次类型，每个班次类型包括： 1 、最早上班时间：m i n s t a r t ； 2 、最晚上班时间：m a x s t a r t ； 3 、最短上班时长：m i n l e n g t h ： 4 、最长上班时长；m a x - l e n g t h 。 在排班时所有班次都必须属于某个给定的班次类型。 值得注意地是，有的班次类型所包含地班次可能会跨过零时，如班 次l 起始时间：2 3 0 0 ，长度4 2 0 分钟】，如果在计划的最后一天给这个班 次安排雇员，那么这个雇员的工作将会影响到计划的第一天( 就像星期 天的晚班工作到星期一的早晨) 。存在这种班次的m s d 问题我们称为循 6 黄伟恩雇员班次安排问题的算法研究 中山大学硕士学位毕业论文2 0 0 5 年5 月 环m s d 问题。 优化要素： 每分钟实际雇员数目超出需求表预算雇员数目的罚分w 1 。 每分钟实际雇员数目少于需求表预算雇员数目的罚分w 2 。 所用的班次数目，每个罚分为w 3 。 注意不同天数会有同一个班次。如星期一的f 7 ：0 0 1 4 ：0 0 】班次和星期二的 f 7 ：0 0 1 4 ：0 0 班次属于同一个班次，不用累加罚分。 一般情况下，需求表的符合程度远远比班次数目重要得多，因此在优化 求解时可以优先考虑如何贴近需求表，再进一步减少班次得数目。 求解输出： m s d 问题得输出是一份排班计划安排表，包括以下要素： 使用了哪些班次。 每个班次在每一天安排工作的人数。 该安排表实际运作时的罚分( 罚分越少解约优) 。 2 2 典型m s d 问题的具体例子 为了更好地理解m s d 问题，这里给出一个m s d 问题地实际例子： 一个企业需要排班，给定每个时段的需求表见表2 - 1 ： 表2 - 1 开始结束星期一星期二星期三星期四星期五 星期六 星期日 6 ：0 08 ：0 0 2226200 8 ：0 09 ：0 0 5559533 9 舶 1 0 ：0 07771 3755 1 0 ：0 01 1 = 0 0 9991 5977 1 1 舶1 4 = o o777 1 3755 1 4 ：0 01 6 ：o o1 0 9791 055 1 6 ：0 01 7 ：0 076 46722 1 7 ：0 | o2 2 ：0 0542 2 5 oo 2 2 ：0 06 ：0 05 5 5 5555 7 堕堡昼塞里壅达塞捧问题的算法研究 中山大学硕士学位毕业论文 2 0 0 5 年5 月 给定班次类型见表2 - 2 表2 - 2 班次类型最早上班时刻最迟上班时刻 最短工作时间最长工作时间 早班 6 ：0 0 8 ：0 0 7 小时9 小时 上午班 9 ：0 01 1 ：0 0 7 小时9 小时 下午班 1 3 ：0 01 5 ：0 0 7 小时9 小时 晚班 2 2 ，0 02 4 ：o o 7 小时9 小时 从上述需求可以看出t 它的单位时长是1 小时： 计划安排天数是1 周( 共7 天) ； 需求表共有2 4 7 = 1 6 8 项； 班次类型有4 种，每种班次类型包含多种班次选择t 如早班类型的选择班次可以是： 【6 0 0 ，7 小时1 ；【6 0 0 ，8 小时】； 6 - 0 0 ，9 小时】； 7 - 0 0 ，7 小时j ；【7 伽，8 小时】；【7 0 0 ，9 小时】； 【8 0 0 ，7 小时】；【8 0 0 ，8 小时l ：【8 0 0 ，9 小时1 。 我们的目标是制定个尽可能贴近需求表，班次类型尽量少的班次安排 计划，其中一个可能的解决方案见表2 - 3 ： 表2 - 3 开始长度星期一星期二 星期三星期四 星期五星期六 星期日 6 ：0 0 8 小时 2226200 8 ，d 0 8 小时 3 333333 9 ：0 0 8 小时 2224222 1 4 ：0 0 8 小时 5422500 2 2 ：0 0 8 小时 555 5 55 5 这个方案使用了5 种班次，不过并没有完全满足需求表，每天的 9 0 0 1 0 ：0 0 仍然缺少两个雇员。 8 黄伟恩 雇员班次安排问题的算法研究中山大学硕士学位毕业论文2 0 0 5 年5 月 2 3 典型m s d 问题的数学模型 对于2 1 提出的m s d 问题，我们需要把它抽象为数学模型，再对它进行求 解。 给定以下条件： 计划时段：0 t 1 ； 班次类型：v l v 2 v 。； 其中v i 包括 m i ns t a r t ，m a xs t a r t ，m i ni c n g t h ，m a xl e n g t h ； m i ns t a r t ：最早开始时刻； m a xs t a r t ：最迟开始时刻： m i nl e n g t h ：最短工作时间； m a x l e n g t h ：最长工作时间。 在每个时段t 中，给定最优需求人数r e q t 。 约束条件： 对于每个班次类型v i ，一共可以生成k i = ( m a xs t a r t - r a i ns t a r t ) * ( m a x l e n g t h - m i nl e n g t h + 1 ) 个班次。 班次x ( d ，i ，j ) ：第d 天第i 个班次类型的第j 种选择，它从时刻s ( d ，i ，j ) 开 始到e ( d ，i ，j ) 结束。即它影响需求表中的r e q s ( d ，i ，j ) 到r e q e ( d ，i ，j ) 项。 班次覆盖集合庐( f ) = x ( d ，i ，j ) 1s ( d ，i ，j ) = t = 1 ) r e q l n c 嘲= r e q f o 】- r e q i t - 1 】 那么r e q i n c t 就反映了需求表在第t - 1 时段到第t 时段的增量，它对求解 有很重要的启发性： 如果r e q i n c t = o 则第t 个时段很可能没有雇员上下班； 1 1 璺童堡一生星整盗塞壁塑璧竺兰鳖壁塑 ! 些查兰堡圭堂堡望些丝苎! ! 堕墨! 星 如果r e q i n c t o 则第t 个时刻很可能多了r e c i j n c 【l 】个雇员上班； 如果r e q i n c t o 则第t 个时刻很可能有旧q j n c 【t 】个雇员下班。 因此，采用需求增量表可以大大减少搜索规模，突出需求表差额和班次安排 的矛盾，从而快速求得较优解。 3 3 需求增量表的使用 3 3 1 增建的模型记号 为了方便模型的描述，定义如下记号： i n t e r v a l ：每个阅隔的分钟数。 d a y s ：需求表涉及的天数。 t o t a l l e n g t h ：输入需求表的总长度，其值为2 4 * ( 6 0 l n i e r v a l ) * d a y s 。 r c q i = 第i 个时段还需要工作的人数( 动态需求表) 。 值得注意的是这里的r e q 意义和输入的需求表有所不同，在没有班次 安排时它等价于输入需求表，但会随着班次安排的改变而改变。 r e q i n c i ：非循环动态需求增量表。 其中r e q i n c o l = o ，r e q i n c i f r e q i - r e q i - 1 , ( o i t o t a l l e n g t h ) ， 值得注意的是这里的r e q i n c 是动态的，随着班次安捧的改变而改 变，而且这里的增置表是非循环的，邵r e q i n c o 的值不为 r e q o - r e q i t - l 】，丽是为0 s h 谂【i j 】= a ：即安排a 个雇员到从时刻i 开始到时刻j 结束的班次。 3 3 2 需求增量表的数学分析推导： ( 1 ) 根据r e q i n c 的定义，可以看出 上 r e q i = ( r e q 1 - r e q 【o 】卜如q 【2 】啊q 【1 】) + + ( r e q i - r e q i 1 1 ) = 罗嘲跏啦l ； 嗣 ( 2 ) 如果安排s h i f l i , j f a ，则此班次影响的时段需求的雇员数目均减少了a ， 即等价于令r c q i ，r e q i + 1 ，r c q i + 2 1 坤q 【i - l 诠部减去a ，那么： r e q i n c i = r e q i - r e q i - 1 】，所以r e q i n c 【i 】也减少了a i 对i k o 的项，如果不存在则打印班次安捧，结束l ( 2 ) 寻找时刻集合p ，对任意p e p ，班次s h i f t i ，p l 是合法班次； ( 3 ) 在 p l 寻找最小的p 有t e q i n c b l o ，则安排s h i f t | i , p l = a ，即 r e q i n c i - - - a ，m q i n c l n + = a ，至少使其中一个值清零； ( 4 ) 返回( 1 ) 。 当然，这个方法还会有其它问题，比如对p 是空集或者不存在p p 有 r e q i n c p 0 ， 贝q 有可能在第i 时刻开始有r e q i n c i 个雇员上班， 1 6 黄伟恩 雇员班次安捧问题的算法研究中山大学硕士学位毕业论文 2 0 0 5 年5 月 班： 或者在第i 时刻开始有n 个雇员上班，有n + r e q i n c i 】个雇员下 如果r e q i n c i o 且i f f i e a r l i s t t i m e r ， 这个增薰只能由第一天的早班实现，所以设定安排人数搜索的 开始点为e a r l y u p 点。 当e a r l y u p 被确定且e a r l y u p = e a r l i s t t i m e r ， 这个下降量被认为是晚班人员的下班实现的。 e n d p m v i d el 为r e q e a r l y u p - 1 。 由于最后一天晚班不能解决0 时以后的增量，所以从e a r l y u p 时刻开始以后的迁移人数不能大于e n d p m v i d e ，保持递减。 在需求表的分离中，从e a r l y u p 到e n d m a x a f f 中所有r e q u r e m e n t 的上升都 认为是早班的贡献，而所有r e q u r e m e n t 的下降都认为是晚班的贡献。分离算法 就是基于这个原则来做的。 定义分离算法如下； 定义v n i f m a x ( o , r e q i 1 - r e q i 】) 黄伟恩雇员班次安捧问题的算法研究 中i i i 大学硕士学位毕业论文 2 0 0 5 年5 月 令d o w n = d n e n d m a x a f f 。 i = 从e n d m a x a f f 时刻向前扫描到e a r l y u p 时刻 i f f d o w n r e q i ) d o w n f r c q i ； r e q l i = d o w n ； r e q i + t o t a l l c n g t h + = d o w n ； 即i 时刻分派d o w n 个劳动力去r e q 表末 i f ( d n i i o ) d o w n + f d n i ； ，如果第1 i 】时刻r e q n r e m e n t 下降则认为是晚班的贡献，加到d o w n 变量中 i f ( d o w n e n d l r o v i d e ) d o w n = e n d p m v i d e ； d o w n 人数不能大于e n d p r o v i d e ，保持分派过去的人数是递减的 例如，对需求表头： 1 8 1 8 1 8 1 8 1 9 1 9 1 7 1 4 1 9 1 9 1 9 1 9 1 9 2 1 经过上述分离算法后，留在早班的r e q 为： 0 0 0 0 9 9 9 9 1 4 1 4 1 4 1 4 1 4 1 6 “果持递增) 分去晚班的r e q 则为( 这写数据将放到r e q t o t a l l e n g t h l 后面) ： 1 8 1 8 1 8 1 8 1 0 1 0 8 5 5 555 55 ( 保持递减) 4 2 具体搜索算法 4 2 1 遗留问题的解决方案 具体搜索算法以3 5 中提供的搜索算法为基础，但是它必须解决简单求解算 法遗留下来的问题： 存在r c q i n c l i l o 但是没有任何班次从i 时刻出发，如何处理? 在此我们提出两种解决方案： 1 9 黄伟恩 雇员班次安排问题的算法研究中山大学硕士学位毕业论文 2 0 0 5 年5 月 1 、不管它，留着给后面的时刻来处理： 2 、找在i 前面最近的最短的能覆盖r e q 【i 】的班次s h i f t 【a b 】，其中a i 为这个班次安排r e q i 个雇员。 但是，无论哪种处理方法，都铁定不能使r e q 表清零，同时很可能影响一堆 r e q 值，甚至把部分0 值变成非0 值。因此，我们最好在出现这种问题之前预防 它的出现，即对于没有从i 时刻班次出发的班次的时刻i ，尽量不要令 r e q i n c i o ，即不要安排s h i f l x ，i 】= a ，使r e q i n c i + a 0 。 4 2 2 具体搜索方法步骤 我们定义两种搜索算法对应4 2 1 的两种解决方案， 选择方案1 的为l o n g s e a r c h ，经实践证明此搜索算法比较慢； 选择方案2 的为q u i c k s e a r c h ，经实践证明此搜索算法比较快。 我们使用分离之后的固定需求表r e q 和由它生成的动态需求增量表r e q i n c 作为输入进行搜索，在搜索过程中，我们只改变r e q i n c 的值，从而算出动态需 求表r e q 的对应值，最终目的是使r e q i n c 表尽量清零。 搜索流程； s e a r c h ( 时段i ，l e f l o u t ( 通过r e q i n c i - l 】计算的r c q i 一1 】的值) ，总 罚分s q ； 1 搜索次数t t 累加1 ，若t t 超过上限煎q 退出； 2 若s c 超出上界则退出； 3 如果i 最后时刻( t o t a l l c ng _ 【h + e n d m a x a f f ) 则 保存解的状态作为景优解，返回； 4 l e f l o u t + f f i r e q i n c i i 此时l e f l o u t 为动态砖q 田的值； 5 如果l e f t o u t 为o ，则s e a r c h0 + 1 1 ，返回： 6 如果l e f t o u t 0 则s e a r c h0 + 1 ，l e f l o u t l s c - l e f l o u t w 3 ) 返回； 7 如果l e f l o u t 0 则执行以下操作，否则返回 8 查找集合p 令s h i f l i ，p 1 合法： 9 如果p 为空集则执行第1 0 步到到1 3 步操作，否则转第1 4 步； l o 对于l o n g s e a r c h ，递归调用s e a r c h0 + 1 ，l c f l o u t , s c + l e f l o u t w 2 ) ， 2 0 黄伟恩雇员班次安捧问题的算法研究中山大学硕士学位毕业论文2 0 0 5 年5 月 返回：如果是o u i c k s e a r c h 转1 1 ： 1 1 找在i 前面最近的最短的能覆盖r e q i i 的班次s h i f t i a ，b 】，其中 a i ，安排r e q i 个人手； 1 2 重新计算l e f t o u t l s c 调用s e a r c h ( i + l ，l e f t o u t , s c ) ，恢复s t e p l o 前的r e q i n c 表，返回； 1 3 第9 步条件结束； 1 4 对集合p 建立优先搜索队列：s o r d 1 l ，s o r d 2 】到s o r d i l p i , 1 5 k = l t o i p i ，循环执行第1 6 步到第1 9 步； 1 6 。安排s h i f l i ，s o r d k l = a 使r e q i n c i ，r e q i n c s o r d i k 】中至少一个清零； 1 7 递归调用函数s e a r c h ( i ，原l e f l o u t ，s c ) ； 1 8 恢复r e q i n c 到s t e p l 5 前的状况： 1 9 第1 5 步循环结束。 流程解释： 搜索函数s e a r c h 包含3 个参数： _时段参数i ，就是当前需要处理的时段变量； 一第1 时段需求的雇工数目l e t l o u t ，它的输入值为动态需求表 r e q 1 1 】的值； 总罚分s c ，就是在第1 个时段的累加罚分，其值为w 1 善y o ) + w 2 善z o ) + w 3 善善。( f ，j ) 见2 3 的数学模型) 。 第1 步：限制搜索次数。由于经典m s d 闯题是n p - h a r d 问题，无法在 有限时间内得出最优解，因此设置搜索次数上限，在搜索达到一定次数 螽输出目前的最优解。 第2 步：设置罚分定界，如果罚分已经超过已知最优解则没有必要再搜 索，强制返回。 第3 步：如果i 大于最后时刻则证明是已经搜索完一个解，保存最优解 第4 步。令i _ e f t o u t = 动态需求表r e q 1 l 的值，就是此刻第1 个时段需要 的瘙员数目。 黄伟恩庙员班次安捧问题的算法研究 中山大学硕士学位毕业论文 2 0 0 5 年5 月 第5 - 7 步：遇到l e f l o u t 0 ， 因此我们必须尽量找到p e p ，m q i n c p o ，根 据4 2 1 ，此时尽量不要找无法从p 时刻出发的班次。 此外，从尽量不要破坏0 值的角度出发，我们尽量不要选用r e q i n c 【p - - o 的 s h i f l i ，p 】班次；从数值大难处理的角度考虑，尽量要选r e q i n c p 尽量少的 黄伟恩 雇员班次安排问题的算法研究 中山大学硕士学位毕业论文2 0 0 5 年5 月 s h i t t i , p 班次。然而，在某些情况下，考虑这两个因素并不一定能得到不考虑这 两个因素更优的结果。 除了上述方案，还要考虑优化班次数量，就是说要尽量选用以前已经用过的 班次。 根据上面的描述，我们可以归纳出优先队列的设置算法： 对于集合( p ) 中任意两个时刻p 1 ，p 2 ，按以下级别进行优先： 1 、如果n q i n c p l l o 则p 1 优先； 2 、如果r e q i n c p 1 , r e q i n c p 2 = 0 ，但是存在由p l 出发的班次不存在p 2 出发 的班次，则口1 优先； 3 、如果心q i n c p 1 1 r e q i n c p 2 = 0 且存在由p l , p 2 出发的班次，则t c q i n c 为非 o 的值优先( 不破坏0 值，减少搜索量) ；如果都为非0 值。则若 r e q i n c p 1 0 ，说明该时段的雇员数目不足够。还差d r e q l l 个雇员才能 达到需求； 如果d r e q 【i l o ，说明该时段的雇员数目比需要的雇员数目多t - d r c q i 个。 虽然搜索结果已经确定，但是我们仍然可以通过一系列班次调整对这个候补 黄伟恩雇员班次安捧问题的算法研究 中山大学硕士学位毕业论文2 0 0 5 年5 月 解进行修正，使它运作时的雇员数目更加贴近需求表。 对于计划内第k 个单位时段： 1 d r e q k = m 0 ，那么这个时段还差m 个雇员才能达到需求。 ( 1 ) 如果存在合法班次s h i f t l ，k + 1 】，并且班次s h i f l t l ，k l 安排了p 个 雇员： 如果p m ， 令s h i f l l k 】减少m 个雇员，这样能使d r e q l t ok - 1 】增加m ； 令s h i f t l , k + 1 】增加m 个雇员，这样使d r e q i l t o k l 减少m ； 最终，在d r e q 表中，d r e q 哟减少了m 变为0 ，其他值不变。 如果p m ， 令s h i f t k + 1 。l 】减少m 个雇员，这样能使d r e q k + lt ol - 1 i 增加m ； 令s h i f t 【呜l l 增加m 个雇员，这样使d r e q k t ol 1 】减少m ； 最终，在d r e q 表中，d r e q k 减少m 变为0 ，其他值不变。 如果p m ， 令s h i f l k 。l 】减少m 个雇员，这样能使d m q 阻t o l - 1 】增加m l 令s h i f t 盼1 ，l 】增加m 个雇员，这样使d m q 阵+ 1t ol 1 】减少m ； 最终，在d r e q 表中，d r e q k 增加m 变为0 ，其他值不变。 如果p o ，那么我们就要设法把结点i 的r e q i n c i 个单位资源通过班 次管道输送到其他结点； 如果r e q i n c 1 j ，则班次跨越第一天零时， 令c = m i n ( r e q i i l j e q 【i + l 】r c q p l 】，t e , q o l , r e q 1 1 r e q u l 】) 因为s h i n i d 的值不会超过c ，所以增加边倒) ，容量c a p i d = c 。 对i = o 到t - h 如果r e q i n c i o ，则增加边( s ，i ) ，容量为r e q i n c i ： 如果r c q i n c i o ，那就在流网络中寻找环路或最近似的环路p ，令c = l e n g t h ( p ) ， 如果m ) - = c 的话，就为这个环路代表的班次安排1 个雇员，并重新计算 m 的值，重复此过程直到m = o 。 如果m - - c 的话，就为对个环路代表班次的减少1 个雇员， 并重新计算m 的值，重复此过程直到m = 0 。 对于问题3 ，由于最大流算法是一次性求单个解的算法，而且最大流算 堕堡垦壁里篓次安捧问题的算法研究 中山大学硕士学位毕业论文 2 0 0 5 年5 月 法和需求表没有直接的关系，因此很难通过调整最大流来解决问题3 。 然而，我们可以把最大流求出的排班方案利用4 4 中提出的候补解的剩 余值修正方案来进行调整，从而部分地解决问题3 。 6 4 算法的总体流程 结合6 1 到6 3 的算法，可以描述出需求表差额最大流算法的流程。首先， 在输入问题数据之后，我们把需求表转换成需求增量表，把所有每一天的所有 班次转换成网络流的结点，把需求增量表的每个表项转换成源点的输入和汇点 的输出；然后调用经典最大流的增广路径求解算法来求解最大流，并且在寻找 增广路径时优先选择已经选择过的班次；当求出最大流方案时，把每个具有流 量的边的流量值作为对应班次的雇员书目转换成排班方案，并计算需求表平均 剩余值m ，当m 不为零时调用6 3 中对问题2 的解决方案，寻找环路或近似环 路直到m 值为0 ，最后把候选解用4 4 中提出的候补解剩余值修正方案来进行调 整，得出最终解并输出。算法流程图见图6 i 。 蔓堡垦 星星塞姿室苎塑墨竺兰鳖受塞 主坐查堂堡主堂堡兰些堡奎 ! ! ! ! 苎! 星 (开始) 数据输入 i 求出需求表平均 建立需求增量衷 7 |剩余数值m 把班次和需求 增量表转换成 根据m 的值寻找环路 网络流图 调整雇员排班方案 j 调用最大流求解 对候补解进行 算法求出最大流 方案 剩余值修正 j 把最大流方案l 1 桂恤m 由b 捧il 蝓m 牲讲甫童l 符鬻件lr 件剐秉i 图6 - 1 需求表差额特征最大流算法总体流程图 黄伟恩雇员班次安捧问题的算法研究 中山大学硕士学位毕业论文2 0 0 5 年5 月 6 5 需求表差额特征最大流算法的实验结果和分析 需求表差额特征最大流算法能够对经典m s d 问题在多项式时间内迅速求 解，为了检测和比较算法效果，仍然使用【5 】提供的测试数据进行实验。结果如 下： 表6 - 1 本论文和【l l 的实验比较结果 数据编号生成器的展优解 1 1 l 的结果 差额特征搜索算法 差额特征最大流算法 14 8 04 8 0柏0 4 8 0 23 0 04 2 03 0 0 3 9 0 309 0 0 6 0 0 7 2 0 44 8 01 1 7 08 1 0 7 8 0 54 8 04 8 04 8 0 4 8 0 * 64 2 04 2 04 2 0 4 8 0 7 2 7 0 6 3 02 7 0 3 9 0 81 5 01 8 01 s o l 92 2 51 s o 2 5 5 1 03 5 1 03 4 5 0 1 13 03 03 0 3 0 1 2 9 0 9 0 9 0 + 1 3 1 0 51 1 0 5 1 0 5 1 41 9 63 9 07 0 5 2 5 5 1 5 1 1 8 01 8 0 1 8 0 1 82 2 53 7 52 2 s 3 4 5 1 75 4 0 1 1 1 09 3 0 6 9 0 1 8 7 2 07 2 07 2 0 7 2 0 1 91 1 9 5 2