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.     

Rebalancing the assembly lines: exact solution approaches

In this study, we consider an assembly line rebalancing problem with disruptions caused by workstation breakdowns or shutdowns. After the disruption, we aim to find a rebalance so as to catch the trade-off between the efficiency measure of cycle time and stability measure of number of tasks assigned to different workstations in the original and new balances. Our aim is to generate all nondominated objective vectors with respect to the efficiency and stability measures. We develop two optimisation algorithms: a Mixed Integer Linear Programming-based algorithm and a Branch and Bound algorithm. The results of our experiments have shown the favourable performances of both algorithms and the superiority of the Branch and Bound algorithm.     

Comparisons of bi-objective genetic algorithms for hybrid flowshop scheduling with sequence-dependent setup times

This paper addresses the scheduling problems in a hybrid flowshop with two objectives of minimising the makespan and total tardiness. Since this problem is NP-hard, evolutionary algorithms based on the genetic algorithm (GA) namely; BOGAW, BOGAC, BOGAT, and BOGAS are proposed for searching the Pareto-optimal frontier. In these algorithms, we propose to generate a section of solutions for the next generation using a neighbourhood search structure on the best individual in each generation. The selection procedure selects the best chromosome based on an evaluation mechanism used in the algorithm (i.e., weighted sum, crowding distance, TOPSIS and single-objective). The aim of this paper is to clarify that the cited characteristic is efficient and it enhances the efficiency of algorithms. Therefore, we perform a comparison between the proposed algorithms to find the best alternative. Data envelopment analysis is used to evaluate the performance of approximation methods. The obtained result from the comparison shows that, BOGAC is the more efficient. To continue, since the efficiency of our idea is not clear, we compare our efficient algorithm with other efficient algorithms in the literature (namely PGA-ALS and MOGLS). The final persuasive results support the idea that BOGAC in comparison with PGA-ALS and MOGLS is more effective and efficient.     

A new approach for rebalancing of U-lines with stochastic task times using ant colony optimisation algorithm

In real world, line balancing involves existing lines in existing factories and the line typically needs to be rebalanced rather than balanced. Rebalancing of a U-line can be defined as a changeover process from its initial configuration to a new configuration for a while due to the reasons such as demand variations, changes in product design and changes in task times, etc. This study defines U-line rebalancing problem with stochastic task times and proposes a solution procedure based on ant colony optimisation. The objective of the proposed algorithm is to minimise total cost of rebalancing which is the sum of task transposition costs, workstation opening/closing costs and operating costs of workstations for a particular planning horizon. A comprehensive experiment is conducted to generate problem instances and to compare rebalancing costs of U-lines by means of several factors. A total of 6600 rebalancing solutions are obtained and several comparisons are performed.     

Transmitter-Receiver Path Selection for Cell Range Extension Using Multi-Hop D2D

Conventional approach of dealing with more users per coverage area in cellular networks implies densifying the amount of (Access Point) AP which will eventually result in a larger carbon footprint. In this paper, we propose a base station off-loading and cell range extension (CRE) scheme based on multi-hop device-to-device (MHD2D) path selection between transmitter and receiver node. The paper also provides derivations of upper and lower bounds for energy efficiency, capacity, and transmit power. The proposed path selection scheme is inspired by the foraging behavior of honey bees. We present the algorithm as a modified variant of the artificial bee colony algorithm (MVABC). The proposed optimization problem is modeled as a minimization problem where we optimize the Energy Efficiency (EE). The proposed path selection MVABC is compared with the Genetic Algorithm (GA) and also with classical artificial bee colony (ABC) through simulations and statistical analysis. The student’s t-test, p-value, and standard error of means (SEM) clearly show that MVABC based path selection out-performs the GA and classical ABC schemes. MVABC based approach is 66% more efficient when compared with classic ABC and about 62% efficient when compared with GA based scheme.     

A simulated annealing algorithm for balancing the assembly line type II problem with sequence-dependent setup times between tasks

This paper addresses the general assembly line balancing problem where the simple version is enriched by considering sequence-dependent setup times between tasks. Recently, Andres et al. (Andres, C., Miralles, C., and Pastor, R., 2008. Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. European Journal of Operational Research, 187, (3), 1212–1223.) proposed the type I general assembly line balancing problem with setups (GALBPS-I) and developed a mathematical model and several algorithms for solving the problem. In a similar vein, we scrutinised the GALBPS type II problem where the challenge is to find the minimum cycle time for a predefined number of work stations. To solve the problem, we develop a mathematical model and a novel simulated annealing (SA) algorithm to solve such an NP-hard problem. We then employed the Taguchi method as an optimisation technique to extensively tune different parameters of our algorithm and make the classical SA algorithm more efficient in terms of running time and solution quality. Computational results reflected the high efficiency of the SA algorithm in both aspects.     

Pneumatic motor speed control by trajectory tracking fuzzy logic controller

In this study, trajectory tracking fuzzy logic controller (TTFLC) is proposed for the speed control of a pneumatic motor (PM). A third order trajectory is defined to determine the trajectory function that has to be tracked by the PM speed. Genetic algorithm (GA) is used to find the TTFLC boundary values of membership functions (MF) and weights of control rules. In addition, artificial neural networks (ANN) modelled dynamic behaviour of PM is given. This ANN model is used to find the optimal TTFLC parameters by offline GA approach. The experimental results show that designed TTFLC successfully enables the PM speed track the given trajectory under various working conditions. The proposed approach is superior to PID controller. It also provides simple and easy design procedure for the PM speed control problem.     

Genetic algorithm with adaptive and dynamic penalty functions for the selection of cleaner production measures: a constrained optimization problem

This paper presents a new approach of genetic algorithm (GA) to solve the constrained optimization problem. In a constrained optimization problem, feasible and infeasible regions occupy the search space. The infeasible regions consist of the solutions that violate the constraint. Oftentimes classical genetic operators generate infeasible or invalid chromosomes. This situation takes a turn for the worse when infeasible chromosomes alone occupy the whole population. To address this problem, dynamic and adaptive penalty functions are proposed for the GA search process. This is a novel strategy because it will attempt to transform the constrained problem into an unconstrained problem by penalizing the GA fitness function dynamically and adaptively. New equations describing these functions are presented and tested. The effects of the proposed functions developed have been investigated and tested using different GA parameters such as mutation and crossover. Comparisons of the performance of the proposed adaptive and dynamic penalty functions with traditional static penalty functions are presented. The result from the experiments show that the proposed functions developed are more accurate, efficient, robust and easy to implement. The algorithms developed in this research can be applied to evaluate environmental impacts from process operations.     

A new approach to the cell formation problem with alternative processing routes and operation sequence

Cellular manufacturing (CM) is an important application of group technology in manufacturing systems. One of the crucial steps in the design of CM is the identification of part families and manufacturing cells. This problem is referred to as cell formation problem (CFP) in the literature. In this article, a solution approach is proposed for CFP, which considers many parameters such as machine requirement, sequence of operations, alternative processing routes, processing time, production volume, budget limitation, cost of machines, etc. Due to the NP-hardness of CFP, it cannot be efficiently solved for medium- to large-sized problems. Thus, a genetic algorithm (GA) is proposed to solve the formulated model. Comparison of the results obtained from the proposed GA to the globally optimum solutions obtained by Lingo Software and those reported in the literature reveals the effectiveness and efficiency of the proposed approach.     

One- and two-sided assembly line balancing problems with real-world constraints

In this study, we consider balancing problems of one- and two-sided assembly lines with real-world constraints like task or machine incompatibilities. First, we study the one-sided assembly line balancing problem (ALBP) with a limited number of machine types per workstation. Using a genetic algorithm (GA), we find optimal results for real-world instances. A set of larger test cases is used to compare two well-established solution approaches, namely GA and tabu search (TS). Additionally, we apply a specific differential evolution algorithm (DE), which has recently been proposed for the considered ALBP. Our computational results show that DE is clearly dominated by GA. Furthermore, we show that GA outperforms TS in terms of computational time, if capacity constraints are tight. Given the algorithm’s computational performance as well as the fact that it can easily be adapted to additional constraints, we then use it to solve two-sided ALBP. Three types of constraints and two different objectives are considered. We outperform all previously published methods in terms of solution quality and computational time. Finally, we are the first to provide feasible test instances as well as benchmark results for fully constrained two-sided ALB.     

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.     

求解大规模TSP问题的混合算法

遗传算法求解大规模TSP时呈现出求解时间长、后期效率明显降低等缺陷。通过结合分块方法、局部搜索算法以及禁忌算法,本文提出一个求解TSP的混合算法,以提高初始解质量,减少计算量。利用遗传算法和混合算法对几个TSP进行数值实验,表明无论在结果的质量上还是在运行效率上,混合算法都明显优于遗传算法,而且,规模越大效果越明显。     

A genetic algorithm based heuristic for adjacent paper-reel layout problem

In this paper, we present an algorithm that solves a paper reel layout problem where the available space is divided into equal-size cells. The problem is to find a layout with the minimum transportation cost subject to adjacency and other constraints. A genetic algorithm is used in a two-stage iterative approach to solve the problem. Computational results seem to indicate the efficiency and effectiveness of the proposed solution method.     

Linear Programming Based Genetic Algorithm for the Unequal Area Facility Layout Problem

The facility layout problem (FLP) is generally defined as locating a set of departments in a facility with a given dimension. In this paper, a hybrid genetic algorithm (GA)/linear programming (LP) approach is proposed to solve the FLP on the continuous plane with unequal area departments. This version of the FLP is very difficult to solve optimally due to the large number of binary decision variables in mixed integer programming (MIP) models as well as the lack of tight lower bounds. In this paper, a new encoding scheme, called the location/shape representation, is developed to represent layouts in a GA. This encoding scheme represents relative department positions in the facility based on the centroids and orientations of departments. Once relative department positions are set by the GA, actual department locations and shapes are determined by solving an LP problem. Finally, the output of the LP solution is incorporated into the encoding scheme of the GA. Numerical results are provided for test problems with varying sizes and department shape constraints. The proposed approach is able to either improve on or find the previously best known solutions of several test problems.     

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.     

Real-coded genetic algorithm and fuzzy logic approach for real-time tuning of proportional-integral?derivative controller in automatic voltage regulator system

Optimal tuning of proportional?integral?derivative (PID) controller parameters is necessary for the satisfactory operation of automatic voltage regulator (AVR) system. This study presents a combined genetic algorithm (GA) and fuzzy logic approach to determine the optimal PID controller parameters in AVR system. The problem of obtaining the optimal PID controller parameters is formulated as an optimisation problem and a real-coded genetic algorithm (RGA) is applied to solve the optimisation problem. In the proposed RGA, the optimisation variables are represented as floating point numbers in the genetic population. Further, for effective genetic operation, the crossover and mutation operators which can deal directly with the floating point numbers are used. The proposed approach has resulted in PID controller with good transient response. The optimal PID gains obtained by the proposed GA for various operating conditions are used to develop the rule base of the Sugeno fuzzy system. The developed fuzzy system can give the PID parameters on-line for different operating conditions. The suitability of the proposed approach for PID controller tuning has been demonstrated through computer simulations in an AVR system.     

FUZZY-GENETIC ALGORITHMS AND TIME-OPTIMAL OBSTACLE-FREE PATH GENERATION FOR MOBILE ROBOTS

This paper, describes a new yet efficient technique based on fuzzy logic and genetic algorithms (Gas) to solve the find-path problems of a mobile robot, which is formulated as a nonlinear programming problem. In the proposed algorithm, a fuzzy logic controller is used to find obstracle-free directions locally and GAs are used as optimizer to find optimal/near-optimal locations along the obstracle-free directions. This algorithm is found to be more efficient than a steepest gradient descent method. Although the fuzzy-GA method is shown to find slightly inferior or similar solutions to those found using the best-known tangent-graph and A* algorithms, it is computationally faster than them. Moreover, the fuzzy-GA approach is practically more viable than the tangent-graph method, because of former's lesser sensitivity to the number and type of obstacles. The efficiency of the proposed method demonstrated in this paper suggests that it can be extended to solve motion planning problems having moving obstacles.     

A multi-objective model for risk mitigating in supply chain design

The goal of this study is to recognise various factors for responsive SCs that affect supply risk and model their impact on SC design and operation. We propose a conceptual model for SC responsiveness that encompasses practices such as flexibility, agility, internal integration, and visibility. This conceptual model is utilised to build up a multi-objective, multi-period SC design and operation model. A heuristic algorithm is developed to find the supplier, product, period, and production rate for the numerical problem. The improved genetic algorithm (GA) produces solutions with more accuracy in considerably less time than a traditional GA. Finally, an approach to prioritise the objective functions is developed that allows managers to focus on specific objective functions more than optimum values. This approach provides risk-averse, responsiveness-oriented, cost-effective managers the capability to set priorities based on their policies.     

Extending capacity planning by positive lead times and optional overtime,earliness and tardiness for effective master production scheduling

In this paper we consider the problem of improving the Master Production Schedule (MPS) in make-to-order production systems when demand exceeds available resource capacity. Due to the complexity of the problem, in practice solutions are usually obtained manually. We propose an algorithm that offsets production orders guided by tardiness, earliness and overtime penalties. The intermediate tool used to determine resource utilization is Rough Cut Capacity Planning (RCCP) extended by positive lead times and options for overtime, earliness and tardiness. This approach leads to a more realistic resource loading calculation, similar to CRP but without its computational burden. The discrete optimization model is solved by a Genetic Algorithm (GA); within the GA, delays or early deliveries of each order are represented as genes of a chromosome. The method is tested against systematically developed benchmark problems and real industrial data. Improvements over the traditional RCCP procedure and an ERP's embedded routines are demonstrated by the computational results and support the applicability of the proposed approach for real-life make-to-order environments.     

A new paradigm for rule-based scheduling in the wafer probe centre

This paper addresses the scheduling problem in the wafer probe centre. The proposed approach is based on the dispatching rule, which is popularly used in the semiconductor manufacturing industry. Instead of designing new rules, this paper proposes a new paradigm to utilize these rules. The proposed paradigm formulates the dispatching process as a 2-D assignment problem with the consideration of information from multiple lots and multiple pieces of equipment in an integrated manner. Then, the dispatching decisions are made by maximizing the gains of multiple possible decisions simultaneously. Besides, we develop a genetic algorithm (GA) for generating good dispatching rules through combining multiple rules with linear weighted summation. The benefits of the proposed paradigm and GA are verified with a comprehensive simulation study on three due-date-based performance measures. The experimental results show that under the proposed paradigm, the dispatching rules and GA can perform much better than under the traditional paradigm.