第３４卷第１期 ２０１３年２月 江西理工大 学学报 Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｊｏｕｒｎａｌ ｏｆ Ｊｉａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｖｏ１．３４．ＮＯ．１ Ｆｅｂ．２０１３ 文章编号：２０９５—３０４６（２０１３）０１—００９０—０６ 基于多目标优化的大型项目任务分配模型 刘建生， 孙彦武 （江西理工大学理学院，江西赣州３４１０００） 摘 要：大型项目任务分配问题的多目标、多变量、多约束、大组合等特点，使得任务分配费时、费 力．文中分别以利润最大且延期较短和无延期且利润最大为目标，利用时间序列分析方法，将贪 婪算法和多目标优化问题相结合，建立两个基于多目标优化的大型项目任务分配模型．利用两个 模型分别确定某大型项目的任务分配方案，仿真结果表明：两个模型和算法均最大限度降低了大 型项目任务分配问题的时间复杂度，有效地解决了任务分配费时、费力这一问题． 关键词：大型项目；任务分配；多目标规划；时间序列分析；贪婪算法 中图分类号：０２２１．６ 文献标志码：Ａ Ｌａｒｇｅ－ｓｃａｌｅ ｐｒｏｊ一 一 ●。 ｅｃｔ ａｓｍｇｎｍｅｎｔ‘ ｍｏｄｅｌ一’■ ｂａｓｅｄ ｏｎ 一 ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ ＬＩＵ Ｊｉａｎ－ｓｈｅｎｇ，ＳＵＮ Ｙａｎ－ｗｕ （Ｆａｃｕｌｔｙ ｏｆ Ｓｃｉｅｎｃｅ，Ｊｉａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｇａｎｚｈｏｕ ３４１０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ，ｍｕｌｔｉ—ｖａｒｉａｂｌｅ，ｍｕｌｔｉ—ｃｏｎｓｔｒａｉｎｔ ａｎｄ ｌａｒｇｅ ｃｏｍｂｉｎａｔｉｏｎｓ ｏｆ ｌａｒｇｅ－ｓｃａｌｅ ｐｒｏｊｅｃｔ ａｓｓｉｇｎｍｅｎｔｓ ｍａｋｅ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ ｔｉｍｅ—ｃｏｎｓｕｍｉｎｇ ａｎｄ １ａｂＯｒｉＯＵＳ．Ｉｎ ｔｈｉｓ ａｒｔｉｃｌｅ，ｂａｓｅｄ ｏｎ ｍｕｌｔｉ一０ｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ，ｔｗｏ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ ｍｏｄｅｌｓ ｏｆ ｌａｒｇｅ—ｓｃａｌｅ ｐｒｏｊｅｃｔ ｕｓｉｎｇ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｔｉｍｅ ｓｅｒｉｅｓ ａｎａｌｙｓｉｓ ａｎｄ ｔｈｅ ｃｏｍｂｉｎａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ ａｎｄ ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ ａｒｅ ｅｓｔａｂｌｉｓｈｅｄ．Ｏｎｅ ｍｏｄｅｌ ｓｅｔｓ ｔｈｅ ｍｏｓｔ ｐｒｏｆｉｔａｂｌｅ ａｎｄ ｓｈｏｒｔｅｒ ｄｅｌａｙ ａｓ ｉｔｓ ｇｏａｌ，ａｎｄ ｔｈｅ ｏｔｈｅｒ ｓｅｔｓ ｎｏ－ｄｅｌａｙ ａｎｄ ｔｈｅ ｍａｘｉｍｕｍ ｐｒｏｆｉｔ ａｓ ｉｔｓ ｇｏａ１．Ａ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ ｏｆ ｌａｒｇｅ—ｓｃａｌｅ ｐｒｏｊｅｃｔ ｉｓ ｄｅｔｅｒｍｉｎｅｄ ｂｙ ｕｓｉｎｇ ｔｈｅｓｅ ｔｗｏ ｍｏｄｅｌｓ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅｓｅ ｍｏｄｅｌｓ ａｎｄ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ｒｅｄｕｃｅ ｔｈｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｌａｒｇｅ－ｓｃａｌｅ ｐｒｏｊｅｃｔ ａｓｓｉｇｎｍｅｎｔｓ ａｎｄ ｄｅａｌ ｗｉｔｈ ｔｈｅ ｐｒｏｂｌｅｍｓ ｏｆ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ ｂｅｉｎｇ ｔｉｍｅ——ｃｏｎｓｕｍｉｎｇ ａｎｄ ｌａｂｏｒｉｏｕｓ． Ｋｅｙ ｗｏｒｄｓ：ｌａｒｇｅ——ｓｃａｌｅ ｐｒｏｊｅｃｔ；ｔａｓｋ ａｌｌｏｃａｔｉｏｎ；ｍｕｌｔｉ——ｏｂｊｅｃｔｉｖｅ ｐｒｏｇｒａｍｍｉｎｇ；ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｔｉｍｅ ｓｅｒｉｅｓ； ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ 个良好的任务分配方案就显得非常重要【ｌ－２］．在项目 问题的提出 随着中国经济的迅速发展，大型项目工程越来 越多．项目管理研究愈来愈多的受到学术界和企业 界的高度关注，大型项目具有工期长、任务多、费用 建设过程中，通过任务分配的优化设计以实现利润 最大化系多目标规划问题．文献［３］针对任务的实 际需求，以工期、质量、以及费用作为任务分配优化 的目标函数，提出并设计了一种基于遗传算法的任 务分配模型．但是并未从时间复杂度方面人手，解 决任务分配问题；就目前而言，解决此类问题的软 高，质量要求高等特点，因而在其运营之前制定一 收稿日期：２０１２—０７—１３ 作者简介：刘建生（１９５９一），男，副教授，主要从事信息安全与智能计算等方面的研究，Ｅ－ｍａｉｌ：ｊｘｇｚｊｓｃｎ＠１２６．ｃ０ｍ． 第３４卷第１期 刘建生，等：基于多目标优化的大型项目任务分配模型 ９１ 件。能直接求解的变量个数一般在１００００个以下， 并且计算的时问复杂度随变量个数的增加成指数增长 ［４１．基于此．文中以利润最大且延期较短和无延期 且利润最大为目标，建立了基于多目标优化的两个 大型项目任务分配模型．根据运筹学的多目标规 划问题原理 ．利润最大且延期时间最短为目标函 数的任务分配模型，将利润设为第一目标，即追求 利润最大，在不改变最大利润的情况下，尽可能减 小延期时间：利润最大且无延期为目标函数的任务 分配模型，可将延期时间作为第一约束条件，在延 期时间为零情况下，尽可能使利润最大化．同时采 用时间序列分析方法，给出了基于贪婪算法的最佳 任务分配模型，应用ＭＡＴＬＡＢ编程，实现了大型项 目任务分配系统的优化设计，最大限度地降低了分 配算法的时间复杂度． 为具体说明此问题，设有Ⅳ个大型项目的任 务分配问题需要完成，每一项目由很多任务组成， 其中每一任务具有四个属性：完成任务所需技能， 任务量，任务价值，任务完成时限．同时，完成每项 任务只需ｌ项技能，工人的技能、效率、工资等信息 已知．每个任务都可以完成．为保证同一任务 能够同时进行．假设项目所需设备完善．工人工资 以计件方式计算，一个工人同一时刻只能用一项技 能进行作业，对每一项任务连续完成后，方可进行 其他任务． ２ 利润最大且延期较短模型的建立与求解 ２．１利润最大且延期较短模型的建立 项目利润为项目任务总价值与工人工资之差． 任务总价值为： Ｋ １ ｓ： ｑ ｋ＝ｌ 其中，ｑ 为ｋ任务的价值，Ｋ为任务总数，ｋ＝ｌ，２，…， ． 定义１ Ｘｌ ，…， 为 工人完成任务数量的 序列； ， ，…， 。为任务的剩余时间序列． 工人工作时使用不同技能得到的工资不同，设 定第ｉ个工人用第 种技能工作时，所得日工资为 ｃ ，日工作量为 ，则ｉ工人用 技能完成单位工作 的工资为： ＝ｃ 当ｉ工人没有 技能时 ＝０ 由于一个任务只需要使用一项技能去完成，则 工人完成第 项任务的工资为： ＰＩ ，ｘｇ． ＝１ 其中， ＝｛ 曩能， 为技能总数． 因此．工人的总工资为： ．∑∑Ｉ＝１ ｉ＝１【 ＾＝１∑ ）Ｊ１ 其中 ＝｛ ｛ ２ 警 务，Ｋ为任 务总数，Ⅳ为工人总数， 为给工人ｉ安排的任务 总数， 为ｉ工人在第ｈ顺序完成ｋ任务量，ｉ＝１， ２，…，Ｎ，ｋ＝ｌ，２，…，Ｋ，ｈ＝ｌ，２，…，Ｋ． 所以项目总利润为： Ｑ＝Ｓ一 ＝∑ ∑∑１ｋ＝１ ｋ：１ ｉ＝１【 ｐ ×∑ ：１ ）ＪＩ ＝ Ｋ ｆ Ｎ ｆ Ｍ Ｋ １ １ 一 【 ｐ × ｘ Ｊ ｊ 第ｉ个工人完成第ｋ项任务的速率为： ＝ ／ｙ ） ＝１ 由于任务分配过程中一个工人可能需要完成 多项任务，以及使用多种技能．但工人在同一时刻 只能使用一种技能去完成一项任务．所以 工人在 第ｈ顺序开始ｋ任务的时刻为完成前面 一１个任 务时间的总和。即： ＝∑∑∑ ） ＝１ ＝ｌ ｈ ：１ 其中，ｋ＝ｌ，２，…，Ｋ；ｉ＝Ｉ，２，…，Ⅳ；ｈ＇－１，２，…， 一１。 ｉ工人在第ｈ顺序完成ｋ任务的延期时间长度为： ∑ Ｘｔ龇）一 ｈ：ｌ 其中， 为完成ｋ任务的时限．ｉ工人完成ｋ任务 的延期时间为： 『Ｋｉ 【０ ， １．１ 她Ｘｔｍ）＜ ｔ／ｋ＝ｊ Ｋ ；∑ Ｘｔ ）一 ，其它 ９２ Ｋ Ｎ 江西理工大学学报 ２０１３年２月 项目总延期时间为：Ｄ ∑∑ｆ ＝１ ＝ｌ 其中， 为工人ｉ完成 任务的任务量．对该模型 变换可得： 对于一个任务，所有工人的实际完成量为 Ｎ Ｋ Ⅳ∑ Ｋ ∑，ｒＫ∑ ∑∑ ｉ＝ｌ ｈ＝ｌ ），ｋ任务的任务量为慨，实际完成 Ｎ Ｋ Ｓ．ｔ．１ｉ＝１ ≤从 【∑ ≥ ，ｋ＝ｌ ２一，Ｋ 为非负整数 ≥ ０ 量应不小于任务量，即：∑∑ ｉ＝ｌｈ＝ｌ 一）≥帆，ｋ＝１２－，…， ∑ 模型中Ｐ 为常数， 为变量，ｙ与 为线性 ＝ 个工人同一时刻只能完成一项任务，则有： Ｋ ∑ ＝１，ｉ＝１ ２一，Ｎ；ｈ＝１ ２一，Ｋ ＝１ 一个工人一项任务只能做一次，则有： Ｋ 、－弋 ≤１，ｉ＝１ ２一，Ｎ；ｋ＝ｌ ２一，Ｋ． ｈ＝１ 综上可得利润最大且延期较短的数学模型为： Ｋ ｒ Ｎ ｆ Ｋ １ １ ｍａｘ Ｑ ｊ ㈩ Ｋ Ⅳ ｍｉｎ Ｄ ∑∑ ． ｎ ｋ＝１ｉ＝１ ｙ ＝ 其中 ｔ＝ Ⅳ∑ ∑㈦ ， ∑ ｘｔ ）一 ，其它 Ｘ ｈ：１ Ｓ．ｔ．１１ ＝１∑ｆ ｉｋｈ＝１ ，ｉ＝１，２，…，Ｎ；ｈ＝ｌ，２，…Ｋ ，ｉ＝１，２，…，Ｎ；ｋ＝ｌ，２，…Ｋ 为非负整数 Ｍ，鸶 为０－１整数 分析式（１）得，价值与自变量之间为线性关系， 延期时间与任务工作顺序有关．当不考虑延期时 问的情况下，该模型可简化为： Ｋ『 Ⅳ ］ ｍａｘ Ｑ＝∑Ｉ：１【 ｇ 一∑（１ ｐ × ）Ｊ ｌ ｝∑ ≥ ， ＝１ ２一，Ｋ Ｓ． ．１ｉ＝１ 。 为非负整数 关系．当Ｘ 增大时，ｌ，增大；当 × 越 减小时，ｙ减小．２ 所以要使】，最小， 应尽量取小．另外，任务之间 × Ｋ 没有相互约束，只有任务内部有约束．对于ｋ任务有： Ｎ Ｎ ｍｉｎ ∑（ｉ＝１ ｐ ２ｘ￣ ） ．｛∑ ＝ｌｉ＝１ 。 通过分析可得，当Ｐ￣＊ｋ＝ｍｉｎ ．．，卅｛Ｐ ｝时， Ｘｉ＊ｋ＝Ｍｋ，其余都为０时，ｙ 最小，为ＰＩ％× ．单个任 务均取最小值时．总任务最小． 定义２ Ｙｔ，Ｙ２’…ｙＫ为ｉ工人每天能完成任务最 大数量的序列，｛ ， ：，…， ｝为ｉ工人完成任务 所需时间的序列， 。，ｚ ，…，ｚ 为ｉ工人完成任务的 时刻序列． ＝∑ ＝１ ２一， ； ＝１ ２一， ） Ｊ＝１ 则有： ｚ ｙｏ（天）， Ｄｒ， ＝： ∑ｍａｍａｘ — 一７ ，Ⅲｒ，ｊ００｝） ｍ：１ 假设剩余时间序列中任意相邻两个任务的剩 余时间 和 小工人完成对应任务所需时间为 Ｚ 和Ｚ ｉ工人完成对应任务时刻为 和ｚ州，此 时对于 和 ，ｉ工人对这两个任务的延期时间为： Ｄ ＝ 一 ）＋ ＋ 一 ＋。） 由于 川＝Ｚｗ＋Ｚ １，所以可得， Ｄ ＝２ｘｚ ＋ｌ＋２ 一（ ＋ ＋１） 由题设可知，无论 与 ＋ 的位置交换与否 都不影响和的值 ．因此，令：ｃ＝２ｘｚ 一（ ＋ ＋ ），ｃ 为定值．则：Ｄ ＝２ｘｚ ｌ＋ｃ．由上式可知，要使 最小，应使２ｘｚ ｌ最小，即Ｚ １． 第３４卷第１期 刘建生，等：基于多目标优化的大型项目任务分配模型 ９３ 当 工人按序列由小到大完成时，延期时间 Ｄ 最小．由于每个工人相互，项目总延期时 间与每个工人工作的延期时间成线性关系．故只 要每个工人的延期时间达到最小时，项目总延期时 间会最小．利用贪婪算法 “】，优先考虑ｉ工人完成 单位 技能的工资，算法Ｎ—Ｓ流程图如图ｌ所示． 图１利润最大且延期较短模型的算法流程图 ２．２利润最大且延期较短模型的求解 目，利用ＭＡＴＬＡＢ软件进行编程计算，计算结果如 表ｌ所示． 应用上述模型和算法，分别对５个不同的项 表１利润最大且延期较短模型的求解结果 ３ 无延期且利润最大模型的建立与求解 所以无延期且利润最大模型的为： ３．１无延期且利润最大模型的建立 要求任务分配不延期，实现利润最大化．可把 上述模型中，追求延期时间最小的目标转变为约束： ｍａｘ Ｑ＝∑＝ １ ∑ ｉ｛【 ｑ —— ： ＝ １ ×［【 ｃ ∑： １ Ｍ（￣ｉｋｈ）］¨Ｊ ）Ｊ （２） ｎｎａｘ ｃ ＝＝ 江西理工大学学报 ２０１３年２月 对上述模型以优先考虑ｉ工人完成单位 技能 的工资，运用贪婪算法，算法的Ｎ—Ｓ流程图ｍ 如 图２所示． Ⅳ 厶 ∑ ＾＝１ ，ｉ－１ ２一，Ⅳ；ｈ＝ｌ，２，…，Ｋ ３．２无延期且利润最大模型的求解 ＝ｓ．ｔ． ｌ Ｋ∑㈦ Ｋ 应用上述模型和算法，分别对５个不同的项 从 ∑（ｆ ）＜ ｈ＝１ 目，利用ＭＡＴＬＡＢ软件进行编程计算，计算结果如 Ⅳ 一１ ｈ．Ｘｕ ） 表２所示． ＾Ｉ ｔｉｋｈ＝∑∑∑ ×Ｘｉｋ＝ｌ ＝１ ｈ ：１ 表２无延期且利润最大模型的求解结果 ＝ ２ Ｋ 标注：延期时问为０，说明存在无延期且利润最大的任务分配方案 图２无延期且利润最大模型的算法流程图 第３４卷第１期 刘建生，等：基于多目标优化的大型项目任务分配模型 优化研究【Ｊ］．系统工程理论与实践，２００７（１０）：１ １３—１ １７． ９５ 如果采用传统优化方法求解本规划问题，计算 机需要搜索的次数为１００００００亿次．如果每次计算 需要约１ ｓ的时间，这样计算机完成计算需要约３ 【２】杨耀红，汪应洛．工程项目工期成本质量模糊均衡优化研究【Ｊ］． 系统工程理论与实践．２００６（７）：１ １２一ｌ１７． ［３】曾强，杨育，王小磊，等．大型工程项目任务多目标优化调度 年的时间．应用文中所提出的分配模型和算法，从 表１和表２中可看出分配项目１所需的时间只需 ５．９７０８８ Ｓ和２４８．４２５９ ｓ，大大降低了算法的时间复 方法［Ｊ］．计算机工程与应用，２０１０，４６（２４）：２１７—２２１． ［４】刘怀愚，朱昌杰，李璨．时间复杂度的几种计算方法［Ｊ］．电脑知 杂度． ４ 结语 文中提出了大型项目任务分配的两个模型． 其一以项目利润最大及延期时间较短为优化目标 建立了多目标优化模型．其二以项目利润最大及无 延期为优化目标建立了多目标优化模型．提出了 一种基于时间序列分析方法和贪婪算法的新算法 对模型进行求解。该算法结合了时间序列分析方法 及贪婪算法各自的优点．具有较好的收敛效果．实 例表明文中提出的大型项目任务分配模型是正确 和有效的，对于促进项目管理向精细化管理转变具 有重要意义． 参考文献： ［１】高兴夫，胡程顺，钟登华．工程项目管理的工期一费用一质量综合 识与技术．２０１１．７（１９）：４６３６—４６３８． 【５】黄桐城，鲍祥霖．数学规划与对策论［Ｍ］．上海：上海交通大学出 版社．２ｏ０２． 【６］支学艺，何锦龙，江小华，等．灰色关联投影法在矿井通风方案 优化中的应用［Ｊ］．江西理工大学学报，２０１０，３１（１）：１７—１９． ［７］张树京，齐立心．时间序列分析简明教程【Ｍ】．北京：清华大学出 版社．北方交通大学出版社．２００３． ［８】蔡荣英，黄健，林大辉，等．任务分配的贪婪随机自适应搜 索过程［Ｊ］．计算机工程与设计，２００６，２７（２１）：４０３６—４０３８． 【９】张治，施鹏飞．一种有效的贪婪模式匹配算法［Ｊ］．计算机研究 与发展，２００７，４４（１１）：１９０３—１９１１． 【１０】申时凯，吴绍兵，申浩如，等．计算最短公共超串的贪婪算法【ＪＪ． 计算机工程与设计，２００７（８）：３６５０—３６５２． ［１１】蒋建国，李勇，夏娜．一种求解单任务Ａｇｅｎｔ联盟生成的贪 婪算法［Ｊ］．系统仿真学报，２００８（８）：３６６—３６９． 【ｌ２】王晓东．计算机算法设计与分析［ＭＩ．３版．北京：电子工业出版 社．２００７． 【１３】Ｍａｒｋ Ａｌｌｅｎ Ｗｅｉｓｓ．数据结构与算法分析【Ｍ】．冯舜玺，译．北京： 机械工业出版社．２００４．
