A Study on Scheduling Coupled Activities with Minimum Total Feedback Lengths

doi:10.12005/orms.2019.0084

Abstract

Abstract: The scheduling of coupled activities directly affects the time and cost of new product development, and thus has become a focal point of both scholars and design managers. Researchers have shown that finding an activity sequence with minimum total feedback length can significantly reduce development time. However, the feedback length minimization problem is NP-hard and hard to solve. To solve large problem instances in reasonable time, this study combines the genetic algorithm with an existing greedy heuristic, and designs a new hybrid optimization algorithm. We also systematically analyze the effect of parameters, such as crossover rate and mutation rate, on algorithm’s performance, and suggest appropriate parameter values. Experimental results indicate that the hybrid optimization algorithm greatly improves the existing greedy heuristic. Moreover, with same settings, the hybrid optimization algorithm often yields better solutions than the genetic algorithm without the greedy heuristic.

Key words: design structure matrix, new product development, coupled activity scheduling, genetic algorithm, hybrid optimization algorithm

摘要： 耦合活动的排程直接影响新产品开发的周期和成本,因而受到了学者和研发管理人员的普遍关注。本文针对最小化总反馈长度这一耦合活动排程常用目标,将遗传算法与局部搜索算法相结合,提出了一种新的混合优化算法,并系统分析了参数对算法性能的影响。然后将算法应用到实际案例和大量随机算例中,实验结果表明混合优化算法较大幅度提高了现有局部搜索算法解的质量;同等情形下,混合优化算法所获得解比单纯运用遗传算法所获得解更好。

关键词: 设计结构矩阵, 新产品开发, 耦合活动排程, 遗传算法, 混合优化算法

CLC Number:

C393

QIAN Yan-jun, LIN Jun. A Study on Scheduling Coupled Activities with Minimum Total Feedback Lengths[J]. Operations Research and Management Science, 2019, 28(4): 94-99.

钱艳俊,林军. 最小化总反馈长度的耦合活动排程研究[J]. 运筹与管理, 2019, 28(4): 94-99.

References

[1] Shaja A S, Sudhakar K. Optimized sequencing of analysis components in multidisciplinary systems[J]. Research in Engineering Design, 2010, 21(3): 173-187.
[2] Ulrich K T, Eppinger S D. Product design and development(5th ed.)[M]. McGraw-Hill, Boston, 2013.
[3] Browning T R. Design structure matrix extensions and innovations: a survey and new opportunities[J]. IEEE Transactions on Engineering Management, 2016, 63(1): 27-52.
[4] Eppinger S D, Whitney D E, Smith R P, Gebala D A. A model-based method for organizing tasks in product development[J]. Research in Engineering Design, 1994, 6(1): 1-13.
[5] Lin J, Chai K H, Wong Y S, Brombacher A C. A dynamic model for managing overlapped iterative product development[J]. European Journal of Operational Research, 2008, 185(1): 378-392.
[6] Yang Q, Yao T, Lu T, Zhang B. An overlapping-based design structure matrix for measuring interaction strength and clustering analysis in product development project[J]. IEEE Transactions on Engineering Management, 2014, 61(1): 159-170.
[7] Smith R P, Eppinger S D. A predictive model of sequential iteration in engineering design[J]. Management Science, 1997, 43(8): 1104-1120.
[8] Eppinger S D, Browning T R. Design structure matrix: methods and applications[M]. MIT press. Cambridge, Massachusetts, 2012.
[9] Browning T R. Applying the design structure matrix to system decomposition and integration problems: a review and new directions[J]. IEEE Transactions on Engineering Management, 2001, 48(3): 292-306.
[10] Qian Y J, Lin J, Goh T N, Xie M. A novel approach to DSM-based activity sequencing problem[J]. IEEE Transactions on Engineering Management, 2011, 58(4): 688-705.
[11] Ahmadi R, Roemer T A, Wang R H. Structuring product development processes[J]. European Journal of Operational Research, 2001, 130(3): 539-558.
[12] Lee H, Suh H W. Workflow structuring and reengineering method for design process[J]. Computers and Industrial Engineering, 2006, 51(4): 698-714.
[13] Luh D B, Ko Y T, Ma C H. A dynamic planning approach for new product development[J]. Concurrent Engineering: Research and Applications, 2009, 17(1): 43-59.
[14] 唐敦兵,钱晓明,刘建刚.基于设计结构矩阵DSM的产品设计与开发[M].科学出版社,2009.
[15] Tuholski S J, Tommelein I D. Design structure matrix implementation on a seismic retrofit[J]. Journal of Management in Engineering, 2010, 26(3): 144-152.
[16] 杨青,单晨,唐尔玲.基于返工风险传播和预处理的研发项目流程DSM优化[J].系统工程理论与实践,2015,35(6):1501-1508.
[17] Meier C, Yassine A A, Browning T R. Design process sequencing with competent genetic algorithms[J]. Journal of Mechanical Design, 2007, 129(6): 566-585.
[18] Steward D V. The design structure system: a method for managing the design of complex systems[J]. IEEE Transactions on Engineering Management, 1981, 49(4): 428-442.
[19] Kusiak A, Wang J. Efficient organizing of design activities[J]. International Journal of Production Research, 1993, 31(4): 753-769.
[20] Lin J, Qian Y, Cui W, Goh T N. An effective approach for scheduling coupled activities in development projects[J]. European Journal of Operational Research, 2015, 243: 97-108.
[21] Gebala D A, Eppinger S D. Methods for analyzing design procedures, proceedings of ASME 3rd international conference on design theory and methodology, 1991. 227-233.
[22] Browning T R, Eppinger S D. Modeling impacts of process architecture on cost and schedule risk in product development[J]. IEEE Transactions on Engineering Management, 2002, 49(4): 428-442.
[23] Whitfield R I, Duffy A H B, Coates G, Hills B. Efficient process optimization[J]. Concurrent Engineering: Research and Applications, 2003, 11(2): 83-92.
[24] Lancaster J, Cheng K. A fitness differential adaptive parameter controlled evolutionary algorithm with application to the design structure matrix[J]. International Journal of Production Research, 2008, 46(18): 5043-5057.
[25] Qian Y, Lin J. Organizing interrelated activities in complex product development[J]. IEEE Transactions on Engineering Management, 2014, 61(2): 298-309.
[26] Lin J, Huang W, Qian Y, Zhao X. Scheduling interrelated activities using insertion-based heuristics[J]. IEEE Transactions on Engineering Management, 2018, 65(1): 113-127.
[27] Tang D B, Zheng L, Li Z Z, Zhang S Q. Re-engineering of the design process for concurrent engineering[J]. Computers and Industrial Engineering, 2000, 38(4): 479-491.
[28] Lin J, Qian Y J, Cui W T. Managing the concurrent execution of dependent product development stages[J]. IEEE Transactions on Engineering Management, 2012, 59(1): 104-114.