新产品开发过程中的任务调度与分配

钟金宏，郑 贵 ZHONG Jin-hong,ZHENG Gui

（1.合肥工业大学 管理学院，安徽 合肥 230009；2.过程优化与智能决策教育部重点实验室，安徽 合肥 230009）

(1.School of Management,Hefei University of Technology,Hefei 230009,China;2.Key Laboratory of Process Optimization and Intelligent Decision-making,Ministry of Education,Hefei 230009,China)

0 引言

快速推出高质量的新产品和新服务对提升和保持企业的市场竞争力非常关键，受到企业的普遍重视。新产品开发过程中的任务调度和资源优化配置，有利于提高资源的利用率，优化开发流程，从而缩短新产品开发周期，降低开发成本。对复杂产品开发来说尤其如此，它包含众多的各级开发任务，需要大量各类资源；而且，它需要众多供应商的协同开发设计，设计和资源是分布的，合理调配资源、优化安排任务显得尤为重要。目前，新产品开发过程中的任务调度、任务分配研究不多，复杂产品开发过程中这方面研究就更少。本文从任务调度、任务分配和实验任务分配等方面进行了回顾。

1 任务调度

本质上，新产品开发过程中的任务调度问题就是通过合理规划和重组任务（活动），获取使产品开发成本最低或时间最短的任务安排。文献中任务调度模型考虑的因素主要有[1-19]：资源约束、是否针对复杂产品、是否为多项目、是否考虑子项目、并行工程、设计迭代、供应商参与模式、新产品收益的不确定性、任务（活动）的可替换性，以及任务（活动）的成本、持续时间的不确定性。采用的方法主要有：基于设计结构矩阵（DSM）的方法、基于Petri网的方法、启发式算法、元启发式算法（如粒子群优化算法、蚁群算法、遗传算法、模拟退火算法）、模糊束搜索算法、Markov过程建模方法、模糊集理论、随机方法。

基于DSM/Petri网的流程优化模型。Chen等开发了基于DSM的项目调度和重新调度框架[1]。裘乐淼等基于动态DSM实现任务重组和任务执行次序的优化[2]。米洁利用DSM计算不同任务序列的执行时间，获取最优任务序列[3]。施国强等分别采用扩展高级关系Petri网和着色Petri网研究了复杂产品开发过程中的子项目和多项目调度问题[4-5]。Yan等基于扩展随机高级评估Petri网（ESHLEP-N），提出了建模和仿真产品开发流程的方法[6]。

考虑不确定性的数学规划模型。任务（或活动）的持续时间不确定是主要关注点。Belhe和Kusiak开发了动态启发式调度方法，处理设计活动的权重和持续时间的不确定，目标是最小化设计项目的加权延迟[7]。Schmidt和Grossmann研究了农药和医药公司新产品开发中的任务调度问题，考虑任务的成本和持续时间以及新产品收入等方面的不确定性，建立了混合整数规划模型，最大化期望的新产品净现值[8]。Hapke和Slowinski用模糊集表述不确定性活动持续时间，应用调度规则确定软件开发项目的最小模糊完工时间调度[9-10]。Wang考虑不确定性活动持续时间和首选到期日约束，建立了以最小化项目延迟概率为目标的优化模型，分别开发了模糊束搜索算法和用定性可能性理论指导搜索过程的遗传算法[11-12]。后来，他将产品开发项目调度问题建模为约束满足问题，考虑项目到期日约束不能违背，采用SA和GA修复调度使资源约束违背成本最小[13]。梁亮和郭波建立了考虑设计迭代和任意设计活动完成时间随机分布的产品开发过程随机优化模型，开发了结合Markov过程建模方法的混合蚁群求解算法[14]。张龙等研究了具有不确定时间参数的复杂产品开发项目调度问题，提出基于预测的模糊项目调度算法[15]。

未考虑不确定性的数学规划模型。Tukel和Wasti分别建立了契约式和资源集成式供应商参与模式产品开发项目的调度模型[16]。Yan和Wu基于活动的加权优先级，提出了并行产品开发流程的启发式调度方法，使用GA确定权重[17]。周婼娜等研究了并行开发模式下有限资源约束的任务调度问题，提出了以加权任务关键度和延期率为任务优先级的调度策略[18]。Ranjbar和Davaris研究了考虑替代技术的项目调度问题，设计了新的改进分支定界算法调度可替换R&D活动实现期望净现值最大[19]。

2 任务分配

产品开发过程中的任务分配问题从本质上讲是一个资源配置和任务调度的集成优化问题。文献中涉及的待配置资源包括一般性泛化资源和人力资源，问题模型可分为单/多目标的数学规划模型和多属性决策模型，考虑的模型要素主要有：并行工程、供应商协同设计开发、一般产品与复杂产品、单项目与多项目、设计迭代数量的不确定性、设计风险管理、单目标与多目标[19-35]。采用的方法主要有：Lagrangian松弛、随机动态规划、序数优化、元启发式方法（如蜂群算法、病毒进化遗传算法、遗传算法）、分枝定界法、基于任务加权优先级或任务与资源匹配加权优先级的多准则评价排序法、多色集合理论、系统动力学与控制理论等。

针对一般性泛化资源。Liu等研究了考虑不确定性同时管理设计风险的分布式设计项目的调度和协调问题，提出了平衡建模精度和计算复杂性的新数学优化模型，开发了结合松弛和随机动态规划的求解方法[20]。Luh等研究考虑不确定设计迭代数量同时管理设计风险的设计项目调度问题，以最小化项目拖期、提前和风险惩罚为目标，开发了结合松弛、随机动态规划和序数优化的求解方法[21]。Joglekar和Ford提出了集成系统动力学和控制理论的产品开发过程资源分配模型，控制理论模型用于推出最优资源分配策略（预见策略），系统动力学模型用于检验策略的表现[22]。黄洪钟等提出了基于任务优先级的资源分配算法[23]。曹守启等基于资源与任务匹配的加权优先级，开发了复杂产品开发过程中资源的优化选择和使用的多准则评价方法[24]。Koudil等研究了协同设计中任务分配与调度的集成优化问题，设计了蜂群算法[25]。孙清超等建立了多项目环境下资源分配问题的粗匹配和细匹配数学模型，提出了开发能力需求分析方法[26]。唐加福等研究了产品设计过程中多种资源的优化分配，建立了考虑设计预算和资源约束的以用户对产品的总体满意水平最大为目标的线性规划模型[27]。宫俊和汪定伟采用面向任务级的敏捷化开放机制研究了多研究中心多新产品开发的调度问题，建立了以完成所有新产品开放任务时间之和最小为目标的优化模型，以实现资源共享和互补，设计了禁忌搜索算法[28]。

针对人力资源。杨波等提出了产品开发过程中任务分解原则，分别建立了任务到团队、任务到团队内人员的数学模型，分支定界法[29]。李玉家等建立了考虑人力资源约束的并行产品开发过程中的任务分配问题的数学模型，采用遗传算法实现总项目完成周期最小化[30]。贺泽等采用AHP方法评价并分配船舶协同设计中的智力资源[31]。刘建刚等基于遗传算法开发了将并行开发任务分配给确定开发团队的智能化解决方案[32]。张永健等建立了考虑项目时间最短、完成质量最高及设计人员负载均衡的设计任务规划多目标优化模型，设计了病毒进化遗传算法[33]。崔卫华等利用多色集合理论建立了设计者资源的静态和动态分配模型[34]。宫俊和汪定伟研究了企业的多个研究中心及其研究人员如何有效地分配到多个新产品开发中，建立了以最小开发成本为目标的决策优化模型，设计基于遗传算法的优化方法[35]。

3 试验任务分配

产品开发过程中的试验任务分配研究很少，主要针对制药行业的新药品开发试验。Schmidt和Grossmann研究了无限资源下的制药行业新产品开发试验任务调度问题，提出了7个混合整数规划模型（MIP）[36]。Jain和Grossmann将这些调度模型扩展到考虑资源约束和外包情况，开发了基于图的MIP模型[37]。Honkomp等研究了非常类似于新产品开发试验任务调度的R&D项目调度问题[38]。Subramanian等提出了考虑活动的持续时间、成本和资源需求不确定的临床试验仿真优化框架[39]。后来他们通过考虑市场回报率和活动费用估计的变化风险，扩展了该模型[40]。Maravelias和Grossmann提出了集成试验任务调度和能力规划决策的MIP模型[41]。后来他们开发了考虑资源投资和可变资源需求的试验任务调度MIP模型[42]。Colvin和Maravelias开发了医药R&D中的临床试验规划的多阶段随机规划框架[43]。后来他们针对制药行业新产品研发中的临床试验调度和临床试验必需资源规划的集成优化问题，提出了随机规划框架[44]。

4 结束语

产品开发过程管理和云计算一道成为继供应链之后企业管理的新热点，如R&D项目组合选择、开发流程优化、开发过程的动态管理、参与产品开发供应商的协同管理等。值得注意的是，复杂产品开发过程工程管理方面的研究还比较匮乏。

任务分配与调度是产品开发过程管理的重要内容，但这方面的研究并不多，外文文献尚无明确针对复杂产品开发的任务分配与调度研究。产品开发过程中的试验任务分配与调度研究就更少，主要是针对制药行业的新药品开发。

文献中主要是采用DSM/Petri网、数学规划、多准则评价等方法来建立问题模型，产品开发过程的不确定性是模型中经常考虑的因素，在任务分配方面的研究中人力资源配置是关注热点。模型的求解方法主要是启发式方法、元启发式方法、模糊集理论、随机方法和精确方法。

[1] Chen,C.H.,Ling,S.F.,Chen,W.Project scheduling for collaborative product develop-ment using DSM[J].International Journal of Project Management,2003,21(4):291-299.

[2] 裘乐淼，张树有，徐春伟,等.基于动态设计结构矩阵的复杂产品配置过程规划技术[J].机械工程学报，2010,46(7):136-141.

[3] 米洁.基于不确定性的复杂产品开发迭代过程优化设计[J].计算机集成制造系统，2009,15(2):222-225.

[4] 施国强，李伯虎，柴旭东.不确定条件下复杂产品开发项目调度模型研究[J].计算机集成制造系统，2007,13(10):1909-1913.

[5] 施国强，李伯虎，柴旭东.基于着色Petri网的复杂产品开发多项目调度建模研究[J].系统仿真学报，2007,19(7):3869-3872.

[6] Yan,H.S.,Wang,Z.,Jiao,X.C.Modeling.Scheduling and simulation of product develop-ment process by extended stochastic high-level evaluation Petri nets[J].Robotics and Computer Integrated Manufacturing,2003,19(4):329-342.

[7] Belhe,U.,Kusiak,A.Scheduling design activities with a pull system approach[J].IEEE Transactions on Robotics and Automation,1995,12(1):15-21.

[8] Schmidt,C.W.&Grossmann,I.E.A mixed integer programming model for stochastic scheduling in new product development[J].Computers&Chemical Engineering,1996,20(1):1239-1244.

[9] Hapke,M.,Slowinski,R.Fuzzy project scheduling system for software development[J].Fuzzy Sets and Systems,1994,67(1):101-117.

[10] Hapke,M.,Slowinski,R.Fuzzy priority heuristics for project scheduling[J].Fuzzy Sets and Systems,1996,83(3):291-299.

[11] Wang,J.A fuzzy project scheduling approach to minimize schedule risk for product development[J].Fuzzy Sets and Systems,2002,127(2):99-116.

[12] Wang,J.A fuzzy robust scheduling approach for product development projects[J].European Journal of Operational Research,2004,152(1):180-194.

[13] Wang,J.Constraint-based schedule repair for product development projects with time-limited constraints[J].Int.J.Production Economics,2005,95(3):399-414.

[14]梁亮，郭波.基于混合蚁群算法的产品开发过程优化方法[J].系统工程理论与实践，2009,29(10):118-128.

[15] 张龙，刘民，刘涛,等.复杂产品开发项目调度问题的模糊优化算法[J].控制工程，2009,16(6):731-734.

[16] Tukel,O.I.,Wasti,S.N.Analysis of supplier buyer relationships using resource constrained project scheduling strategies[J].European Journal of Operational Research,2001,129(2):271-276.

[17] Ji-Hong Yan,Cheng Wu.Scheduling approach for concurrent product development processes[J].Computer in industry,2001,46(2):139-147.

[18]周婼娜，秦现生，顾学民.并行产品开发模式下任务调度方法研究[J].计算机应用，2007,27(12):3139-3141.

[19] Ranjbar,M.,Davari,M.An exact method for scheduling of the alternative technologies in R&D projects[J].Computers&Operations Research,2013,40(1):395-405.

[20] Liu,F.,Luh,P.B.,Moser,B.,Kegg,R.L.Scheduling and Coordination of Distributed Design Projects[J].Annals of the ClRP,1998,47(1):111-114.

[21] Luh,P.B.,Liu,F.,Moser,B.Scheduling of design projects with uncertain number of iterations[J].European Journal of Operational Research,1999,113(3):575-592.

[22] Joglekar,N.R.,Ford,D.N.Product development resource allocation with foresight[J].European Journal of Operational Research,2005,160(1):72-87.

[23] 黄洪钟，李丽，刘伟.并行工程中设计任务的动态调度[J].机械工程学报，2002,38（增）:164-167.

[24] 曹守启，陈云，韩彦岭,等.复杂产品开发过程中资源优化使用技术研究[J].计算机集成制造系统，2005,11(1):26-31.

[25] Koudil,M.,Benatchba,K.,Tarabet,A.,Sahraoui,E.B.Using artificial bees to solve partitioning and scheduling problems in codesign[J].Applied Mathematics and Computation,2007,186(2):1710-1722.

[26]孙清超，孙伟，郭钢.多项目环境下复杂产品开发资源动态分配技术[J].中国机械工程，2011,22(23):2844-2848.

[27] 唐加福，刘士，陈以,等.产品优化设计的资源分配模型[J].系统工程学报，2003,18(3):284-288.

[28] 宫俊，汪定伟.敏捷化产品开发中调度问题的研究[J].控制与决策，2002,17（增刊）:707-710.

[29]杨波，黄克正，孙红卫.面向并行工程的任务分配与规划[J].计算机集成制造系统，2002,8(7):542-545.

[30] 李玉家，胡宗武，金烨.并行产品开发过程中的任务分配问题研究[J].中国机械工程，2002,13(7):580-583.

[31]贺泽，邱长华，王能建.船舶协同设计团队模型及智力资源评价方法研究[J].哈尔滨工程大学学报，2007,28(1):108-113.

[32] 刘建刚，杨春，王宁生,等.并行产品开发中任务智能分配[J].哈尔滨工业大学学报，2009,41(7):190-192.

[33]张永健，钟诗胜，王瑞.基于病毒进化遗传算法的复杂产品设计任务规划[J].计算机辅助设计与图形学学报，2011,23(2):350-356.

[34]崔卫华，杨波，宋开峰.产品协同设计过程的资源配置[J].组合机床与自动化加工技术，2011(3):97-100.

[35] 宫俊，汪定伟.新产品开发的资源二维指派问题[J].东北大学学报（自然科学版），2002,23(4):338-340.

[36] Schmidt,C.W.,&Grossmann,I.E.Optimization models for the scheduling of testing tasks in new product development[J].Industrial&Engineering Chemistry Research,1996,35(10):3498-3510.

[37] Jain,V.,&Grossmann,I.E.Resource-constrained scheduling of tests in new product development[J].Industrial&Engineering Chemistry Research,1999,38(8):3013-3026.

[38] Honkomp,S.J.,Reklaitis,G.V.,&Pekny,G.F.Robust planning and scheduling of process development projects under stochastic conditions[C]//Proceedings of the AIChE annual meeting,Los Angeles,CA,1997.

[39] Subramanian,D.,Pekny,J.F.,&Reklaitis,G.V.A simulation-optimization framework for research and development pipeline management[J].AIChE Journal,2001,47(10):2226-2242.

[40] Subramanian,D.,Pekny,J.F.,Reklaitis,G.V.,&Blau,G.E.Simulation optimization framework for stochastic optimization of R&D pipeline management[J].AIChE Journal,2003,49(1):96-112.

[41] Maravelias,C.T.,&Grossmann,I.E.Simultaneous planning for new product development and batch manufacturing facilities[J].Industrial&Engineering Chemistry Research,2001,40(26):6147-6164.

[42] Maravelias,C.T.,&Grossmann,I.E.Optimal resource investment and scheduling of tests for new product development[J].Computers&Chemical Engineering,2004,28(6-7):1021-1038.

[43] Colvin,M.,Maravelias,C.T.A stochastic programming approach for clinical trial planning in new drug development[J].Computers&Chemical Engineering,2008,32(12):2626-2642.

[44] Colvin,M.,Maravelias,C.T.Scheduling of testing tasks and resource planning in new product development using stochastic programming[J].Computers and Chemical Engineering,2009,33(5):964-976.