新產品開發(fā)過程中的任務調度與分配

鐘金宏，鄭 貴 ZHONG Jin-hong,ZHENG Gui

（1.合肥工業(yè)大學 管理學院，安徽 合肥 230009；2.過程優(yōu)化與智能決策教育部重點實驗室，安徽 合肥 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 引言

快速推出高質量的新產品和新服務對提升和保持企業(yè)的市場競爭力非常關鍵，受到企業(yè)的普遍重視。新產品開發(fā)過程中的任務調度和資源優(yōu)化配置，有利于提高資源的利用率，優(yōu)化開發(fā)流程，從而縮短新產品開發(fā)周期，降低開發(fā)成本。對復雜產品開發(fā)來說尤其如此，它包含眾多的各級開發(fā)任務，需要大量各類資源；而且，它需要眾多供應商的協同開發(fā)設計，設計和資源是分布的，合理調配資源、優(yōu)化安排任務顯得尤為重要。目前，新產品開發(fā)過程中的任務調度、任務分配研究不多，復雜產品開發(fā)過程中這方面研究就更少。本文從任務調度、任務分配和實驗任務分配等方面進行了回顧。

1 任務調度

本質上，新產品開發(fā)過程中的任務調度問題就是通過合理規(guī)劃和重組任務（活動），獲取使產品開發(fā)成本最低或時間最短的任務安排。文獻中任務調度模型考慮的因素主要有[1-19]：資源約束、是否針對復雜產品、是否為多項目、是否考慮子項目、并行工程、設計迭代、供應商參與模式、新產品收益的不確定性、任務（活動）的可替換性，以及任務（活動）的成本、持續(xù)時間的不確定性。采用的方法主要有：基于設計結構矩陣（DSM）的方法、基于Petri網的方法、啟發(fā)式算法、元啟發(fā)式算法（如粒子群優(yōu)化算法、蟻群算法、遺傳算法、模擬退火算法）、模糊束搜索算法、Markov過程建模方法、模糊集理論、隨機方法。

基于DSM/Petri網的流程優(yōu)化模型。Chen等開發(fā)了基于DSM的項目調度和重新調度框架[1]。裘樂淼等基于動態(tài)DSM實現任務重組和任務執(zhí)行次序的優(yōu)化[2]。米潔利用DSM計算不同任務序列的執(zhí)行時間，獲取最優(yōu)任務序列[3]。施國強等分別采用擴展高級關系Petri網和著色Petri網研究了復雜產品開發(fā)過程中的子項目和多項目調度問題[4-5]。Yan等基于擴展隨機高級評估Petri網（ESHLEP-N），提出了建模和仿真產品開發(fā)流程的方法[6]。

考慮不確定性的數學規(guī)劃模型。任務（或活動）的持續(xù)時間不確定是主要關注點。Belhe和Kusiak開發(fā)了動態(tài)啟發(fā)式調度方法，處理設計活動的權重和持續(xù)時間的不確定，目標是最小化設計項目的加權延遲[7]。Schmidt和Grossmann研究了農藥和醫(yī)藥公司新產品開發(fā)中的任務調度問題，考慮任務的成本和持續(xù)時間以及新產品收入等方面的不確定性，建立了混合整數規(guī)劃模型，最大化期望的新產品凈現值[8]。Hapke和Slowinski用模糊集表述不確定性活動持續(xù)時間，應用調度規(guī)則確定軟件開發(fā)項目的最小模糊完工時間調度[9-10]。Wang考慮不確定性活動持續(xù)時間和首選到期日約束，建立了以最小化項目延遲概率為目標的優(yōu)化模型，分別開發(fā)了模糊束搜索算法和用定性可能性理論指導搜索過程的遺傳算法[11-12]。后來，他將產品開發(fā)項目調度問題建模為約束滿足問題，考慮項目到期日約束不能違背，采用SA和GA修復調度使資源約束違背成本最小[13]。梁亮和郭波建立了考慮設計迭代和任意設計活動完成時間隨機分布的產品開發(fā)過程隨機優(yōu)化模型，開發(fā)了結合Markov過程建模方法的混合蟻群求解算法[14]。張龍等研究了具有不確定時間參數的復雜產品開發(fā)項目調度問題，提出基于預測的模糊項目調度算法[15]。

未考慮不確定性的數學規(guī)劃模型。Tukel和Wasti分別建立了契約式和資源集成式供應商參與模式產品開發(fā)項目的調度模型[16]。Yan和Wu基于活動的加權優(yōu)先級，提出了并行產品開發(fā)流程的啟發(fā)式調度方法，使用GA確定權重[17]。周婼娜等研究了并行開發(fā)模式下有限資源約束的任務調度問題，提出了以加權任務關鍵度和延期率為任務優(yōu)先級的調度策略[18]。Ranjbar和Davaris研究了考慮替代技術的項目調度問題，設計了新的改進分支定界算法調度可替換R&D活動實現期望凈現值最大[19]。

2 任務分配

產品開發(fā)過程中的任務分配問題從本質上講是一個資源配置和任務調度的集成優(yōu)化問題。文獻中涉及的待配置資源包括一般性泛化資源和人力資源，問題模型可分為單/多目標的數學規(guī)劃模型和多屬性決策模型，考慮的模型要素主要有：并行工程、供應商協同設計開發(fā)、一般產品與復雜產品、單項目與多項目、設計迭代數量的不確定性、設計風險管理、單目標與多目標[19-35]。采用的方法主要有：Lagrangian松弛、隨機動態(tài)規(guī)劃、序數優(yōu)化、元啟發(fā)式方法（如蜂群算法、病毒進化遺傳算法、遺傳算法）、分枝定界法、基于任務加權優(yōu)先級或任務與資源匹配加權優(yōu)先級的多準則評價排序法、多色集合理論、系統(tǒng)動力學與控制理論等。

針對一般性泛化資源。Liu等研究了考慮不確定性同時管理設計風險的分布式設計項目的調度和協調問題，提出了平衡建模精度和計算復雜性的新數學優(yōu)化模型，開發(fā)了結合松弛和隨機動態(tài)規(guī)劃的求解方法[20]。Luh等研究考慮不確定設計迭代數量同時管理設計風險的設計項目調度問題，以最小化項目拖期、提前和風險懲罰為目標，開發(fā)了結合松弛、隨機動態(tài)規(guī)劃和序數優(yōu)化的求解方法[21]。Joglekar和Ford提出了集成系統(tǒng)動力學和控制理論的產品開發(fā)過程資源分配模型，控制理論模型用于推出最優(yōu)資源分配策略（預見策略），系統(tǒng)動力學模型用于檢驗策略的表現[22]。黃洪鐘等提出了基于任務優(yōu)先級的資源分配算法[23]。曹守啟等基于資源與任務匹配的加權優(yōu)先級，開發(fā)了復雜產品開發(fā)過程中資源的優(yōu)化選擇和使用的多準則評價方法[24]。Koudil等研究了協同設計中任務分配與調度的集成優(yōu)化問題，設計了蜂群算法[25]。孫清超等建立了多項目環(huán)境下資源分配問題的粗匹配和細匹配數學模型，提出了開發(fā)能力需求分析方法[26]。唐加福等研究了產品設計過程中多種資源的優(yōu)化分配，建立了考慮設計預算和資源約束的以用戶對產品的總體滿意水平最大為目標的線性規(guī)劃模型[27]。宮俊和汪定偉采用面向任務級的敏捷化開放機制研究了多研究中心多新產品開發(fā)的調度問題，建立了以完成所有新產品開放任務時間之和最小為目標的優(yōu)化模型，以實現資源共享和互補，設計了禁忌搜索算法[28]。

針對人力資源。楊波等提出了產品開發(fā)過程中任務分解原則，分別建立了任務到團隊、任務到團隊內人員的數學模型，分支定界法[29]。李玉家等建立了考慮人力資源約束的并行產品開發(fā)過程中的任務分配問題的數學模型，采用遺傳算法實現總項目完成周期最小化[30]。賀澤等采用AHP方法評價并分配船舶協同設計中的智力資源[31]。劉建剛等基于遺傳算法開發(fā)了將并行開發(fā)任務分配給確定開發(fā)團隊的智能化解決方案[32]。張永健等建立了考慮項目時間最短、完成質量最高及設計人員負載均衡的設計任務規(guī)劃多目標優(yōu)化模型，設計了病毒進化遺傳算法[33]。崔衛(wèi)華等利用多色集合理論建立了設計者資源的靜態(tài)和動態(tài)分配模型[34]。宮俊和汪定偉研究了企業(yè)的多個研究中心及其研究人員如何有效地分配到多個新產品開發(fā)中，建立了以最小開發(fā)成本為目標的決策優(yōu)化模型，設計基于遺傳算法的優(yōu)化方法[35]。

3 試驗任務分配

產品開發(fā)過程中的試驗任務分配研究很少，主要針對制藥行業(yè)的新藥品開發(fā)試驗。Schmidt和Grossmann研究了無限資源下的制藥行業(yè)新產品開發(fā)試驗任務調度問題，提出了7個混合整數規(guī)劃模型（MIP）[36]。Jain和Grossmann將這些調度模型擴展到考慮資源約束和外包情況，開發(fā)了基于圖的MIP模型[37]。Honkomp等研究了非常類似于新產品開發(fā)試驗任務調度的R&D項目調度問題[38]。Subramanian等提出了考慮活動的持續(xù)時間、成本和資源需求不確定的臨床試驗仿真優(yōu)化框架[39]。后來他們通過考慮市場回報率和活動費用估計的變化風險，擴展了該模型[40]。Maravelias和Grossmann提出了集成試驗任務調度和能力規(guī)劃決策的MIP模型[41]。后來他們開發(fā)了考慮資源投資和可變資源需求的試驗任務調度MIP模型[42]。Colvin和Maravelias開發(fā)了醫(yī)藥R&D中的臨床試驗規(guī)劃的多階段隨機規(guī)劃框架[43]。后來他們針對制藥行業(yè)新產品研發(fā)中的臨床試驗調度和臨床試驗必需資源規(guī)劃的集成優(yōu)化問題，提出了隨機規(guī)劃框架[44]。

4 結束語

產品開發(fā)過程管理和云計算一道成為繼供應鏈之后企業(yè)管理的新熱點，如R&D項目組合選擇、開發(fā)流程優(yōu)化、開發(fā)過程的動態(tài)管理、參與產品開發(fā)供應商的協同管理等。值得注意的是，復雜產品開發(fā)過程工程管理方面的研究還比較匱乏。

任務分配與調度是產品開發(fā)過程管理的重要內容，但這方面的研究并不多，外文文獻尚無明確針對復雜產品開發(fā)的任務分配與調度研究。產品開發(fā)過程中的試驗任務分配與調度研究就更少，主要是針對制藥行業(yè)的新藥品開發(fā)。

文獻中主要是采用DSM/Petri網、數學規(guī)劃、多準則評價等方法來建立問題模型，產品開發(fā)過程的不確定性是模型中經?？紤]的因素，在任務分配方面的研究中人力資源配置是關注熱點。模型的求解方法主要是啟發(fā)式方法、元啟發(fā)式方法、模糊集理論、隨機方法和精確方法。

[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] 裘樂淼，張樹有，徐春偉,等.基于動態(tài)設計結構矩陣的復雜產品配置過程規(guī)劃技術[J].機械工程學報，2010,46(7):136-141.

[3] 米潔.基于不確定性的復雜產品開發(fā)迭代過程優(yōu)化設計[J].計算機集成制造系統(tǒng)，2009,15(2):222-225.

[4] 施國強，李伯虎，柴旭東.不確定條件下復雜產品開發(fā)項目調度模型研究[J].計算機集成制造系統(tǒng)，2007,13(10):1909-1913.

[5] 施國強，李伯虎，柴旭東.基于著色Petri網的復雜產品開發(fā)多項目調度建模研究[J].系統(tǒng)仿真學報，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]梁亮，郭波.基于混合蟻群算法的產品開發(fā)過程優(yōu)化方法[J].系統(tǒng)工程理論與實踐，2009,29(10):118-128.

[15] 張龍，劉民，劉濤,等.復雜產品開發(fā)項目調度問題的模糊優(yōu)化算法[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]周婼娜，秦現生，顧學民.并行產品開發(fā)模式下任務調度方法研究[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] 黃洪鐘，李麗，劉偉.并行工程中設計任務的動態(tài)調度[J].機械工程學報，2002,38（增）:164-167.

[24] 曹守啟，陳云，韓彥嶺,等.復雜產品開發(fā)過程中資源優(yōu)化使用技術研究[J].計算機集成制造系統(tǒng)，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]孫清超，孫偉，郭鋼.多項目環(huán)境下復雜產品開發(fā)資源動態(tài)分配技術[J].中國機械工程，2011,22(23):2844-2848.

[27] 唐加福，劉士，陳以,等.產品優(yōu)化設計的資源分配模型[J].系統(tǒng)工程學報，2003,18(3):284-288.

[28] 宮俊，汪定偉.敏捷化產品開發(fā)中調度問題的研究[J].控制與決策，2002,17（增刊）:707-710.

[29]楊波，黃克正，孫紅衛(wèi).面向并行工程的任務分配與規(guī)劃[J].計算機集成制造系統(tǒng)，2002,8(7):542-545.

[30] 李玉家，胡宗武，金燁.并行產品開發(fā)過程中的任務分配問題研究[J].中國機械工程，2002,13(7):580-583.

[31]賀澤，邱長華，王能建.船舶協同設計團隊模型及智力資源評價方法研究[J].哈爾濱工程大學學報，2007,28(1):108-113.

[32] 劉建剛，楊春，王寧生,等.并行產品開發(fā)中任務智能分配[J].哈爾濱工業(yè)大學學報，2009,41(7):190-192.

[33]張永健，鐘詩勝，王瑞.基于病毒進化遺傳算法的復雜產品設計任務規(guī)劃[J].計算機輔助設計與圖形學學報，2011,23(2):350-356.

[34]崔衛(wèi)華，楊波，宋開峰.產品協同設計過程的資源配置[J].組合機床與自動化加工技術，2011(3):97-100.

[35] 宮俊，汪定偉.新產品開發(fā)的資源二維指派問題[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.