面向大规模定制的装配线优化调度研究

针对大规模定制生产模式下汽车装配线调度存在的问题,提出一种多目标优化调度的方法,设计了相应的目标函数。提出一种多目标遗传算法,设计了相应的编码、选择和交换方案,在算法实现中对精英策略和选择机制进行了改进。仿真实验说明该算法可行有效,优于VEGA、PGA和NPGA等其他遗传算法。     

Development of a multiobjective GA for advanced planning and scheduling problem

In this paper, we consider an advanced planning and scheduling (APS) problem in manufacturing supply chain. The problem was formulated with mixed integer programming and three objectives are taken into account. To solve the APS model, a multiobjective genetic algorithm with local search is presented to find the Pareto optimal solutions. The proposed algorithm makes use of the principle of nondominated sorting, coupled with the use of a metric for normalized crowding distance. Local search technique is used to improve the efficiency. The proposed algorithm was compared with two other multiobjective genetic algorithms from the literature. Performance of these heuristics has been tested on ten problems in three scenarios. The computational results demonstrate the effectiveness and efficiency of the proposed approach and indicate that the presented algorithm outperforms previous work for APS problems.     

Multi-objective optimization and evaluation method of modular product configuration design scheme

Product configuration is one of the key technologies for mass customization. Traditional product configuration optimization targets are mostly single. In this paper, an approach based on multi-objective genetic optimization algorithm and fuzzy-based select mechanism is proposed to solve the multi-objective configuration optimization problem. Firstly, the multi-objective optimization mathematical model of product configuration is constructed, the objective functions are performance, cost, and time. Then, a method based on improved non-dominated sorting genetic algorithm (NSGA-II) is proposed to solve the configuration design optimization problem. As a result, the Pareto-optimal set is acquired by NSGA-II. Due to the imprecise nature of human decision, a fuzzy-based configuration scheme evaluation and select mechanism is proposed consequently, which helps extract the best compromise solution from the Pareto-optimal set. The proposed multi-objective genetic algorithm is compared with two other established multi-objective optimization algorithms, and the results reveal that the proposed genetic algorithm outperforms the others in terms of product configuration optimization problem. At last, an example of air compressor multi-objective configuration optimization is used to demonstrate the feasibility and validity of the proposed method.     

基于多目标遗传算法的产品优化配置研究

针对产品配置设计存在的问题，提出一种基于多目标遗传算法的产品优化配置方法，设计了相应编码解码方案和适应度计算方法，在具体算法中，对小生境的范围确定和精英策略提出改进。仿真实验证明，该算法可行有效，优于其他遗传算法。     

Parallel genetic algorithms for product configuration management on PC cluster systems

This work presents two parallel genetic algorithms (PGAs) for product configuration management: a parallel conventional genetic algorithm (PCGA) and a parallel multiple-searching genetic algorithm (PMGA). This parallel/distributed approach is based on a coarse-grained (or island) paradigm which is implemented on a cluster of PCs using message passing interface for the genetic information interchange. The product configuration problem assuming that customers would like to have minimum cost and a customized product can be obtained by finding the shortest path of the configuration network diagram. The performance of these algorithms is estimated by comparing the solutions of PGAs with those of sequential genetic algorithms (GAs) and mathematical programming. A weighting scale example from an empirical study is reported for illustrational purposes. Computational results show that the solutions obtained from the PMGA outperform other GAs in both accuracy and efficiency.     

Green partner selection in virtual enterprise based on Pareto genetic algorithms

The partner selection problem (PSP) in virtual enterprise has been comprehensively investigated from the aspects of research fields, contents, attributes or criteria been considered, and algorithms. With the consideration of environmental protection, the importance of “green criteria” in PSP is introduced, and two new green criteria, i.e., carbon emission and lead content in manufacturing production, are firstly brought into PSP. A formulation of PSP with green criteria is established which includes four objectives and six constraints. A new improved algorithm, named Pareto genetic algorithm for PSP (Pareto-PSGA), is designed for addressing the specific PSP. With Pareto solution ideas, vector encoding, random selection, two-point crossover, and single-point mutation for Pareto solutions are designed in the Pareto-PSGA. Experimental results demonstrate that compared with other typical intelligent algorithms such as simulated annealing and particle swarm optimization, Pareto-PSGA shows high performance in solving the specific PSP with more suitable Pareto solutions in shorter time.     

Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems

This paper presents a hybrid Pareto-based discrete artificial bee colony algorithm for solving the multi-objective flexible job shop scheduling problem. In the hybrid algorithm, each solution corresponds to a food source, which composes of two components, i.e., the routing component and the scheduling component. Each component is filled with discrete values. A crossover operator is developed for the employed bees to learn valuable information from each other. An external Pareto archive set is designed to record the non-dominated solutions found so far. A fast Pareto set update function is introduced in the algorithm. Several local search approaches are designed to balance the exploration and exploitation capability of the algorithm. Experimental results on the well-known benchmark instances and comparisons with other recently published algorithms show the efficiency and effectiveness of the proposed algorithm.     

Metaheuristic approaches to sequencing mixed-model fabrication/assembly systems with two objectives

This paper is concerned about the sequencing problems in pull production systems which are composed of one mixed-model assembly line and one flexible fabrication flow line with limited intermediate buffers. Two objectives are considered simultaneously: minimizing the total variation in parts consumption in the assembly line and minimizing the makespan in the fabrication line. The mathematical models are presented. Since the problem is Non-deterministic Polynomial-hard (NP-hard), a multiobjective genetic algorithm is proposed for solving the models, in which a method to generate the production sequence for the fabrication line from the production sequence for the assembly line is put forward, and Pareto ranking method and sharing function method are employed to evaluate the individuals' fitness. The feasibility and efficiency of the multiobjective genetic algorithm is shown by computational comparison with an adaptive genetic algorithm and a multiobjective simulated annealing.     

多目标免疫遗传算法性能分析及其在柔性作业车间调度中的应用

讨论了一种多目标免疫遗传算法的收敛性和多样性。首先,提出了一种集成免疫思想和遗传算法的多目标优化算法;接着,采用马尔可夫链对算法的收敛性进行了定量分析,证明该算法能以概率1收敛到Pareto最优解集;定性分析了算法的多样性保持策略。最后,结合某柔性车间调度问题的实例,验证了算法的良好收敛性和多样性。     

A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs

In this paper the problem of permutation flow shop scheduling with the objectives of minimizing the makespan and total flow time of jobs is considered. A Pareto-ranking based multi-objective genetic algorithm, called a Pareto genetic algorithm (GA) with an archive of non-dominated solutions subjected to a local search (PGA-ALS) is proposed. The proposed algorithm makes use of the principle of non-dominated sorting, coupled with the use of a metric for crowding distance being used as a secondary criterion. This approach is intended to alleviate the problem of genetic drift in GA methodology. In addition, the proposed genetic algorithm maintains an archive of non-dominated solutions that are being updated and improved through the implementation of local search techniques at the end of every generation. A relative evaluation of the proposed genetic algorithm and the existing best multi-objective algorithms for flow shop scheduling is carried by considering the benchmark flow shop scheduling problems. The non-dominated sets obtained from each of the existing algorithms and the proposed PGA-ALS algorithm are compared, and subsequently combined to obtain a net non-dominated front. It is found that most of the solutions in the net non-dominated front are yielded by the proposed PGA-ALS.     

An effective multi-objective genetic algorithm based on immune principle and external archive for multi-objective integrated process planning and scheduling

Process planning and scheduling are two major sub-systems in a modern manufacturing system. In traditional manufacturing system, they were regarded as the separate tasks to perform sequentially. However, considering their complementarity, integrating process planning and scheduling can further improve the performance of a manufacturing system. Meanwhile, the multiple objectives are needed to be considered during the realistic decision-making process in a manufacturing system. Based on the above requirements from the real manufacturing system, developing effective methods to deal with the multi-objective integrated process planning and scheduling (MOIPPS) problem becomes more and more important. Therefore, this research proposes a multi-objective genetic algorithm based on immune principle and external archive (MOGA-IE) to solve the MOIPPS problem. In MOGA-IE, the fast non-dominated sorting approach used in NSGA-II is utilized as the fitness assignment scheme and the immune principle is exploited to maintain the diversity of the population and prevent the premature condition. Moreover, the external archive is employed to store and maintain the Pareto solutions during the evolutionary process. Effective genetic operators are also designed for MOIPPS. To test the performance of the proposed algorithm, three different scale instances have been employed. And the proposed method is also compared with other previous algorithms in literature. The results show that the proposed algorithm has achieved good improvement and outperforms the other algorithms.     

基于双层配置体系的产品配置算法研究

在大规模定制生产模式下,产品配置遇到了复杂模糊配置数据的处理问题,为此,提出了基于实例重用的产品配置模糊求解技术,设计了基于多目标遗传算法的产品配置优化算法.将产品配置过程划分为部件配置与零件配置两部分,利用典型条件概率解决产品配置领域的部件模糊配置问题,设计了基于非支配排序遗传算法-Ⅱ,求解以成本、时间和库存为优化目标的零件配置,并结合两者建立完整的产品配置求解算法体系.该算法有效地解决了复杂产品配置中模糊数据处理及配置组合爆炸的问题.     

A novel hybrid multi-objective shuffled frog-leaping algorithm for a bi-criteria permutation flow shop scheduling problem

This paper investigates a novel multi-objective model for a permutation flow shop scheduling problem that minimizes both the weighted mean earliness and the weighted mean tardiness. Since a flow shop scheduling problem has been proved to be NP-hard in a strong sense, a new hybrid multi-objective algorithm based on shuffled frog-leaping algorithm (SFLA) and variable neighborhood search (VNS) is devised to find Pareto optimal solutions for the given problem. To validate the performance of the proposed hybrid multi-objective shuffled frog-leaping algorithm (HMOSFLA) in terms of solution quality and diversity level, various test problems are examined. Further, the efficiency of the proposed algorithm, based on various salient metrics, is compared against two well-known multi-objective genetic algorithms: NSGA-II and SPEA-II. Our computational results suggest that the proposed HMOSFLA outperforms the two foregoing algorithms, especially for large-sized problems.     

Multidimensional visualization and clustering for multiobjective optimization of artificial satellite heat pipe design

This study presents a newly developed approach for visualization of Pareto and quasi-Pareto solutions of a multiobjective design problem for the heat piping system in an artificial satellite. Given conflicting objective functions, multiobjective optimization requires both a search algorithm to find optimal solutions and a decision-making process for finalizing a design solution. This type of multiobjective optimization problem may easily induce equally optimized multple solutions such as Pareto solutions, quasi-Pareto solutions, and feasible solutions. Here, a multidimensional visualization and clustering technique is used for visualization of Pareto solutions. The proposed approach can support engineering decisions in the design of the heat piping system in artificial satellites. Design considerations for heat piping system need to simultaneously satisfy dual conditions such as thermal robustness and overall limitation of the total weight of the system. The proposed visualization and clustering technique can be a valuable design tool for the heat piping system, in which reliable decision-making has been frequently hindered by the conflicting nature of objective functions in conventional approaches.     

Multiobjective optimization of injection molding parameters based on soft computing and variable complexity method

The objective of this study is to propose an intelligent methodology for efficiently optimizing the injection molding parameters when multiple constraints and multiple objectives are involved. Multiple objective functions reflecting the product quality, manufacturing cost and molding efficiency were constructed for the optimization model of injection molding parameters while multiple constraint functions reflecting the requirements of clients and the restrictions in the capacity of injection molding machines were established as well. A novel methodology integrating variable complexity methods (VCMs), constrained non-dominated sorted genetic algorithm (CNSGA), back propagation neural networks (BPNNs) and Moldflow analyses was put forward to locate the Pareto optimal solutions to the constrained multiobjective optimization problem. The VCMs enabled both the knowledge-based simplification of the optimization model and the variable-precision flow analyses of different injection molding parameter schemes. The Moldflow analyses were applied to collect the precise sample data for developing BPNNs and to fine-tune the Pareto-optimal solutions after the CNSGA-based optimization while the approximate BPNNs were utilized to efficiently compute the fitness of every individual during the evolution of CNSGA. The case study of optimizing the mold and process parameters for manufacturing mice with a compound-cavity mold demonstrated the feasibility and intelligence of proposed methodology.     

基于DNA遗传算法求解机床加工调度问题

研究了机床加工的多目标调度问题,提出一种基于DNA计算的混合遗传算法,结合Pareto非支配排序法来求解。为保证最优解集的多样性,采用四进制编码方式,将DNA序列分成中性和有害两部分,交叉操作只在中性部分进行;由动态变化的变异概率决定是否执行变异操作,并比较设计的算法与常规遗传算法获得的结果。试验结果表明,可以有效地解决机床加工中的多目标调度问题。     

Evolutionary bi-criteria optimum design of robots based on task specifications

The optimum robot structure design problem based on task specifications is an important one, since it has greater influence on manipulator workspace design, vibrations of the manipulator during operation, manipulator efficiency in the work environment and power consumption. In this paper, an optimization robot structure problem is formulated with the objective of determining the optimal geometric dimensions of the robot manipulators considering the task specifications (pick and place operation). The aim is to minimize torque required for motion and maximize manipulability measure of the robot subject to dynamic, kinematic, deflection and structural constraints with link physical characteristics (length and cross-sectional area parameters) as design variables. In this work, five different cross-sections (hollow circle, hollow square, hollow rectangle, C-channel and I-channel) have been experimented for the link. Three evolutionary optimization algorithms namely multi-objective genetic algorithm (MOGA), elitist nondominated sorting genetic algorithm (NSGA-II) and multi-objective differential evolution (MODE) are used for the optimum structural design of 2-link and 3-link planar robots. Two methods (normalized weighting objective functions and average fitness factor) are used to select the best optimal solution. Two multiobjective performance measures namely solution spread measure and ratio of non-dominated individuals are used to evaluate the Pareto optimal fronts. Two more multiobjective performance measures namely optimiser overhead and algorithm effort, are used to find computational effort of optimization algorithm. The results obtained from various techniques are compared and analyzed.     

基于有约束多目标进化算法的冷轧负荷分配分析

冷轧负荷分配问题可以抽象为一个有约束多目标优化问题。为解决此问题,提出了基于环境Pareto支配选择策略的有约束多目标进化算法。该算法更加客观地评价了两个不同解的优劣,利用优秀不可行解加速算法收敛。以等功率裕量、最小轧制能耗、最小综合打滑函数、末机架板形良好轧制力为优化目标,利用有约束多目标进化算法得到了4个目标函数之间的定量关系,使决策者不需要掌握复杂的轧制理论知识就可以直观地掌握轧制规律,并进一步说明了多目标策略在压下负荷分配中的必要性。     

考虑布局熵的多态性车间布局稳健优化模型与算法

为满足大规模定制和产业集群下多品种、小批量的市场需求和订单动态波动的客户需求以及车间低成本、高稳健性的布局要求,设计了以单位面积布置成本、单位产品物流成本和布局熵为优化指标的多目标布局优化模型。提出了基于Pareto优化的聚类并行多目标遗传算法,引入模糊C-均值聚类算法以提高Pareto解集分布的多样性与均匀性,设计了多元胞差分进化重插入操作与基于“精英策略”的移民操作,增强了算法全局与局部搜索能力,有效避免了早熟现象。通过典型算例对比,验证了模型和算法的有效性;同时在企业布局实例应用中,获得了既能满足低成本又能将布局熵值控制在理想范围内的车间布局方案,表明模型具有良好的实用性。     

Multiobjective trajectory optimization of intelligent electro-hydraulic shovel

Multiobjective trajectory planning is still face challenges due to certain practical requirements and multiple contradicting objectives optimized simultaneously. In this paper, a multiobjective trajectory optimization approach that sets energy consumption, execution time, and excavation volume as the objective functions is presented for the electro-hydraulic shovel (EHS). The proposed cubic polynomial S-curve is employed to plan the crowd and hoist speed of EHS. Then, a novel hybrid constrained multiobjective evolutionary algorithm based on decomposition is proposed to deal with this constrained multiobjective optimization problem. The normalization of objectives is introduced to minimize the unfavorable effect of orders of magnitude. A novel hybrid constraint handling approach based on ε-constraint and the adaptive penalty function method is utilized to discover infeasible solution information and improve population diversity. Finally, the entropy weight technique for order preference by similarity to an ideal solution method is used to select the most satisfied solution from the Pareto optimal set. The performance of the proposed strategy is validated and analyzed by a series of simulation and experimental studies. Results show that the proposed approach can provide the high-quality Pareto optimal solutions and outperforms other trajectory optimization schemes investigated in this article.