基于PDM任务指派问题的研究及应用
|
摘要
产品数据管理(Product Data Management,PDM)是一种以企业的产品为中心,通过计算机网络和数据库等技术,对所有描述产品的数据和与产品开发相关的过程统一进行管理的技术。近年来针对PDM技术的研究大多数是针对PDM的体系结构、产品的数据模型、软件系统的开发、实施方法和集成接口等,很少有论文研究PDM关键过程中的优化问题,其中基于PDM任务指派问题属于PDM关键过程中优化问题中的一类问题。研究基于PDM任务指派问题的解决方法可为PDM系统核心的设计、开发提供理论和算法的支持,可为提高企业的产品设计和生产效率起到积极的意义。
本文用遗传算法的理论和方法对PDM系统项目管理中设计任务的指派问题的建模和优化进行了研究,主要工作分为三个部分:
(1)建立了基于PDM任务指派问题的数学模型,目标是确定最优的指派方案,使项目组的有限设计资源得到合理利用。
(2)分别从宏观和微观上改进了遗传算法,在宏观上引入了循环策略和模拟退火算法,在微观上针对基于PDM任务指派问题数学模型的特点对编码的方式、解码的规则以及遗传算子进行了改进,提出了一种间接编码的混合遗传算法,并对该混合遗传算法的染色体编码方案、解码规则、适值函数和遗传算子等进行了详细设计。
(3)在运用Camel函数和Shubert函数验证了采用循环策略的模拟退火遗传算法性能的基础上,针对提出的间接编码的混合遗传算法,通过一个应用实例,分析并验证了基于PDM任务指派问题的模型和间接编码的混合遗传算法解决该问题的有效性。
Product Data Management (PDM) is a kind of technology which concentrates on products of manufacturing enterprises. It manages both the data to describe products and the developing process of products based on computer network and database technology.
In recent years there are many literatures relating to research of PDM technology. Most of them concern on the architecture of PDM, models of product data, development of software system, implementation methodology and integration interface, etc. The optimization problems of key processes in PDM are seldom studied, for example, research of the task assignment problem based on PDM. The solution of the task assignment problem in PDM may provide theoretical and algorithmic support for kernel design and development of PDM system. It is meaningful for improving design and manufacturing efficiency in enterprises.
In this paper, we discuss modeling and optimization for the design task assignment problem of project management in PDM based on genetic algorithms. The main content includes three aspects as follows:
(1) A mathematical model of the task assignment problem in PDM is established, the objective is to obtain the optimal assignment scheme and to enable the efficient allocation of limited design resources.
(2)The thesis proposes two ways of macroscopic and microscopic respectively in order to improve the performance of the genetic algorithm. In macroscopic aspect, the circular strategy and simulated annealing algorithm are introduced, and in microscopic aspect, the encoding scheme, decoding rule and genetic operators are improved for the mathematical model of task assignment problem in PDM. Then, we propose a kind of indirect hybrid genetic algorithm. Finally, a kind of encoding scheme, decoding rule, fitness function and genetic operators are designed in detail.
(3)Based on using Camel function and the Shubert function to test the performance of the simulated annealing genetic algorithm adopting circular strategy, test was carried through an application example of the task assignment problem based on PDM. The experimental results show that the model and the indirect hybrid genetic algorithm has great effectiveness.
本文用遗传算法的理论和方法对PDM系统项目管理中设计任务的指派问题的建模和优化进行了研究,主要工作分为三个部分:
(1)建立了基于PDM任务指派问题的数学模型,目标是确定最优的指派方案,使项目组的有限设计资源得到合理利用。
(2)分别从宏观和微观上改进了遗传算法,在宏观上引入了循环策略和模拟退火算法,在微观上针对基于PDM任务指派问题数学模型的特点对编码的方式、解码的规则以及遗传算子进行了改进,提出了一种间接编码的混合遗传算法,并对该混合遗传算法的染色体编码方案、解码规则、适值函数和遗传算子等进行了详细设计。
(3)在运用Camel函数和Shubert函数验证了采用循环策略的模拟退火遗传算法性能的基础上,针对提出的间接编码的混合遗传算法,通过一个应用实例,分析并验证了基于PDM任务指派问题的模型和间接编码的混合遗传算法解决该问题的有效性。
Product Data Management (PDM) is a kind of technology which concentrates on products of manufacturing enterprises. It manages both the data to describe products and the developing process of products based on computer network and database technology.
In recent years there are many literatures relating to research of PDM technology. Most of them concern on the architecture of PDM, models of product data, development of software system, implementation methodology and integration interface, etc. The optimization problems of key processes in PDM are seldom studied, for example, research of the task assignment problem based on PDM. The solution of the task assignment problem in PDM may provide theoretical and algorithmic support for kernel design and development of PDM system. It is meaningful for improving design and manufacturing efficiency in enterprises.
In this paper, we discuss modeling and optimization for the design task assignment problem of project management in PDM based on genetic algorithms. The main content includes three aspects as follows:
(1) A mathematical model of the task assignment problem in PDM is established, the objective is to obtain the optimal assignment scheme and to enable the efficient allocation of limited design resources.
(2)The thesis proposes two ways of macroscopic and microscopic respectively in order to improve the performance of the genetic algorithm. In macroscopic aspect, the circular strategy and simulated annealing algorithm are introduced, and in microscopic aspect, the encoding scheme, decoding rule and genetic operators are improved for the mathematical model of task assignment problem in PDM. Then, we propose a kind of indirect hybrid genetic algorithm. Finally, a kind of encoding scheme, decoding rule, fitness function and genetic operators are designed in detail.
(3)Based on using Camel function and the Shubert function to test the performance of the simulated annealing genetic algorithm adopting circular strategy, test was carried through an application example of the task assignment problem based on PDM. The experimental results show that the model and the indirect hybrid genetic algorithm has great effectiveness.
引文
[1].童秉枢,李建明.产品数据管理(PDM)技术[M].北京:清华大学出版社, 2000: 6--7.
[2].陈宇红.产品数据管理系统的功能分析与技术实施[J].机电工程技术, 2001, 2 (3): 29--31.
[3].卢有杰,王勇.项目管理知识体系指南(第3版) [M].北京:电子工业出版社, 2005: 17--21.
[4].田俊国.项目管理的概念及项目的过程管理[J].计算机世界, 2006, 4 (25): 87--92.
[5].李彦强.面向网络化制造的分布式项目管理系统研究: [硕士学位论文].浙江:浙江大学, 2005.
[6].万立,乔新愚,吴义忠. PDM中多资源约束下的项目管理技术[J].计算工程与应用, 2004, 17 (10): 214--217.
[7].毕星,翟丽.项目管理[M].上海:复旦大学出版社, 2000: 7--11.
[8].李建明,童秉枢,许隆文.产品数据管理技术的现状与发展[J].计算机集成制造系统, 1998, 4 (6): 23--30.
[9].约瑟夫.萧塔纳.制造企业的产品数据管理[M].北京:机械工业出版社, 2000: 15--19.
[10].雒兴刚.产品数据管理(PDM)中若干关键优化问题的研究: [博士学位论文].沈阳:东北大学, 2006.
[11]. Yanping ZHANG,Chun ZHANG. Interoperation of Step Application Protocols for Product Data Management[J]. Concurrent Engineering Research and Applications, 1998, 6 (2): 161--169.
[12]. Wiebe E N. Adding Agility to CAD Integrating Product Data Management Tools into An Organization[J]. Human Factors and Ergonomics in Manufacturing, 1997, 7 (1): 21--35.
[13].郭阳,杨军,陈旭灿,李思昆.基于设计体模型的产品数据管理技术[J].国防科技大学学报, 1998, 20 (3): 53--56.
[14].韩鑫,王建民,孙家广.产品数据管理系统的构造框架和实现方法[J].软件学报, 1998, 12 (12): 881--883.
[15]. Sackett P J,Bryan M G. Framework for the Development of A Product Data Management Strategy[J]. International Journal of Operations & Production Management, 1998, 18 (2): 168--179.
[16]. Vandenhamer Peter,Lepoeter Kees. Configuration Management and Product Data Management[J]. Proceedings of the IEEE, 1996, 84 (1): 42--56.
[17]. Harris S B. A Literature Review and Summary of the Emerging Research Questions[J]. Journal of Engineering Manufacture, 1996, 210 (3): 207--220.
[18]. Philpotts M. An Introduction to the Concepts and Terminology of Product Data Management[J]. Industrial Management Data Systems, 1996, 96 (4): 11--17.
[19]. Kay C,Madden D. Critical Success Factors in Implementing Product Data Management[J]. International Journal of Micrographics and Optical Technology, 1995, 13 (4): 191--194.
[20]. Siegel Jeff. Hands-on Product Data Management[J]. Computer-Aided Engineering, 1995, 14 (2): 42--43.
[21]. Bourke R W,Miller E D. Product Data Management Systems-Evaluating Your Needs[J]. P & IM Review and APICS News, 1991, 11 (4): 38--40.
[22].纪丰伟,陈恳.基于PDM平台的任务调度技术研究[J].计算机集成制造系统, 2002, 8 (7): 511--521.
[23].肖继先,韩润春.一类非确定型指派问题及其解法[J].工业技术经济,2005, 17 (4): 181--184.
[24]. Drezner Z. The Extended Concentric Tabu for the Quadratic Assignment Problem[J]. European Journal of Operational Research, 2005, 160 (3): 416--422.
[25]. Liu L Z. The Fuzzy Quadratic Assignment Problem with Penalty:New Models and Genetic Algorithm[J]. Applied Mathematics and Computation, 2006, 174 (21): 1229--1244.
[26]. Ahuja R,Orlin J,Tiwari A. A Greedy Genetic Algorithm for the Quadratic Assignment Problem[J]. Computers and Operations Research, 2000, 27 (9): 917--934.
[27]. Lin C,Wen U. A Labelling Algorithm for the Fuzzy Assignment Problem[J]. Fuzzy Sets and Systems, 2004, 142 (11): 373--391.
[28]. Bogomolnaia A. A New Solution to the Random Assignment Problem[J]. Journal of Economic Theory, 2001, 100 (39): 295--328.
[29]. Jian CAO,Youliang ZHANG,Haiyan ZHAO,Shuangxi HUANG. Research on Dynamic Assignment of Design Tasks[J]. Journal of Computer Aided Design & Computer Graphics, 1999, 11 (2): 168--171.
[30]. Liu B,Iwamura K. A Note on Chance Constrained Programming with Fuzzy Coefficients[J]. Fuzzy Sets and Systems, 1998, 100 (19): 229--233.
[31].杨波,黄克正,孙红卫.面向并行工程的任务分配与规划[J].计算机集成制造系统, 2002, 8 (7): 542--560.
[32].雒兴刚,汪定伟,唐加福.产品数据管理中任务指派问题的模型和算法[J].系统工程学报, 2007, 22 (5): 467--473.
[33].孙福权,郑秉霖,崔建江.炼钢热轧一体化管理的生产计划编制问题研究[J].自动化学报, 2000, 26 (3): 409--410.
[34]. Misevicius A. An Improved Hybrid Genetic Algorithm: New Results for theQuadratic Assignment Problem[J]. Knowledge-Based Systems, 2004, 17 (6): 65--73.
[35].李爱国,覃征,鲍复民.粒子群优化算法[J].计算机工程与应用, 2002, 38 (21): 69--74.
[36]. Li Y,Ida K, Gen M. Neural Network Approach for Multicriteria Solid Transportation Problem[J]. Computers and Industrial Engineering, 1997, 33 (19): 465--468.
[37].朱求长.运筹学及其应用[M].武汉:武汉大学出版社, 2002: 197--201.
[38]. Hartmann S. A Competitive Genetic Algorithm for Resource-Constrained Project Scheduling[J]. Naval Research Logistics, 1998, 45 (7): 733--750.
[39]. Hartmann S. A Self-Adapting Genetic Algorithm for Project Scheduling under Resource Constraints[J]. Naval Research Logistics, 2002, 49 (5): 433--448.
[40]. Holland J H. Adaptation in Nature and Artificial Systems[M]. Ann Arbor: The University of Michigen Press, 1995: 11--17.
[41].王小平,曹立明.遗传算法理论、应用与软件实现[M].西安:西安交通大学出版社, 2002: 9--17.
[42].周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社, 1999: 19--31.
[43].刘振宏,蔡茂诚.组合优化算法和复杂性[M].北京:清华大学出版社, 1998: 47--53.
[44].吴少岩,许卓群.遗传算法中遗传算子的启发式构造策略[J].软件学报, 1998, 21 (11): 1003--1008.
[45].田东平,迟洪钦.混合遗传算法与模拟退火算法[J].计算机工程与应用, 2006, 42 (22): 63--65.
[46].乔超,唐慧佳,王春红.一种基于选择的遗传算法[J].计算机工程与应用, 2007, 43 (1): 70--73.
[47].吴柯.一类高效的混合遗传算法[J].计算机与数字工程, 2006, 34 (10): 43--45.
[48].张进社,徐宗本,梁怡.整体退火遗传算法及其收敛充要条件[J].中国科学(E辑), 1997, 27 (2): 154--164.
[49].孙德宝.自适应最优保存的模拟退火遗传算法及应用[J].华中科技大学学报, 2007, 13 (5): 46--47.
[50].玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社, 2000: 142--151.
[51].玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社, 2000: 15--21.
[52].姚俊峰,梅炽,彭小奇.混沌遗传算法及其应用[J].系统工程, 2001, 119 (1): 70--74.
[2].陈宇红.产品数据管理系统的功能分析与技术实施[J].机电工程技术, 2001, 2 (3): 29--31.
[3].卢有杰,王勇.项目管理知识体系指南(第3版) [M].北京:电子工业出版社, 2005: 17--21.
[4].田俊国.项目管理的概念及项目的过程管理[J].计算机世界, 2006, 4 (25): 87--92.
[5].李彦强.面向网络化制造的分布式项目管理系统研究: [硕士学位论文].浙江:浙江大学, 2005.
[6].万立,乔新愚,吴义忠. PDM中多资源约束下的项目管理技术[J].计算工程与应用, 2004, 17 (10): 214--217.
[7].毕星,翟丽.项目管理[M].上海:复旦大学出版社, 2000: 7--11.
[8].李建明,童秉枢,许隆文.产品数据管理技术的现状与发展[J].计算机集成制造系统, 1998, 4 (6): 23--30.
[9].约瑟夫.萧塔纳.制造企业的产品数据管理[M].北京:机械工业出版社, 2000: 15--19.
[10].雒兴刚.产品数据管理(PDM)中若干关键优化问题的研究: [博士学位论文].沈阳:东北大学, 2006.
[11]. Yanping ZHANG,Chun ZHANG. Interoperation of Step Application Protocols for Product Data Management[J]. Concurrent Engineering Research and Applications, 1998, 6 (2): 161--169.
[12]. Wiebe E N. Adding Agility to CAD Integrating Product Data Management Tools into An Organization[J]. Human Factors and Ergonomics in Manufacturing, 1997, 7 (1): 21--35.
[13].郭阳,杨军,陈旭灿,李思昆.基于设计体模型的产品数据管理技术[J].国防科技大学学报, 1998, 20 (3): 53--56.
[14].韩鑫,王建民,孙家广.产品数据管理系统的构造框架和实现方法[J].软件学报, 1998, 12 (12): 881--883.
[15]. Sackett P J,Bryan M G. Framework for the Development of A Product Data Management Strategy[J]. International Journal of Operations & Production Management, 1998, 18 (2): 168--179.
[16]. Vandenhamer Peter,Lepoeter Kees. Configuration Management and Product Data Management[J]. Proceedings of the IEEE, 1996, 84 (1): 42--56.
[17]. Harris S B. A Literature Review and Summary of the Emerging Research Questions[J]. Journal of Engineering Manufacture, 1996, 210 (3): 207--220.
[18]. Philpotts M. An Introduction to the Concepts and Terminology of Product Data Management[J]. Industrial Management Data Systems, 1996, 96 (4): 11--17.
[19]. Kay C,Madden D. Critical Success Factors in Implementing Product Data Management[J]. International Journal of Micrographics and Optical Technology, 1995, 13 (4): 191--194.
[20]. Siegel Jeff. Hands-on Product Data Management[J]. Computer-Aided Engineering, 1995, 14 (2): 42--43.
[21]. Bourke R W,Miller E D. Product Data Management Systems-Evaluating Your Needs[J]. P & IM Review and APICS News, 1991, 11 (4): 38--40.
[22].纪丰伟,陈恳.基于PDM平台的任务调度技术研究[J].计算机集成制造系统, 2002, 8 (7): 511--521.
[23].肖继先,韩润春.一类非确定型指派问题及其解法[J].工业技术经济,2005, 17 (4): 181--184.
[24]. Drezner Z. The Extended Concentric Tabu for the Quadratic Assignment Problem[J]. European Journal of Operational Research, 2005, 160 (3): 416--422.
[25]. Liu L Z. The Fuzzy Quadratic Assignment Problem with Penalty:New Models and Genetic Algorithm[J]. Applied Mathematics and Computation, 2006, 174 (21): 1229--1244.
[26]. Ahuja R,Orlin J,Tiwari A. A Greedy Genetic Algorithm for the Quadratic Assignment Problem[J]. Computers and Operations Research, 2000, 27 (9): 917--934.
[27]. Lin C,Wen U. A Labelling Algorithm for the Fuzzy Assignment Problem[J]. Fuzzy Sets and Systems, 2004, 142 (11): 373--391.
[28]. Bogomolnaia A. A New Solution to the Random Assignment Problem[J]. Journal of Economic Theory, 2001, 100 (39): 295--328.
[29]. Jian CAO,Youliang ZHANG,Haiyan ZHAO,Shuangxi HUANG. Research on Dynamic Assignment of Design Tasks[J]. Journal of Computer Aided Design & Computer Graphics, 1999, 11 (2): 168--171.
[30]. Liu B,Iwamura K. A Note on Chance Constrained Programming with Fuzzy Coefficients[J]. Fuzzy Sets and Systems, 1998, 100 (19): 229--233.
[31].杨波,黄克正,孙红卫.面向并行工程的任务分配与规划[J].计算机集成制造系统, 2002, 8 (7): 542--560.
[32].雒兴刚,汪定伟,唐加福.产品数据管理中任务指派问题的模型和算法[J].系统工程学报, 2007, 22 (5): 467--473.
[33].孙福权,郑秉霖,崔建江.炼钢热轧一体化管理的生产计划编制问题研究[J].自动化学报, 2000, 26 (3): 409--410.
[34]. Misevicius A. An Improved Hybrid Genetic Algorithm: New Results for theQuadratic Assignment Problem[J]. Knowledge-Based Systems, 2004, 17 (6): 65--73.
[35].李爱国,覃征,鲍复民.粒子群优化算法[J].计算机工程与应用, 2002, 38 (21): 69--74.
[36]. Li Y,Ida K, Gen M. Neural Network Approach for Multicriteria Solid Transportation Problem[J]. Computers and Industrial Engineering, 1997, 33 (19): 465--468.
[37].朱求长.运筹学及其应用[M].武汉:武汉大学出版社, 2002: 197--201.
[38]. Hartmann S. A Competitive Genetic Algorithm for Resource-Constrained Project Scheduling[J]. Naval Research Logistics, 1998, 45 (7): 733--750.
[39]. Hartmann S. A Self-Adapting Genetic Algorithm for Project Scheduling under Resource Constraints[J]. Naval Research Logistics, 2002, 49 (5): 433--448.
[40]. Holland J H. Adaptation in Nature and Artificial Systems[M]. Ann Arbor: The University of Michigen Press, 1995: 11--17.
[41].王小平,曹立明.遗传算法理论、应用与软件实现[M].西安:西安交通大学出版社, 2002: 9--17.
[42].周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社, 1999: 19--31.
[43].刘振宏,蔡茂诚.组合优化算法和复杂性[M].北京:清华大学出版社, 1998: 47--53.
[44].吴少岩,许卓群.遗传算法中遗传算子的启发式构造策略[J].软件学报, 1998, 21 (11): 1003--1008.
[45].田东平,迟洪钦.混合遗传算法与模拟退火算法[J].计算机工程与应用, 2006, 42 (22): 63--65.
[46].乔超,唐慧佳,王春红.一种基于选择的遗传算法[J].计算机工程与应用, 2007, 43 (1): 70--73.
[47].吴柯.一类高效的混合遗传算法[J].计算机与数字工程, 2006, 34 (10): 43--45.
[48].张进社,徐宗本,梁怡.整体退火遗传算法及其收敛充要条件[J].中国科学(E辑), 1997, 27 (2): 154--164.
[49].孙德宝.自适应最优保存的模拟退火遗传算法及应用[J].华中科技大学学报, 2007, 13 (5): 46--47.
[50].玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社, 2000: 142--151.
[51].玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社, 2000: 15--21.
[52].姚俊峰,梅炽,彭小奇.混沌遗传算法及其应用[J].系统工程, 2001, 119 (1): 70--74.