An adaptive genetic algorithm approach for the mixed-model assembly line sequencing problem

A mixed-model assembly line (MMAL) is a type of production line that is capable of producing a variety of different product models simultaneously and continuously. The design and planning of such lines involve several long- and short-term problems. Among these problems, determining the sequence of products to be produced has received considerable attention from researchers. This problem is known as the Mixed-Model Assembly Line Sequencing Problem (MMALSP). This paper proposes an adaptive genetic algorithm approach to solve MMALSP where multiple objectives such as variation in part consumption rates, total utility work and setup costs are considered simultaneously. The proposed approach integrates an adaptive parameter control (APC) mechanism into a multi-objective genetic algorithm in order to improve the exploration and exploitation capabilities of the algorithm. The APC mechanism decides the probability of mutation and the elites that will be preserved for succeeding generations, all based on the feedback obtained during the run of the algorithm. Experimental results show that the proposed adaptive GA-based approach outperforms the non-adaptive algorithm in both solution quantity and quality.     

Non-dominated ranked genetic algorithm for a multi-objective mixed-model assembly line sequencing problem

The increasing market demand for product variety forces manufacturers to design mixed-model assembly lines (MMAL) on which a variety of product models similar to product characteristics are assembled. This paper presents a method combining the new ranked based roulette wheel selection algorithm with Pareto-based population ranking algorithm, named non-dominated ranking genetic algorithm (NRGA) to a just-in-time (JIT) sequencing problem when two objectives are considered simultaneously. The two objectives are minimisation the number of setups and variation of production rates. This type of problem is NP-hard. Various operators and parameters of the proposed algorithm are reviewed to calibrate the algorithm by means of the Taguchi method. The solutions obtained via NRGA are compared against solutions obtained via total enumeration (TE) scheme in small problems and also against four other search heuristics in small, medium and large problems. Experimental results show that the proposed algorithm is competitive with these other algorithms in terms of quality and diversity of solutions.     

基于传统遗传算法的改进排爆机器人路径规划研究

针对传统遗传算法进化速度慢、容易陷入局部最优点等缺陷,提出了改进后新的路径规划算法。在判断路径中,基于闵科夫斯基原理对障碍物进行扩展;在构造路径中基于可视图原理进行改进,构造机器人的真正可行区域;在最短路径中对遗传算法中种群的初始化,个体的编码方法等问题做了详细的研究,并在选择算子中引入相似度的概念,大大扩大了初始种群的范围,避免进入局部最优点。最后通过仿真实验验证了此算法的可行性。     

A modified multi-objective genetic algorithm for two-sided assembly line re-balancing problem of a shovel loader

This article deals with a real-life multi-objective two-sided assembly line rebalancing problem (MTALRBP) with modifications of production demand, line’s structure and production process in a Chinese construction machinery manufacturing firm. The objectives are minimising the cycle time and rebalancing cost, considering some specific constraints associated with the inevitable wait time, such as novel cycle time, idle time and balanced constraints. A modified non-dominated sorting genetic algorithm II (MNSGA-II) is proposed to solve this problem. MNSGA-II employs some problem-specific designs for encoding and decoding, initial population, crossover operator, mutation operator and selection operator. The great performance of MNSGA-II is demonstrated from two aspects: one is through the comparison between the representative results and current situation in the production system in terms of some ALs’ performance evaluation index, the other is utilising the comparison between the proposed MNSGA-II and two versions of initial NSGA-II in terms of ratio, convergence and spread.     

An improved NSGA-II algorithm for multi-objective lot-streaming flow shop scheduling problem

Crossover and mutation operators in NSGA-II are random and aimless, and encounter difficulties in generating offspring with high quality. Aiming to overcoming these drawbacks, we proposed an improved NSGA-II algorithm (INSGA-II) and applied it to solve the lot-streaming flow shop scheduling problem with four criteria. We first presented four variants of NEH heuristic to generate the initial population, and then incorporated the estimation of distribution algorithm and a mutation operator based on insertion and swap into NSGA-II to replace traditional crossover and mutation operators. Last but not least, we performed a simple and efficient restarting strategy on the population when the diversity of the population is smaller than a given threshold. We conducted a serial of experiments, and the experimental results demonstrate that the proposed algorithm outperforms the comparative algorithms.     

遗传禁忌搜索算法在混流装配线排序中的应用

针对混流装配线排序问题,提出了一种混合遗传禁忌搜索算法,在每一代遗传演化之后,按一定比例随机选择部分解进行禁总搜索,以提高算法的全局搜索能力和收敛性。通过一个混流装配线排序实验,分别利用遗传算法和遗传禁忌搜索算法进行求解,结果表明遗传禁忌搜索算法具有更好的全局搜索能力和收敛性能。     

Sustainable operator assignment in an assembly line using genetic algorithm

This paper addresses the operator assignment in predefined workstations of an assembly line to get a sustainable result of fitness function of cycle time, total idle time and output where genetic algorithm is used as a solving tool. A proper operator assignment is important to get a sustainable balanced line. To improve the efficiency and meet the desired target output within the time limit, a balanced assembly line is a must. Real world lines consist of a large number of tasks and it is very time consuming and crucial to choose the most suitable operator for a particular workstation. In addition, it is very important to assign the suitable operator at the right place as his skill of operating machines finally reflects in productivity or in the cost of production. To verify better assignments of workers, a genetic algorithm is adopted here. A heuristic is proposed to find out the sustainable assignment of operators in the predefined workstations.     

基于迷宫算法和遗传算法的船舶管路路径规划

船舶管路的多样性和布局环境中约束的复杂性导致管路设计效率低下.为辅助设计人员提高管路设计效率并减少人为错误,提出了一种新的管路设计方法.首先,基于轴平行包围盒简化管路布局空间,利用栅格法对其进行离散化,并赋予空间网格特定的能量值,构建管路布局优化问题的数学模型.其次,基于遗传算法的框架,引入改进迷宫算法,提出管路路径规划方法,其中:迷宫搜索中引入辅助点的概念,增加了遗传算法中初始种群的多样性,有利于提高遗传算法的全局搜索能力;提出了定长度的编码方法,简化了管路染色体处理难度,提高了算法性能;基于引入方向优先搜索策略的迷宫算法,设计定长度编码遗传算子,保证了子代个体的质量,提高算法的收敛速度.最后,基于仿真试验,验证算法的性能.试验结果表明了该方法的可行性和高效率,以及其对实际管路布局工作具有指导意义.     

基于遗传算法的家用保安机器人路径规划方法

将领域知识与遗传算法相结合,提出了一种针对家用保安机器人的路径规划方法.该算法采用改进的栅格化方法来描述家庭环境,重新定义了路径适应度函数的评价方法,并设计有效的路径遗传算子.仿真结果表明了该算法的正确性和有效性.利用该算法实现了在实际家庭环境下保安机器人的路径规划与动态避障.     

运用改进的遗传算法进行框架结构损伤检测

运用一种改进的遗传算法来进行结构的损伤检测研究。该方法在传统遗传算法的变异算子里引入了一种被称为零变异率因子的参数，使得种群中时刻保持一定数量的零值元素，即相当于用结构的损伤只是发生在局部这个信息约束了传统的遗传算法，从而使得检测的结果更加准确。通过对某一框架模型试验数据的损伤检测研究，证明了该方法应用于实际工程结构的可行性，同时阐明了实际应用中的若干重要问题。     

多目标遗传算法在电梯主动导轮系统集成优化设计中的应用

介绍了一种基于多目标遗传算法的电梯主动导轮系统集成结构和控制器优化设计方法。在本方法中．电梯主动导轮结构参数和主动控制器参数同时作为优化设计变量，电梯系统性能和控制代价作为优化设计目标。这是一个复杂的多目标优化问题。由于控制器具有特定的结构，多目标遗传算法直接被用来求解该多目标集成优化问题。这样不仅可以避免权函数的选择，而且一次运行就可以求出所有的Pareto最优解。最后用一个实验室比例电梯模型作为例子来说明该设计过程。     

免疫粒子群算法在混流装配线排序中的应用

混流装配线上的产品投产排序是影响装配线生产效率的重要因素.建立以最小化装配线总闲置—超载成本为优化目标的装配线排序模型,采用粒子群算法来解决混流装配线的投产排序问题.考虑到基本粒子群算法易陷入局部最优解的问题,引入免疫算法思想对其进行改进,根据抗体亲和性与浓度值的计算,及时进行粒子的替换以维持种群的多样性,防止粒子过早...     

Stochastic two-sided U-type assembly line balancing: a genetic algorithm approach

In this paper, a novel stochastic two-sided U-type assembly line balancing (STUALB) procedure, an algorithm based on the genetic algorithm and a heuristic priority rule-based procedure to solve STUALB problem are proposed. With this new proposed assembly line design, all advantages of both two-sided assembly lines and U-type assembly lines are combined. Due to the variability of the real-life conditions, stochastic task times are also considered in the study. The proposed approach aims to minimise the number of positions (i.e. the U-type assembly line length) as the primary objective and to minimise the number of stations (i.e. the number of operators) as a secondary objective for a given cycle time. An example problem is solved to illustrate the proposed approach. In order to evaluate the efficiency of the proposed algorithm, test problems taken from the literature are used. The experimental results show that the proposed approach performs well.     

Assembly line balancing by a new multi-objective differential evolution algorithm based on TOPSIS

In this paper, we propose a multi-objective differential evolution algorithm (MODEA) to solve the multi-objective simple assembly line balancing problem type-2 (SALBP-2). This problem arises when in an existing assembly line, changes in the production process or demand structure take place and the organisation wants to produce the optimum number of items using a fixed number of workstations, which is associated with optimally assigning the tasks to an ordered sequence of stations such that the precedence relations are not violated and some measures of performance are optimised. The two considered objectives are: minimising the cycle time and the smoothness index of the assembly line. To that purpose, we develop a MODEA which unlike the existing algorithms deals with the considered objectives separately in selecting the next population members by proposing a new acceptance scheme based on the Pareto dominance concept and a new evaluation scheme based on TOPSIS. Also, by using the Taguchi method, we tune the effective factors of the developed algorithm. Then its efficiency is tested over available assembly line balancing benchmarks and compared to a new algorithm provided recently in the bi-objective SALBP-2 literature. Computational experiments indicate that the developed algorithm outperforms the existing meta-heuristic over a large group of benchmarks.     

An efficient local improvement operator for the multi-objective wireless sensor network deployment problem

Wireless sensor network layout, also known as sensor node deployment, is a complex NP-complete optimization task that determines most of the functioning features of a wireless sensor network. Coverage, connectivity and lifetime (handled through its opposing parameter, power consumption), are three of the most important characteristics of the service, and are taken into consideration in this article within a multi-objective approach of the problem. Leveraging on the specific properties of the wireless sensor nodes and networks, the Proximity Avoidance Coverage-preserving Operator (PACO) for local improvement is presented, described and tested. The testbed consists of a set of state-of-the-art multi-objective optimization algorithms with different configurations, and problem instances of varying size. In all the scenarios, and more specially in the algorithmic settings that already produce high performance solutions, PACO has proven to be a robust enhancement to the raw optimization technique, without requiring additional computation, that easily scales through problem complexity.     

基于遗传算法的层间等级网络编码优化

面向单信源异构信宿网络,研究了层间等级网络编码的编码类型优化。基于遗传算法,提出了一种最优编码类型的快速搜索方案。该方案充分考虑了信源输出链路上进行的层间等级网络编码的编码类型对整个网络传输性能的影响,将网络总吞吐量作为评价编码类型优劣的标准,设计了符合层间等级网络编码本质特性的遗传操作。实验结果表明,与分层组播网络编码和基于现有启发式算法的层间等级网络编码相比,基于本文方案实现的层间等级网络编码能够为单信源异构信宿网络获得更高的网络总吞吐量。     

An improved multi-objective evolutionary algorithm based on decomposition for energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time

With the increasing attention on environment issues, green scheduling in manufacturing industry has been a hot research topic. As a typical scheduling problem, permutation flow shop scheduling has gained deep research, but the practical case that considers both setup and transportation times still has rare research. This paper addresses the energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time to minimise both makespan as economic objective and energy consumption as green objective. The mathematical model of the problem is formulated. To solve such a bi-objective problem effectively, an improved multi-objective evolutionary algorithm based on decomposition is proposed. With decomposition strategy, the problem is decomposed into several sub-problems. In each generation, a dynamic strategy is designed to mate the solutions corresponding to the sub-problems. After analysing the properties of the problem, two heuristics to generate new solutions with smaller total setup times are proposed for designing local intensification to improve exploitation ability. Computational tests are carried out by using the instances both from a real-world manufacturing enterprise and generated randomly with larger sizes. The comparisons show that dynamic mating strategy and local intensification are effective in improving performances and the proposed algorithm is more effective than the existing algorithms.     

Improved imperialist competitive algorithms for rebalancing multi-objective two-sided assembly lines with space and resource constraints

In this paper, a mathematical model and an improved imperial competition algorithm (IICA) are proposed to solve the multi-objective two-sided assembly line rebalancing problem with space and resource restrictions (MTALRBP-SR). The aim is to find lines’ rebalance with the trade-off between efficiency, rebalancing cost and smoothing after reconfiguration. IICA utilises a new initialisation heuristic procedure based on classic heuristic rules to generate feasible initial solutions. A novel heuristic assimilation method is developed to vigorously conduct local search. In addition, a group-based decoding heuristic procedure is developed to fulfil the final task reassignment with the additional restrictions. To investigate the performance of the proposed algorithm, it is first tested on MTALRBP of benchmark problems and compared with some existing algorithms such as genetic algorithm, variable neighbourhood search algorithm, discrete artificial bee colony algorithm, and two iterated greedy algorithms. Next, the efficiency of the proposed IICA for solving MTALRBP-SR is revealed by comparison with a non-dominated sorting genetic algorithm (NSGA-II) and two versions of original ICA. Computational results and comparisons show the efficiency and effectiveness of IICA. Furthermore, a real-world case study is conducted to validate the proposed algorithm.     

基于遗传算法的三维无线传感器网络定位新算法

针对三维无线传感器网络节点自身定位问题,提出了一种基于遗传算法的新定位算法。该算法通过分析未知节点与它的无线射程范围内的已知节点之间的通讯约束和距离测量,对未知节点建立数学模型;针对此数学模型利用遗传算法求解,把该解作为未知节点的估计位置。理论分析和试验结果表明,该算法具有很强的健壮性,未知节点的失效和新节点的加入不会影响算法的性能,并且算法定位精度高,条件简单,适合各种规模的无线传感器网络的节点定位。     

异构无线网络的认证算法

本文针对建立在对等方式下的融合网络提出了一种新的认证和密钥更新算法.认证包括三个方面:非漫游状态下的完整认证、漫游状态下的完整认证以及切换状态下的快速认证.密钥更新包括两个方面:非漫游状态下的密钥更新和漫游状态下的密钥更新.在算法中,通过引入认证中心,不仅实现了网络对用户身份的认证,而且实现了节点对网络身份的认证,由此保证了双方身份的合法性;同时为了实现切换的无缝性,采用节点对认证数据包进行中继转发的方式,减少了切换时的认证时间.性能分析表明,该算法能够有效地抵御常见攻击.