（计算机软件与理论专业论文）以工作量均衡为求解目标的项目分派问题的研究.pdf

以工作量均衡为求解目标的项目分派问题的研究摘要 论文题目：以工作量均衡为求解目标的项目分派问题的研究 专业：计算机软件与理论 硕士生：梁志荣 指导老师：郭嵩山教授 摘要 本文从全球其中一家最大的玩具公司研发部门生产实践的需求出发，研究了 一个以工作量均衡为求解目标的项目分派问题。具体来说，有若干个项目，这些 项目具有特定的生产周期，并需要分派给相应的工程师。每个项目能且只能由一 个工程师负责，但每个工程师可以同时负责若干个不同的项目。项目在启动之后， 不允许对其进行重新分派。在每个单位时间，每个工程师的工作量都具有一个上 限。问题求解的是在整个生产计划周期中，每个工程师在每个单位时间都满足工 作量上限要求的前提下，工程师之间的总工作量尽可能地达到均衡。工作量的均 衡性以工程师在整个生产周期总工作量的最大值和最小值的差作为度量标准。 本文所研究的问题在相关文献资料中尚未有相应的研究成果。通过对三划分 问题进行归约，本文证明了这个问题的求解具有强n p 难的计算复杂性，并进一 步证明了，即使是求解一个可行的分派方案，也具有强n p 难的计算复杂性。因 此，在给出了问题的整数规划模型之后，本文提出了一个基于迭代求解子问题的 启发式算法框架。算法的第一个阶段先通过应用第一适合、最佳适合和局部调整 算法，求解满足要求的可行分派方案。在求出可行分派方案之后，算法的第二个 阶段通过应用动态规划算法和分支限界算法，对子问题的均衡性进一步进行优化， 从而提高整个分派方案的均衡性。大量实验数据的测试结果表明，本文所提出的 启发式算法对所有的数据均能求得最优解或者近似最优解，这些求解结果要远好 于著名商用求解器i b m 公司的i l o gc p l e x c 埘本问题的整数规划模型进行求解 的所得的结果。本文的最后对实验结果和算法有效性进行了分析。 关键字：分派问题、工作量均衡、分支限界、启发式算法 o h t t p j w w w - 0 1 i b m c o m s o f l w a r e i n t e g r a t i o n o p t i m i z a t i o n e p l e x l 以1 二作量均衡为求解目标的项目分派问题的研究 t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： r e s e a r c ho np r o j e c ta s s i g n m e n tp r o b l e mw i t ht h eo b j e c t i v eo f b a l a n c i n gw o r k l o a d c o m p u t e rs o f t w a r e & t h e o r y z h i r o n gl i a n g p r o f e s s o rs o n g s h a ng u o a bs t r a c t m o t i v a t e db yt h ep r a c t i c eo ft h er & d d e p a r t m e n to fo n eo ft h el a r g e s tt o y sf i r m s i nt h ew o r d ，i nt h i sp a p e r , w es t u d ya p r o j e c ta s s i g n m e n tp r o b l e mw i t ht h eo b j e c t i v eo f b a l a n c i n gw o r k l o a d t ob em o r es p e c i f i c ，t h e r ea r eas e to fp r o j e c t s ，w h i c hh a v e d i f f e r e n c ed e v e l o p m e n tc y c l e s t h e s ep r o j e c t sn e e dt ob ea s s i g n e dt oe n g i n e e r ss u c h t h a t , e a c hp r o j e c ts h o u l db ea s s i g n e dt oo n ea n do n l yo n ee n g i n e e lw h i l eo n ee n g i n e e r c a nb ea s s i g n e d 诵t l l m u l t i p l ep r o j e c t s t h ep r o j e c t s ，o n c es t a r t e d ，c a nn o tb e r e a s s i g n e d a l s o ，t h e r e saw o r k l o a dl i m i t a t i o ni ne v e r yw o r k i n gt i m eu n i t so fa l lt h e e n g i n e e r s t h ep r o b l e mi st of i n dap r o j e c ta s s i g n m e n tw i t l lt h em o s tb a l a n c e d w o r k l o a d ，w h i l es a t i s f y i n gt h ew o r k l o a dl i m i t a t i o no fe a c ht i m eu n i to fa l lt h e e n g i n e e r s t h ew o r k l o a db a l a n c e i sm e a s t t r e db yt h ed i f f e r e n c eb e t w e e nt h em a x i m u m a n dt h ei n i n i m u n lt o t a lw o r k l o a do fa ht h ee n g i n e e r s t h ep r o b l e mw es t u d yi n t h i sp a p e ri sn e wt ot h el i t e r a t u r e b yr e d u c i n gt h e 3 - p a r t i t i o n i n gp r o b l e m ，w ep r o v et h a tt h ep r o b l e mi ss t r o n g l yn p - h a r d f u r t h e rm o r e ， w ep r o v et h a te v e nt of i n daf e a s i b l ea s s i g n m e n ti s s t r o n g l yn p h a r d s oa r e r f o r m u l a t i n gt h ep r o b l e mi n t oa ni n t e g e rp r o g r a m m i n gm o d e l ，w ep r o p o s e dah e u r i s t i c a l g o r i t h mf r a m e w o r kb a s e di ns o l v i n gs u b p r o b l e m si t e r a t i v e l yt os o l v et h i sp r o b l e m i nt h ef i r s ts t a g eo ft h ef r a m e w o r kw eu s et h ef i r s t f i t ，b e s t f i ta n dal o c a la d j u s t m e n t a l g o r i t h mt of m d f e a s i b l ea s s i g n m e n t so ft h ep r o b l e m i nt h es e c o n ds t a g e ，w eu s ea d y r n a n i cp r o g r a m m i n ga l g o r i t h ma n d ab r a n c h & b o u n da l g o r i t h mt os o l v e s u b p r o b l e m s ，w h i c hl c a d t om o r eb a l a n c e da s s i g n m e n t s e x t e n s i v en u m e r i c a l e x p e r i m e n t ss h o wt h a tt h ep r o p o s e da p p r o a c hc a na c h i e v eo p t i m a lo rn e a r l yo p t i m a l s o l u t i o n sf o ra l lt e s tc a s e s ；s u c hr e s u l ti sm u c hb e t t e rt h a tw h a tc a l lb eo b t a i n e df r o m a l li pm o d e ls o l v e dw i t hi b mi l o gc p l e x a na n a l y s i sf o rt h ea l g o r i t h m sa n d e x p e r i m e n tr e s u l t sh a sa l s ob e e np r o v i d e di nt h el a s ts e c t i o no ft h i sp a p e r k e yw o r d s ：a s s i g n m e n tp r o b l e m ，w o r k l o a db a l a n c i n g ，b r a n c ha n db o u n d ，h e u r i s t i c a l g o r i t h m l n 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：垫! 旦笙鱼旦呈旦 学位论文使用授权说明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其它方法保存学位论文。 学位论文作者签名：猕 日期：加l o 年6 月2 日 翩虢苛妒 日期：勿p 年月y e l 以工作量均衡为求解目标的项目分派问题的研究第1 章绪论 1 1问题背景 第1 章绪论 在日常生活和生产工作中，我们经常要对各种各样的资源进行合理的配置。 无论是个人每天时间的安排、出行路线的选择，还是企业生产巾人员的调配、项 目的分派等等，都需要依据具体的情况，进行一个合理的安排，这样才能达到资 源的最优化利用，提高个人和企业的生产效益。 分派问题( a s s i g n m e n tp r o b l e m ，简称a p ，也称为指派问题、分配问题) 最 早是由h w k u t m 在1 9 5 5 年提出的i l 】，作为组合最优化 2 1 领域中的一个基础性 的问题之一，它研究的就是这样一类资源调度和配置最优化相关的问题。根据不 同的实际问题的而提出的各种约束条件，使得分派问题衍生出许多不同的分支和 变种【”。 在本文中，主要研究的是一个以工作量均衡为求解目标的项目分派问题。简 单来说，就是对于一些在某个特定的计划周期里要求完成的项目，需要分派给不 同的工程师来负责这些项目的整个生产的流程。每个项目都有特定的启动时间以 及完成期限，而且根据项目的特殊性，不同的项目具有不同的工作阶段，每个阶 段的工作量起伏各有特点。一个项目能且只能分派个一个工程师，但一个工程师 可以同时负责多个项目，而且在项目启动之后，并不允许随意进行重新分派。问 题的求解目标是要求这样一种分派方案，使得每个工程师在单位时间工作量满足 一定合理要求的前提下，每个工程师的总工作量达到尽可能的均衡。 本文研究的问题来源于企业的实际生产需求，问题提出的背景是一家在香港 设有研发机构的玩具公司的生产实践。作为其中一家全球最大的玩具设计和生产 制造厂商，其全球生产布局模式是：总部位于美国，而产品的研发和设计机构设 立在香港，产品的生产制造则通过外包，由中国内地众多的玩具生产厂家具体负 责，生产出来的产品销往世界各地。因此，位于香港的研发机构的工程师需要监 控所负责产品的整个生产流程，也就是这些项目的具体负责人。 通常情况下，该公司每年将会接到数以百计的各种各样的玩具生产的订单， 这些订单细分为单个产品之后，就需要分派给研发机构中的工程师对每个产品的 以t 作量均衡为求解目标的项目分派问题的研究 第1 章绪论 生产流程进行具体负责。本文研究的主要问题就是如何分派这些产品给位于研发 机构的工程师，以达到最佳的企业效益。 一般来说，该公司收到的订单可以分为常规性订单、季节性订单、趋势性订 单和突发性订单等。由于常规性订单和季节性订单占据相当的百分比，而且具有 比较高的稳定性，至于趋势性订单和突发性订单，则可以根据历史经验数据结合 合理的数学预测模型，对其进行较为精确的分析和预测，所以该公司具有一定的 缓冲时间来对这些订单进行预处理。订单中包含的信息有：需要的是什么产品， 产品的数量，产品交付的日期，以及发货的目地址等等。在产品具体需求确定下 来之后，接下来的各项工作流程主要有： 1 原材料和产品组件等供应商的选择； 2 产品原型的设计； 3 产品生产相关模具的设计制造； 4 产品试验样本的测试； 5 产品成品的检验： 6 产品成品的交付和配送。 所有这些产品的上述各项具体的流程都需要由研发机构的工程师作为总负 责人，进行全面监管和跟踪负责。 公司可以根据产品的特点将产品分为新产品、现有产品和需要更新的产品三 大类型，同时根据订单和各项产品的属性，可以将产品整个生产过程中每个单位 时间( 以一个星期作为一个工作时间单位) 的工作量进行严格的量化。对于新产 品而言，负责该产品的工程师需要全程跟进产品的各项流程，付出的工作量自然 是最大的。而相对地，对于现有的产品，由于已经具备相当成熟的供应商和o e m 厂商，工作量需求相对最低。需要更新的产品根据订单的需求，负责该产品的工 程师在每个单位时间需要的工作量处于两者之间。 不同类型的产品，具有不同的生产周期。例如现有产品就不需要产品原型设 计和相关模具制造这两个流程，而需要更新的产品虽然也有这两个工作流程，但 在这两个流程中负责的工程师的工作量具有明显的差别：需要更新的产品的工作 量只有新产品的一半左右。 对于同一个产品而言，在其上述六个生产流程中，各个流程间的工作量也是 2 以工作量均衡为求解目标的项目分派问题的研究第i 章绪论 不一样的。例如对新产品而言，原材料和组件等供应商的选择和产品原型的设计 这两个阶段流程需要工程师满负荷地工作；相对来说，处理产品试验样本的测试 和产品交付和配送这两个阶段流程的时候，工程师需要的工作量就比较少。因此， 在实际生产中，基本上每个工程师可以同时负责若干几个产品。三大类型的产品 在其六个工作流程的工作量可以大致用图1 1 表示。 图1 1 不同类型的产品在各个流程的工作量 在下面的讨论中，本文将用“项目”指代这些需要工程师全程负责其整个生产 流程的产品。 由于项目的复杂性，如何将这些数以百计的项目分派给公司里面数十个工程 师就成为了该公司主管们最为头疼的问题之一。现存的分派方式主要由人工协调 为主。随着公司规模的日渐扩大，产品订单的增长，由于这些项目分派不合理所 产生的问题就越来越凸显了。这些问题概括起来说主要有两个方面。首先第一个 问题是，不同的工程师之间的总工作量并不均衡，某些工程师总是需要加班加点 才能勉强完成工作，而少数的一些工程师却大部分时间都十分空闲。公平性的缺 失感使得工程师之间的凝聚力大为减弱，公司总管们要经常进行协调工作来安抚 工程师们的情绪，避免出现罢工的情况发生。第二个问题是，对于每个工程师而 言，他们在工作周期中的工作量起伏太大了。经常的情况是在某几周里面需要通 宵达旦地工作，而接下来的几周工作量却少的可怜。这种情况让工程师们觉得工 作上的安排十分不合理和不可接受，他们强烈要求一个更合理的分派方案，使得 自己的可以有一个更健康合理的工作安排。 对于公司而言，现存的分派方案除了引起工程师的上述不满外，更严重的问 3 以t 作量均衡为求解目标的项日分派问题的研究 第l 章绪论 题是，由于工程师工作量安排的不合理，超时工作的工程师们难免出现精力不足、 判断力下降等问题，因而在工作中出现各种各样的差错的概率增高，使得产品出 现延期交付乃至因产生设计缺陷而引发安全问题。由于产品延期交付需要支付的 违约金，以及由于产品设计缺陷引起的安全问题而引发的大规模产品召回，在 2 0 0 8 年一年内就给公司造成数以百万美元计算的损失，以及不可挽回的的企业声 誉的损失。 因此，寻求一个最优的项目分派方案对公司而言显得十分重要。同时，这个 问题在现实生活中是十分常见的，几乎所有的生产企业都需要处理这样一类具有 特定的开始时间和结束时间，在整个生产流程中的不同阶段具有不同的工作量的 项目；在规模足够人的公司里面，如何最优化分派这些项目给工程师就显得十分 关键，因为一个优化的分派方案可以给企业带来明显的经济效益，同时避免不必 要的损失。本文研究的就是如何解决这样一个项目分派的问题。 1 2 相关问题的研究综述 本文所研究的问题作为分派问题的一个变种，和分派问题以及其分支和变种 等相关问题有着极为紧密的联系。具体来说，和本文所研究问题相关的主要文献 可以分为以下这几类。 第一类称为广义分派问题( g e n e r a l i z e d a s s i g n m e n tp r o b l e m ，简称g a p ) ，最 早由r o s sg t 和s o l a n dr m 在1 9 7 5 年提出【4 j 。作为一个有着众多实际应用例 子的组合最优化问题，g a p 所研究的问题可以简单描述如下： 将个工作分派给m 个处理器来完成，每个工作只能分派给一个处理器， 而每个处理器可以处理多个工作，这里一般要求m 。每个处理器f 具有一定 的资源限制6 f ，每个被分派给处理器f 的工作会消耗这个处理器一定的资源吒， 同时会产生一定的费用c f f 。g a p 求解的是这样一个最优化的分派方案，它使得 在不超过处理器资源限制的前提下，所产生的费用值之和最少【5 1 。我们可以用一 个值为0 或l 的整数决策变量x f ，表示工作是否分派给处理器，那么g a p 的整 数规划模型可以表述如下： 4 以工作量均衡为求解目标的项目分派问题的研究第l 章绪论 求解目标： 约束条件： r a i ny 跫= a 翠l c q x f y 于= i r ( j x 0 6 i ，i = 1 一，m 翟1 两= 1 ，j = 1 一，n ( 1 2 ) ( 1 3 ) x u ( o ，1 ) ，v i ，j ( 1 - 4 ) 在上述模型中，公式1 1 表示求解目标为总费用的最小化；公式1 - 2 表示分 派给每个处理器f 的所有的工作所消耗的资源不能超过这个处理器f 的资源限制 b i ；公式1 3 表示每个工作，只能且必须分派给一个处理器进行处理；公式l _ 4 表示整数变量- - x i f 的取值范围只能是0 或l ：如果第，个工作分派给第f 个处理器 进行处理，那么旎，的值就为l ，否则就为0 。很明显，所有旄f 的一组合理取值对 应一个合理的分派方案，在所有的这些合理分派方案中使得公式1 1 的值最少的 一个方案便是g a p 的解。 作为其中一个组合最优化领域的基础性问题，学术界对g a p 问题有着极为 深入的研究，并提出了很多极具针对性的求解算法。例如j u a na d i a z 和e l e n a f e r n a n d e z 两人【6 1 在2 0 0 1 年提出的带启发式算法的禁忌搜索算法，s a l i mh a d d a d i 和h a c e n eo u z i a 两人【7 1 在2 0 0 4 年提出的高效启发式算法，m a f i aa l b a r e d a - s a m b o l a 等人【8 】在2 0 0 6 年提出的针对一类难解的g a p 的求解精确解的算法，以及vj e e r 和e k u t a n o g l u 两人1 9 】在2 0 0 7 年提出的基于拉格朗日松弛的启发式算法，等等。 在所有这些求解算法中，目前求解g a p 问题最有效的方法是由m u t s u n o r iy a g i u r a 等人f l o 】在2 0 0 6 年提出的。其算法的基本思想是的基于路径重新连接以及发射 链【1 2 】的禁忌搜索。对于当前公认作为评测g a p 求解算法标准的所有4 个类型的 全部基准测试数据，该算法均能取得十分优异的结果，其求解结果已经在一个合 理的时间内达到或者十分接近最优解。 本文所研究的问题和g a p 在两个方面上有明显的区别。首先第一个，在本 文所研究的问题中，项目的工作量呈在一个离散的时间轴上连续分布的状态，而 且工作量根据项目的特性具有不同的随时间起伏的特点，而在g a p 中只有一个 以工作量均衡为求解目标的项目分派问题的研究 第l 章绪论 对应的量，也就是消耗的资源量。第二个是，本文所研究的问题的求解目标是工 程师之间总工作量的均衡，而不是所产生的费用最少。 然而在g a p 问题的变种中，f r a n z ，l 和m i l l e r , j 所研究的问趔b 】也涉及到任 务呈在一个离散的时间轴上分布的状态，不过在他们所研究的问题里面，每个需 要在时间轴上完的任务只会占一个单位时间，而不是本文中所设定的那样，会在 时间轴上连续延续若干个单位时间。另外，s m a r t e l l o 等人1 1 4 1 以及d u i nc 等人【1 5 】 所研究的均衡最优化问题，都涉及了以工作量均衡作为求解的目标。然而在他们 的研究中，并没有涉及任务的工作量在一个时间轴上连续分布的特点，和本文的 研究具有较大的差别。 第二类和本文的研究相关的问题是并行机排序问题f 1 6 1 ( p a r a l l e lm a c h i n e s c h e d u l i n gp r o b l e m ，简称p m s p ) ，也称为并行机调度问题。在这个问题中，有 若干个需要被处理的工作以及若干个并行机器，每个工作有一个特定的开始时间 和必须完成的期限，这些工作需要被分派给这些并行机器来处理，每台机器在相 同的时间只能处理一个工作，但不同的机器可以同时处理不同的工作。这类问题 的根据约束条件和求解目标的不同，文献相当对较多，参考文献【1 7 】给出了 m o k o t o f fe 撰写的到2 0 0 1 年为止，学术界对这个问题的研究情况的一个综述。 在最近几年中，由于各种各样实际问题的驱动，学术界对这个问题的研究依然十 分活跃。 例如l i a o 和s h e e n 等人【1 8 】的研究，他们考虑了在实际的工作环境下，处理工 作的机器具有宕机的可能：例如机器故障、偶然掉电等等，以及考虑了在现实世 界中不同的机器应该具有不同的处理能力。受这两个实际情况的启发，他们研究 了一个考虑了机器的有效性和适合性的，以最后完成时间的最小化为求解目标的 并行机器调度问题，并提出了一个结合了若干直接选择规则的，基于分支限界 ( b r a n c ha n db o u n d ) 算法【1 9 1 的求解方案对这个问题进行有效的求解。 d e l l ，a m i c o 等人f 2 0 】提出了一个求解p m s p 问题的基于经典的分散式搜索【2 1 】 ( s c a t t e rs e a r c h ) 的元启发式算法，以及一个精确求解算法，求解目标同样为最 后完成时间的最小化。他们通过大量的基准测试数据对这两个算法进行了测试和 对比。实验结果表明，他们所提出的元启发式算法对现行的所有p m s p 的基准测 试数据均能达到一个相当好的求解效果，而对于小规模的数据，他们提出的基于 6 以工作量均衡为求解日标的项目分派问题的研究第1 章绪论 二分搜索以及分支定价1 2 2 ( b r a n c h a n d p r i c e ) 的精确求解算法能在短时间内求出 最优解。 除上述这些文献之外，p m s p 问题最近研究文献还有：以最小化工作被提前 和或推迟为求解目标的“等人f 2 3 1 和f e n g 、l a u 等人f 2 4 】的研究文献；以总加工时 间最小化为求解目标的m e l l o u l i 等人【2 5 1 的研究文献；等等。综上所述，对比本文 所研究问题的特点，目前p m s p 问题的研究分支中，和本文所研究的问题还是具 有明显的差别。 第三类和本文的研究相关的问题是人力资源调度问题【2 6 2 7 2 8 捌。在这类问题 中，通常都会有一系列按时间顺序安排的任务，每个任务需要一定的人力资源， 例如工作的人数，工作人员的技能要求等等。问题需要求解一个合理的人员安排， 使得在这些任务可以完成的前提下，所需要用到的费用最小化。虽然限制条件和 求解目标各不相同，但这些问题都可以看做是g a p 问题的特殊例子，并和本文 所研究的问题在限制条件和求解目标上有所区别。 综上所述，本文所研究的问题在现有的相关文献中并没有完全相同的研究成 果。本文所研究问题的重点在于求解总工作量的均衡，这个求解目标相对来说在 相关文献中较为不常见；特别地，在本文所研究的问题中，工程师的工作量设定 为在一个离散的时间轴上连续分布，这个设定在我们所查阅的文献中并没有相同 的设定或相关的研究成果。 1 3 本文的主要贡献和章节安排 本文从企业生产的实际需求出发，研究了一个以工作量均衡为求解目标的项 目分派问题。本文的主要贡献有以下几点： 1 提出问题并建立了这个问题的整数规划模型； 2 证明了本文所提出的问题具有强n p 难的计算复杂性； 3 针对问题的特点，设计了一个高效的启发式算法，并通过实验分析了算 法的合理性和高效性。 本文一共分为6 章，下面是这些章节具体安排的简单介绍。 第l 章即本章为绪论。这一章主要介绍了问题提出的背景，对相关问题的研 究文献进行了一个综述，并通过对比现有的文献，说明了本文所研究问题的新颖 7 以工作量均衡为求解目标的项目分派问题的研究 第1 章绪论 性。 第2 章为问题的描述。在这一章中主要给出问题的整数规划模型，并证明了 本文所提出的问题具有强n p 难的计算复杂性，同时证明了甚至只是求解本文提 出的项目分派问题的一个可行解，也具有强n p 难的计算复杂性。因而，我们得 出本文所研究的问题在目前情况下只适用于启发式算法进行求解的结论。 第3 章为求可行解算法的设计。在这一章巾，我们首先讨论了问题的一个关 键参数的下界估算方法，接着提出了具有针对性的求解公式和优化算法对这个参 数的下界进行估算。接下来，我们针对问题的特点，通过两个普遍适用的启发式 算法的应用，以及设计了一个有针对性的启发式算法，对本文所提出的问题的可 行解的进行了求解，并对这些算法进行了深入的分析。 第4 章为优化均衡性及整体算法框架。在这一章中，针对本文所提出的问题， 在求出可行解的基础上，本文分别有针对性地提出基于动态规划和分支限界的启 发式算法求解子问题，并通过子问题的迭代求解，进而迫近问题的最优解。本章 的最后对本文所提出的以均衡性为求解目标的项目分派问题的整个求解算法框 架进行了总结。 第5 章为实验设计和算法分析。这一章首先讨论t n 试数据的设计，并通过 大量的测试数据，和世界领先的i b m 公司的整数规划求解器i l o gc p l e x 的求 解结果进行对比，充分说明本文所设计的求解算法的高效性。接下来，第5 章的 通过数据的分析，论证了本文所提出的全部算法的合理性和必要性； 第6 章为总结和展望。通过对全文进行总结和回顾，结合实际情况，提出了 本文所研究问题的未来研究方向和相关展望。 8 以工作量均衡为求解目标的项目分派问题的研究第2 章问题描述 第2 章问题描述 本文在第一章中介绍了问题的背景。这一耄将对本文研究的问题进行更详细 的描述，并建立了这个问题的整数规划模型。然后通过对三划分问题进行归约， 进一步分析和论证了问题的计算复杂性。 2 1问题的整数规划模型 下面我们设定本文所研究的问题的相关参数和变量如下： 公司具有k 个项目，需要分派给j ，个工程师。在公司的计划周期中一共有丁 个工作周，工程师的工作量以一周为一个时间单位。对于每个项目，有一个特定 的开始时间和结束时间，项目从开始时间到结束时间中，每周均具有一个特定的 工作量，用q c 表示第k 个项目在第t 周里面的工作量( 如果，不在项目k 的工作 周期中，吼。就为0 ) 。如果在某一周中，一个工程师同时负责多个项目，那么这 个工程师这周的总工作量等于所有这些项目在这周的工作量的总和。同时，在每 个单位时间，也就是每周里面，考虑到工程师的满意度以及相关的法律要求，工 程师的累计工作量具有一个上限c 。 在本文的设定中，项目的开始时间、结束时间以及在开始到结束这个工作周 期中的工作量的变化特点，都是和项目的性质和阶段具体相关的。关于这些设定 的具体内容，请参考第一章中的相关讨论。 同时本文设定，每个工程师都可以负责任何一个项目，而且对每个项目来说， 无论由任何一个工程师来完成，其工作量也是相同的。也就是说，对于所有的工 程师来说，这些项目本质上是没有差别的，不存在某些不能胜任的项目，或者相 同的项目由不同的人完成但工作量不一样的情况。对于这个设定，本文主要考虑 了两个原因：第一个，我们分析了由生产企业提供的数据和相关描述，这些数据 和描述说明，由于研发中心的工程师并不负责生产中的具体细节，而只是负责宏 观上的监督和协调，所以不存在不能胜任的项目或者同一个项目工作量因人而异 的情况，也就是说这是一个在现实生产中合理存在的设定；第二个，不排除现实 生产中某些项目确实需要工程师具有某方面特殊的技能，例如对于高科技的电子 玩具，由一个不懂电子技术的工程师来负责可能并不适合，对于这个问题，可以 9 以工作量均衡为求解目标的项目分派闯题的研究 第2 章问题描述 通过对项目的工作量进行扩展，使其对不同的工程师具有不同的工作量进行解决。 由于这个扩展会使问题变得更为复杂，所以本文只将其列为今后的研究方向，而 不在本文中进行具体的讨论。 在本文的设定中，我们并不允许项目的重新分派，也就是说，当一个项目已 经由某个特定的工程师启动了其工作流程之后，并不允许在整个工作流程完成之 前改由其他的工程师负责这个项目。对于这个设定，本文主要考虑了以下几个方 面的原因。首先第一个是，在实际的生产实践中，工程师们需要处理各利，各样的 人际关系，需要及时地和o e m 厂商进行沟通，如果在项目进行到一半的时候改 由其他的工程师负责，那么这个新来的工程师就需要较多的时间来建立之前的人 际关系网络。第二个，工程师在项目开始之后就会积累项目的相关信息，分析项 目可能出现的情况，以及做好了必要的应对措施。如果突然更改负责人，那么这 些知识的转移需要花费一定的时间，而且可能会出现一定的误差，导致项目的质 量得不到保证。第三就是考虑到交接时间而导致的拖延，使得项目可能出现延期 交货的风险，这对公司的商业声誉和商业利益都构成严重的威胁。最后一点，如 果允许项目开始之后可以重新分派，那么本文所研究的问题就退化为只需要解决 只有一个时间点的子问题了，也就是以均衡为目标的分派问题，在文献【1 4 】中已 有相当类似的研究成果。 现在公司给出了每个项目在其生产流程中的每个单位时间所需的工作量( 这 些工作量具有十分规范的衡量标准) ，他们需要的就是一个最优化的项目分派方 案，使得在满足上述的设定的前提下，每个工程师的总工作量可以达到尽可能的 均衡。设总工作量最大的工程师的工作量为u 总工作量最小的工程师的工作量 为三，那么项目分派结果的工作量均衡程度可以用u 和三之间的差值来衡量，也 就是u l 。 在本节第一段中我们提到，在每个单位时间，工程师的累计工作量具有一个 上限c 。显然，如果c 过小，问题很可能找不到一个可行解，即满足所有设定的 一个分派方案，这种情况说明问题的解空间十分狭小，因而导致最终求解的质量 相对较差；如果c 足够大，那么任意一个分派方案都可以满足单位时间工作量 这个限制，问题的解空间就相对较大，因而求解的结果会相对好得多。因此，不 同的c 的值在很大程度上影响着求解问题的困难程度以及求解结果的好坏：c 1 0 以工作量均衡为求解目标的项日分派目题的研究第2 章问题描述 值越大，问题越容易，求解结果越均衡。总工作量的均衡程度用工程师们最大的 总工作量和最小的总工作量的差值进行定义。因此，公司可以根据不同的c 值 设定下求解出来的最优结果中进行权衡选择：如果选择单位时间工作量较高，可 能引起工程师的不满意以及需要付出比较多的加班薪酬，但可以很好地满足分派 的公平性要求，也就是每个工程师的总工作量较为均衡；如果选择单位时间工作 量较低，这就意味着公平性的缺失，因为工程师之间的总工作量的均衡程度相对 较低，但可以减少工程师单位时间的工作负荷。单位时间工作量上限和总工作量 的均衡程度之间的关系可以用图2 1 进行大致的描述。总工作量均衡度的值越小， 表示越均衡。 、黼蘸 单位时间工作 量大，但总工 作量较为均衡 总 弋f _ 工 作 骨 里 均 衡 度 ， 0 单位时间工作量上限c 图2 1 单位时间工作量上限和总工作量的均衡程度之间的关系 如何选择一个合理c 值，那就需要公司的决策者们通过求解结果进行分析比 较之后权衡了。在本文第5 章实验结果分析中，我们可以看到c 值的设定对结 果的影响。 下面我们对本文所研究的问题建立一个整数规划的模型。首先本文定义一些 符号如下，这些符号在本文后面的章节中将会被引用到： f ：工程师的下标，f = l 一j o ，：工作周的下标，r = 1 ，l 缸项目的下标，k - _ l ，k 。 c k c ：表示项目k 在第t 周的工作量，这里七；1 ，= l ，死如果项目k 的开始工作周为第a 周，结束工作周为第b 周，那么对于所有的，= l ， 2 ，口一j ，b + l ，t ，有20 ， c ： 每个工程师在每周里面的工作量上限。 以工作量均衡为求解目标的项目分派问题的研究 第2 章问题描述 然后本文定义决策变量如下： x 政：如果项目k 被分派给工程师f ，那么这个决策变量的值就为1 ，否则为0 ， 这里有f = l ，山七= l ，。 阢 所有工程师总工作量的最大值。 三：所有工程师总工作量的最小值。 那么，本文所研究的问题的整数规模模型可以表述如下： 求解目标： m i n ( u l ) ( 2 一1 ) 约束条件： 以l 0 x i k ( 0 ，1 ) ，v f j k ；：1 确七= 1 ，k = 1 ，k 乙1 艇1c k c x 讹，f = 1 一，j z 1 艇1c k x 汝lf - 1 ，1 艇l c k c x 玻c ，f = 1 ，；t = 1 ，t ( 2 - 2 ) ( 2 - 3 ) ( 2 4 ) ( 2 5 ) ( 2 - 6 ) ( 2 7 ) 在上述模型中，公式2 1 表示问题的求解目标是弘的最小化，也就是工作 量的均衡；公式2 2 表示u 和三的取值必须大于或等于o ，原因是这两个变量所 代表的实际意思，也就是总工作量不能为负数；公式2 3 表示决策变量施七只能取 0 或者1 的值；公式2 4 表示每个项目只能分派给一个工程师，并且必须分派给 一个工程师来负责；公式2 5 表示u 为所有工程师的总工作量的最大值；公式 2 - 6 表示三为所有工程师的总工作量的最小值；公式2 7 表示在每个工程师的每 一个单位时间，其工作量的累计值不能大于c 。很明显，一组符合2 2 到2 7 要 求的z 次的取值就是本文所研究的问题的一个可行解：而在所有的这些可行解中， 可以让公式2 1 取值最小的一个分派方案，就是本文所研究问题的最优解。在本 文的第三章和第四章中，本文将详细讨论如何求解本问题的可行分派方案和最优 分派方案。 1 2 以工作量均衡为求解目标的项目分派问题的研究第2 章问题描述 2 2 问题的计算复杂性分析 在讨论本文所研究的问题的计算复杂性之前，本文在这里先简单介绍一个著 名的难解问题：三划分问题。 三划分问题求解的是对于一个大小为的正整数多重集合( 也就是说在这个 集合中可能有相同的元素) ，是否存在一种划分方法，可以将这个集合划分为n 3 个不相交的子集，并使得这些子集的数字和都相等的问题。更精确一点来说，给 定一个大小为n = 3 m 的整数多重集a = w i ，f = 1 ，) ，并且这个集合的数字和 为m * b ，问能否将这个集合彳划分为m 个不相交的子集两，& ，品，使得 每个子集的数字和都是b 。三划分问题是一个著名的强n p 完全问题，g a r e y 和 j o h n s o n 最早在1 9 7 5 年【3 0 1 通过对三维匹配问题的归约，证明了三划分问题的时 间复杂性是强n p 完全的。 根据s t e p h e na c o o k 在1 9 7 1 年【3 l 】提出的n p 完全性理论，下面本文尝试通 过三划分问题进行对本文所研究问题的归约，证明本文所研究的问题具有强n p 难的计算复杂性，以及求本文所研究的项目分派问题的一个可行解的计算复杂性 也是强n p 难的【3 2 1 。 命题2 1 ：本文所研究的以工作量均衡为求解目标的项目分派问题的计算复 杂性是强n p 难的。 证明如下： 首先，由于本文所研究的以工作量均衡为求解目标的项目分派问题是最优化 问题，而不是判定问题，因此，本文所研究的以工作量均衡为求解目标的项目分 派问题不是n p 问题。 接着，对于三划分问题，我们可以构造一个和其等价的以工作量均衡为求解 目标的项目分派问题： 有个项目，每个项目的开始和结束时间都是第一周，同时第f 个项目在第 一周的工作量为w f ，每个工程师在第一周里面的总工作量上限为无穷大。现在需 要将这n = 3 m 个项目分派给m 个工程师，每个项目能且只能分派给一个工程师， 求解工作量最为均衡的分派方案，也就是这些工程师的最大总工作量和最小总工 作量的差的最小值。 如果上述的项目分派问题可以求解，那么很明显，可以通过求解结果是否为 1 3 以t 作量均衡为求解目标的项目分派问题的研究 第2 章问题描述 零来判断原来的三划分问题是否成立：如果求解结果为零，那么对应的分派方案 就是三划分问题的一个对应划分；如果求解结果非零，那么原来的三划分问题就 不存在一个满足要求的划分。也就是说，我们证明了三划分问题只是本文所研究 的以工作量均衡为求解目标的项目分派问题的一个特例。 在上述的归约过程中，由于只需要将三划分问题中相应的量对应到本文研究 的问题的一个特例上，其归约过程的计算时间复杂性是多项式级别的。也就是说， 通过构造本文所研究问题的一个特例，我们证明了：三划分问题可以在多项式时 间内归约到本文所研究的项目分派问题。 因此，根据n p 完全性理论，命题2 1 得证。 下面我们进一步讨论，如果只是求解一个满足本章2 1 节中所述的整数规划 模型中的约束条件2 2 到2 7 的项目分派问题的一个可行解，其计算复杂性也是 强n p 难的。 命题2 2 ：求解本文所研究的项目分配问题的一个可行解的计算复杂性是强 n p 难的。 证明如下： 首先，由于现在问题所求的是一个可行的分派方案，而不是判定是否存在一 个可行解，所以求本文所研究的项目分派问题可行解的问题也不是n p 问题。 同样地，我们可以通过构造求解本文所研究的问题一个可行解的另一个特例， 来对三划分问题进行归约。构造的特例如下： 有n 个项目，每个项目的开始和结束时间都是第一周，同时第i 个项目在第 l 周的工作量为w i 。现在需要将这n = 3 m 个项目分派给m 个工程师，每个工程 师在第一周里面的总工作量上限为b ，每个项目能且只能分派给一个工程师，现 在求解是否存在这样一个可行的分派方案，可以满足上述关于第一周工作量上限 等要求。 如果上述项目分派问题的可行分派方案是存在的，那么很明显原来的三划分 问题的划分方案也是存在的，也就是说三划分问题是本文所研究问题是否存在可 行解的一个特例。同样地，由于归约过程是多项式时间复杂度的，我们有：三划 分问题可以在多项式时间内归约到求解本文所研究的项目分派问题的可行解的 问题上。 1 4 以工作量均衡为求解目标的项目分派闻题的研究第2 章阀题描述 因此，根据n p 完全性理论，我们有：求解本文所研究的项目分派问题的可 行解是强n p 难的。 因此，命题2 2 得证。 由于本文所研究问题具有强n p 难的计算复杂性，同时由于即使是求解木文 所研究的项目分派问题的一个可行解，其计算复杂性也是n p 难的。因此，本文 在接下来的第3 和第4 章中主要研究了应用启发式算法对这两个问题其进行求解。 2 3 本章小结 本章的第一节讨论了本文所研究问题的相关设定，并通过严谨的数学描述， 给出了一个适用于类似i b m 公司的i l o gc p l e x 等通用整数规划求解器求解的 整数规划模型。 在本章的第二节，本文通过对三划分问题的归约，证明了本文所研究的问题 具有强n p 难的计算复杂性，并进