基于排队论的动态多项目资源配置方法研究

黄小荣，杜百岗，戴 伟

(1湖北理工学院经济与管理学院，湖北黄石435003;2武汉理工大学机电工程学院，湖北武汉430073)

0 引言

随着制造企业的生产方式从大规模批量生产转变为大规模定制生产，表明现代制造企业的战略已经从以产品为中心转向以顾客为中心［1］。在这样的环境下，一方面，产品的多样性增加、生命周期变短;另一方面，顾客对产品的交货期、质量、成本提出了更高的要求。这些原因使得企业传统的管理方式不再有效。随着项目管理理论与应用的发展，许多企业在大规模定制生产中引入了项目管理的方法［2］，按项目对产品的售前、设计、采购、制造、售后等全过程进行管理。管理的项目化使得许多企业面临多项目管理的挑战。资源是项目执行过程中的重要组成部分，其在多项目之间的竞争与共享是多项目管理中的核心问题。如何配置资源、提高项目的执行效率以降低成本、减少工期是项目管理中的一个重要课题，即资源受限项目调度问题(Resource Constrained Project Scheduling Problem，RCPSP)，该问题研究在满足项目活动关系及资源约束的前提下，如何合理地配置资源、安排项目的各个活动，使得管理目标最优化［3］。

鉴于RCPSP 本身重要的学术意义和应用价值，学者们对其进行了大量的研究，研究内容主要集中于问题的模型和求解算法上，文献［4］对此进行了总结。由于RCPSP 的最初研究对象是工程类项目，在模型的构建上有一个重要假设即项目的静态性，项目的开工时间已知、固定，多个项目同时到达或随机到达聚集后再集中规划;对于执行过程中项目完成时间与资源的动态关系，则采用多模式方法建模［5］，而多模式不足以反映项目全过程的动态性。在大规模定制企业中，一份订单即可看作一个项目，故项目具有较强的动态性、不确定性，项目到达具有流水性以及项目之间具有关联复杂性、差异性。上述原因使得经典的RCPSP 模型的应用受到了限制。

因此，针对项目动态性的上述特点，研究动态环境下多项目资源配置方法对缩短产品交期、降低成本、提高现代制造企业的市场竞争力和经济效益具有重要的理论意义和实际应用价值。基于此，针对制造企业多项目的动态性、不确定性、随机性和流水性，本文考虑将资源看作服务台，而项目看作服务对象，建立动态多项目的排队论模型。首先对项目的到达时间及资源的服务时间进行统计，然后根据这些规律改进企业多项目的资源配置，使得资源既能满足多项目的需要，又能使费用最低或项目交期最优。

1 动态多项目资源配置问题描述

多项目并行以及项目的动态性增加了项目管理的复杂性，给现代企业的管理带来了极大的挑战，项目的动态性主要表现在以下几个方面。

1)项目资源的动态性。一般来说，项目资源的动态性包括对资源需求的动态性和资源自身的动态性。前者表现为未知项目对资源需求的不确定性和现有项目对需求描述的模糊性等。后者主要指资源故障的不确定性，一般与其固有可靠性和参与条件有关，这类不确定性往往会影响项目调度的有效性和调度性能。

2)项目执行过程中的动态性。当企业接到客户的产品需求后，采用项目管理的方式，对产品立项、建立研发小组，设计并确认后小批量试产、批量生产，最后交付，项目管理涵盖了销售、研发、采购、质量控制、制造等各个环节。项目执行过程中各环节资源工作效率的变化、各活动提前期估算不准、项目优先级临时变化等动态性因素削弱了项目按时完工的能力。

3)项目外部环境的动态性。项目外部环境的动态性是指由环境、条件、技术、工艺以及市场行情变化所引起的不确定因素。主要包括供给动态性和需求的动态性。前者来自于供应商无法满足市场需求，比如原材料供应是否充足、外协生产加工的不确定性等;后者来自于最终市场需求与客户订单之间的差距，比如取消订单或者紧急插入新订单等。

动态多项目资源配置问题可以从以下几个方面进行描述。

1)项目类别。根据产品的设计变动量可以将项目分为多类，同类项目之间的相似度高，不同类别的项目包括的任务不同。比如一个全新的产品其项目包括全部的产品研发任务，而只有某个零部件改变的产品则只包括少部分产品的研发任务。

2)项目到达速度。不同类别的项目随订单随机到达，具有普通性、有限性、平稳性和无后效性，因此可假设各类项目的到达均服从泊松分布。

3)项目任务。根据工作分解结构(Work Breakdown Structure，WBS)［6］将项目分解为工作包(Work Package，WP)，WP 即为项目任务，项目任务不可再分，具有原子性，在项目中不同的项目任务所需的资源不同，各类项目中的同类任务资源需求相同。

4)资源约束。企业满足所有项目任务的各类资源有限，所有资源总价之和有限。

5)目标。在资源有限的情况下将其合理地配置到为各项目任务服务的服务台中，优化的目标主要是项目评价工期最短、成本最低。

2 动态多项目资源配置模型

由于项目具有动态性、相似性、流水性等特点，项目随机到达，企业的资源依次为各类项目任务服务，因而可将资源看做服务台，项目看做顾客。同一类项目任务和为其服务的资源可以看做一个基本的排队系统，“项目任务－资源”构成的基本排队系统如图1所示。对于该系统，可以认为:①顾客到达服从泊松分布;②排队规则为等待制且容量无限;③至少有一个服务台，且先到先服务，服务时间无记忆性且服从负指数分布。这说明“项目任务－资源”构成的基本排队系统即为M/M/c 或M/M/1 模型，服务台数为资源的数量，项目任务的工期为平均逗留时间Ws。

图1 “项目任务－资源”构成的基本排队系统

整个项目的执行过程是由这些基本的排队系统串联或并联在一起构成了排队网络。

由文献［7］中的Burke 定理可知，在排队网络中各类项目在各节点中的到达速度与离开速度相同，均等于该类项目到达系统的速度，即均为相同参数的泊松分布。由泊松分布的可加性［8］可知，所有项目到达排队网络中某一节点的泊松分布参数为各类项目的泊松分布参数之和。由文献［9］中的Jackson 定理可知，在计算整个项目的工期时，可将“任务项目－资源”排队网络分解为各自独立的“项目任务－资源”排队系统，各排队系统平均逗留时间之和即为整个项目工期。

基于排队论的动态多项目资源配置模型建立流程，具体描述如下。

步骤1:对企业项目进行归集，根据WBS对项目任务进行分解，按照项目内任务数量对项目进行分类，根据各类项目建立网络计划图模型，并寻找出关键路径与非关键路径。

步骤2:按照统计资料确定各类项目的到达速度，即确定泊松分布参数λ，同时，根据总的网络计划图模型确定项目到达各服务台的到达速度;对服务于同一类项目任务的资源进行抽象，定义资源的服务时间、资源单位等特征，其中服务时间为服从参数μ 的负指数分布，资源单位统一可折算为费用。通过对服务台、顾客的抽象，确定“项目任务－资源”排队系统模型。

步骤3:通过各个节点排队系统与网络图模型建立排队网络模型。

步骤4:确定资源配置目标，寻找约束。资源配置的目标可以是成本最低或项目的平均完工时间最短，排队网络模型中项目的完工时间由各节点配置的服务台数量决定。约束包括资源总价约束、项目关键路径约束与非关键路径的汇入约束［10］等。

步骤5:建立动态多项目资源配置数学模型。

步骤6:对模型进行求解，若资源配置不合理则转向步骤2。

步骤7:输出资源配置计划。

综上所述，完整模型表述如下:

在该模型中，式(1)表示配置目标费用最低，其中fn(xn)表示资源费用函数，xn表示服务节点n 的服务台数量，即第n 类资源的分配数量，N 表示资源的最大种类数。式(2)表示配置目标项目的评价完工时间最短，Tz表示第z 类项目的完工时间，Pz表示第z 类项目关键路径上的任务总数，ws表示任务的执行时间，即任务在服务节点上的逗留时间。式(3)表示汇入约束，即非关键路径节点上的服务时间之和不得大于关键路径节点上的服务时间之和，排队网络模型中存在1～Q 个汇入约束，Ki表示第i 个汇入约束的非关键路径节点数，Mi则表示第i 个汇入约束的关键路径节点数。式(4)表示各节点的逗留时间。式(5)为排队模型相关参数的计算公式。

3 求解

在上述模型中，各节点分配的资源数量决定了项目的完工时间，该模型可看作如何分配各节点资源数量以使成本最低、项目的完工时间最短，因此可将该模型近似地看作多目标背包问题(Knapsack Problem)［11］。作为一种经典的组合优化问题，背包问题有着十分广泛的工程应用背景。由于该问题是一种NP(Non－deterministic Polynomial)完全问题，对其求解较为困难，而多目标更加剧了问题的复杂性。由于各目标之间存在冲突，模型不存在全局最优解，只能对多个目标进行折中处理，寻找Parato非支配解(Non－dominated solutions)［12］。常见的折中方法主要有加权求和法、约束法、最大－最小法等［12］。对于本文提出的问题，考虑到问题的实际背景，即客户会对产品要求一个相对固定的交期，故采用约束法折中，对项目的工期目标进行限定。

背包问题的求解方法可分为精确算法和进化算法。随着问题的规模增大，精确算法的求解效果并不理想。近年来，进化算法特别是遗传算法在求解该问题时越来越有效［13－14］，因此，本文采用遗传算法对问题进行求解。

由于基本遗传算法(Simple Genetic Algorithm，SGA)存在早熟收敛、局部搜索能力差、无方向性等缺点，对SGA 可从编码、初始群体、适应度函数、遗传算子、控制参数等方面进行改进。针对本文问题的特点，采用自适应遗传算法(Adaptive Genetic Algorithms，AGA)主要对遗传算子和控制参数进行改进。对于选择算子，采用最优保存策略以保证优秀基因不被破坏，同时为避免“早熟”现象，配合使用入侵选择策略。对于交叉与变异算子，SGA 采用固定的策略与控制参数无法满足不同进化时期的动态要求，本文主要采用文献［15］中给出的方法进行改进。

下面给出AGA 算法的设计步骤:

步骤1:编码，随机产生初始种群Popsize。为反映所求问题的结构特征，满足积木块编码原则，本文采用多参数级联编码方法，多参数级联编码染色体结构如图2所示。由图2 可知，染色体R 长度为n，采用整数编码，顺序值为节点编号，基因值xn为节点服务台数量，其数值大于等于1，表示服务台的数量至少为1，xn决定着该节点的平均服务时间。在给定的λ 和μ 下，节点服务台数量xn与节点平均服务时间t 之间的关系如图3所示。由图3 可知，节点上资源数目增加到Rmax时，节点上的平均服务时间趋于一定，因此xn的取值范围为［1－Rmax］。根据基因的取值范围随机产生初始种群Popsize。

图2 多参数级联编码染色体结构

图3 节点服务台数量xn 与平均服务t 之间的关系

步骤2:算法终止判断。由于目标函数的最小值难以确定，所以终止条件为最大迭代次数Gen，算法到达预测迭代次数时，取种群中适应度最高的染色体表示的资源配置组合，退出算法，否则转下一步。

步骤3:解码，计算个体的适应度值。由于目标函数是求最小值问题，令:

Cmax为最大完工时间，定义为:

适应值越大表明越接近最优解。

步骤4:选择算子。设num 为新增个体数量。首先更新迄今为止的最优个体，用最优个体取代当前种群适应度值最低的个体。若此时已经连续多代最优个体未更新，则将num 增加△num，当有最优个体更新时，再将num 值调回初始值。然后去除当前种群适应度最低的num 个个体。

步骤5:交叉算子。计算被选入交叉操作的个体适应度指标，根据式(8)算出当前交叉概率pc，采用两点交叉算子对种群进行交叉配对。

式(8)中k 的取值范围为(0，+∞)，Cmax为种群最大适应度值，C－＇为种群平均适应度值，pc∈［0.4，0.9］。当种群趋于收敛时，pc减小;反之，pc增大，种群产生新个体能力增强。

在执行交叉运算后，新生成的个体中基因值xn可能会超出其范围，对于这种情况需要对2 个父代重新选择交叉点进行交叉。若重新选择后仍然超出其范围，则直接将2 个父代补充到下一代。

步骤6:变异算子。采用单点变异操作，以变异概率pm在个体中随机选择变异节点，若染色体第x 位基因被选中，则在该基因值域范围内随机生成一个整数，代替原来的基因。若多代最优个体未更新，则将变异概率增加△pm，反之将pm调回初始值。

步骤7:形成下一代群体，转向步骤2。在算法开始前需要收集并整理出如下数据:①各类项目到达速率RC;②网络中各节点服务速率RS;③资源种类数N;④各资源费用系数CostForXp、各资源上限Rmax;⑤各类项目的非关键路径条数NonKey;⑥各类项目的非关键路径位置矩阵nonKetStr;⑦各类项目的关键路径节点数P;⑧各类项目完工时间限制T;⑨遗传算法相关参数Gen、Popsize、k、pm、△pm、num、△num、Cmax。

4 实验仿真

案例企业为某汽车零部件制造公司，该公司向国内外多家知名汽车主机厂供应汽车零部件，产品型号多达数百种，属于典型的多品种小批量生产企业，对此，企业采用项目方式对订单进行全程管理，并对项目按照产品设计的新旧程度进行分类。为减少问题的复杂程度，不失一般性，将这些项目分为2 类:新产品项目和既有产品项目。每类项目流程高度相似，对项目流程及资源特点进行分析抽象后，得到项目网络图如图4所示，项目网络图基本数据如表1所示，项目数据及相关资源特征如表2～3所示，其中新产品研发时间约束为20，产品生产时间约束为80。遗传算法进化曲线如图5所示。

算法求得最优个体为3，1，1，1，1，1，1，1，1，3，3，4，4，2，2，3，5，2，1，2，4，2，2，1，1;资源费用为227，跟原始费用相比，优化后的资源费用大大降低。

图4 项目网络图

表1 项目网络图基本数据

表2 项目数据表

表3 资源数据表

图5 遗传算法进化曲线

5 结束语

多项目并行与项目的动态性增加了项目资源配置问题的复杂性，对传统的RCPSP 的研究虽已较好地解决了多项目资源配置问题，但对于项目的动态性问题考虑较少。本文基于排队论的动态多项目资源配置模型，从排队论的角度考虑了企业资源服务项目的问题，该模型考虑了项目随机聚散现象和资源随机服务项目工作过程中的特点，利用排队论的数学理论和方法可以较好地处理项目资源配置中的动态性问题。给出的案例首先对项目及资源进行了简单的抽象，表明该模型可以在满足时间约束的情况下对资源进行优化配置。但在实际中，项目及其任务的聚集、项目的优先级、资源的服务时间、资源的共享等情况更加复杂，因此如何建立项目及其资源的相关模型以及模型的验证将是下一步研究的重点。

［1］祁国宁，顾新建，李仁旺.大批量定制及其模型的研究［J］.计算机集成制造系统，2000，6(2):41－45.

［2］邱进冬，顾新建.面向大规模定制的项目管理研究［J］.成组技术与生产现代化，2003，20(1):34－37.

［3］刘士新.项目优化调度理论与方法［M］.北京:机械工业出版社，2006:1－10.

［4］方晨，王凌.资源约束项目调度研究综述［J］.控制与决策，2010，25(5):641－650.

［5］程序，吴澄.粒子群优化算法求解多模式项目再调度问题［J］.计算机集成制造系统，2009，15(1):97－101.

［6］项目管理协会(美)编.项目管理知识体系指南［M］.王勇，张斌，译.北京:电子工业出版社，2009:80－87.

［7］Burke P J.The output of a queueing system［J］.Operations Research，1956，4(6):699－704.

［8］徐怀，唐玲.复合泊松过程的可加性［J］.大学数学，2006，22(6):114－117.

［9］Jackson J R.networks of waiting lines［J］.Operations Research，1957，5(4):518－521.

［10］刘琼，林魁，张超勇，等.基于关键链多项目鲁棒调度［J］.计算机集成制造系统，2012，18(4):813－820.

［11］熊小华，宁爱兵，马良.基于多交换邻域搜索的多维0/1 背包问题竞争决策算法［J］.系统工程理论与实践，2010，30(8):1448－1456.

［12］马小姝，李宇龙，严浪.传统多目标优化方法和多目标遗传算法的比较综述［J］.电气传动自动化，2010(3):48－50.

［13］Lin F.Solving the knapsack problem with imprecise weight coefficients using genetic algorithms［J］.European Journal of Operational Research，2008，185(1):133－145.

［14］刘西奎，李艳，许进.背包问题的遗传算法求解［J］.华中科技大学学报(自然科学版)，2002，30(6):89－90.

［15］李济民.基于遗传算法的轨道精调系统的设计与应用［D］.武汉:武汉理工大学，2012:37－40.