基于图论的可重构制造系统单零件流水线构形优化  

Optimization for single-part flow-line configurations of reconfigurable manufacturing system based on graph theory

作　　者：窦建平[1] 戴先中[1] 孟正大[1] 李俊[1] 

机构地区：[1]东南大学自动化学院复杂工程系统测量与控制教育部重点实验室,江苏南京210096

出　　处：《计算机集成制造系统》2010年第1期81-89,共9页Computer Integrated Manufacturing Systems

基　　金：国家973计划资助项目(2002CB312204)~~

摘　　要：获取各生产周期内的最优和K-1个次优(K优)单零件流水线构形,是可重构制造系统构形选择中一个重要的优化问题。给定零件的工序优先图、工序和工位操作的关系以及各工位操作的可选设备,该流水线构形优化问题即确定工作站数量,选择各工作站内的机床类型和数量,选择并分配工位操作,以最小化流水线构形的资本成本。将寻求满足功能和产能约束、空间约束和投资限制的K优构形问题建模为关联所有可行工位操作序列的复合增广有向图上的约束K最短路径问题,获得K优解。最后,通过案例研究验证了该方法的有效性和优越性。Generating the optimal and K-1 suboptimal（K-best） Single-Part Flow-Line（SPFL） configurations within a specified Demand Period（DP） is an important optimization problem during configuration selection for Reconfigurable Manufacturing System（RMS）.By specifying the opertaion precedence graph for a part,relationships between operations and Operation Setups（OSs） as well as machining options for each OS,the optimization problem was to determine the number of workstations,select machine type and number of parallel machines for each workstation as well as assign OSs for each workstation.The objective was to minimize capital cost of SPFL configurations.Generation of K-best configurations subject to constraints on space,initial investment,functionality and capacity was modeled as a Constrained K-Shortest Paths（CKSP） problem on an combined augmented acyclic graph associated with all feasible OS sequences.Subsequently,K-best configurations were obtainted by a CKSP algorithm.Finally,a case study illustrated the effectiveness and advantages of the proposed model and solution method.

关 键 词：可重构制造系统 构形优化 流水线 图论 约束K最短路径 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TH165[自动化与计算机技术—计算机科学与技术]