以工作量均衡为解目标的项目分派问题的研究.pdf

以工作量均衡为求解目标的项目分派问题的研究 摘要 论文题目：以工作量均衡为求解目标的项目分派问题的研究 专 业：计算机软件与理论 硕士生：梁志荣 指导老师：郭嵩山教授 摘 要 本文从全球其中一家最大的玩具公司研发部门生产实践的需求出发，研究了 一个以工作量均衡为求解目标的项目分派问题。具体来说，有若干个项目，这些 项目具有特定的生产周期，并需要分派给相应的工程师。每个项目能且只能由一 个工程师负责，但每个工程师可以同时负责若干个不同的项目。项目在启动之后， 不允许对其进行重新分派。在每个单位时间，每个工程师的工作量都具有一个上 限。问题求解的是在整个生产计划周期中，每个工程师在每个单位时间都满足工 作量上限要求的前提下，工程师之间的总工作量尽可能地达到均衡。工作量的均 衡性以工程师在整个生产周期总工作量的最大值和最小值的差作为度量标准。 本文所研究的问题在相关文献资料中尚未有相应的研究成果。通过对三划分 问题进行归约，本文证明了这个问题的求解具有强NP难的计算复杂性，并进一 步证明了，即使是求解一个可行的分派方案，也具有强NP难的计算复杂性。因 此，在给出了问题的整数规划模型之后，本文提出了一个基于迭代求解子问题的 启发式算法框架。算法的第一个阶段先通过应用第一适合、最佳适合和局部调整 算法，求解满足要求的可行分派方案。在求出可行分派方案之后，算法的第二个 阶段通过应用动态规划算法和分支限界算法，对子问题的均衡性进一步进行优化， 从而提高整个分派方案的均衡性。大量实验数据的测试结果表明，本文所提出的 启发式算法对所有的数据均能求得最优解或者近似最优解，这些求解结果要远好 于著名商用求解器IBM公司的ILOGCPLEXC埘本问题的整数规划模型进行求解 的所得的结果。本文的最后对实验结果和算法有效性进行了分析。 关键字：分派问题、工作量均衡、分支限界、启发式算法 OhttpJ／www-01．ibm．com／soflware／integration／optimization／eplex／ l 以1二作量均衡为求解目标的项目分派问题的研究 Title： Researchon Problemwiththe of Assignment Project Objective Workload Balancing Major： ComputerSoftwareTheory Name： ZhirongLiang Professor Guo Supervisor： Songshan AB STRACT the Motivated oftheRD ofoneofthe firms by practice department largesttoys inthe this a withthe word，in of paper,westudyprojectassignmentproblem objective workload．To are bemore asetof have balancing specific，there projects，which difference nee