Bi-objective partial flexible job shop scheduling problem: NSGA-II,NRGA, MOGA and PAES approaches

This paper deals with a problem of partial flexible job shop with the objective of minimising makespan and minimising total operation costs. This problem is a kind of flexible job shop problem that is known to be NP-hard. Hence four multi-objective, Pareto-based, meta-heuristic optimisation methods, namely non-dominated sorting genetic algorithm (NSGA-II), non-dominated ranked genetic algorithm (NRGA), multi-objective genetic algorithm (MOGA) and Pareto archive evolutionary strategy (PAES) are proposed to solve the problem with the aim of finding approximations of optimal Pareto front. A new solution representation is introduced with the aim of solving the addressed problem. For the purpose of performance evaluation of our proposed algorithms, we generate some instances and use some benchmarks which have been applied in the literature. Also a comprehensive computational and statistical analysis is conducted in order to analyse the performance of the applied algorithms in five metrics including non-dominated solution, diversification, mean ideal distance, quality metric and data envelopment analysis are presented. Data envelopment analysis is a well-known method for efficiently evaluating the effectiveness of multi-criteria decision making. In this study we proposed this method of assessment of the non-dominated solutions. The results indicate that in general NRGA and PAES have had a better performance in comparison with the other two algorithms.     

GRASP with path relinking for a multiple objective sequencing problem for a mixed-model assembly line

This research presents a new application of greedy randomised adaptive search procedure (GRASP) to address a production sequencing problem for mixed-model assembly line in a just-in-time (JIT) production system in two different cases. In the former case, small size sequencing problems are considered and two objectives are presented; minimisation of setups and optimisation of stability of material usage rates. These two objectives are inversely correlated with each other, so simultaneous optimisation of both is challenging. This type of problem is NP-hard. The GRASP, with path relinking, searches for efficient frontier where simultaneous optimisation of number of setups and usage rates is desired. Several test problems are solved via GRASP and its performance is compared to solutions obtained via complete enumeration and simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) approaches from the literature. Experimental results reveal that the GRASP with path relinking provides near-optimal solutions in terms of the two objectives and its ‘average inferiority%’ and ‘average percentile’ performances are superior to that of other heuristics. In the latter case, the goal is to explore varying the emphasis of these two conflicting objectives. Larger sequencing problems are considered and solved via GRASP with path relinking. Its objective function values are compared to the solutions obtained via a SA approach from the literature. Experimental results show that GRASP also provides good performance on large size problems and its percentage improvement is better than that of SA. Overall results also show, however, that the GRASP performs poorly with regard to CPU time.     

Pareto optimization using the struggle genetic crowding algorithm

Many real-world engineering design problems involve the simultaneous optimization of several conflicting objectives. In this paper, a method combining the struggle genetic crowding algorithm with Pareto-based population ranking is proposed to elicit trade-off frontiers. The new method has been tested on a variety of published problems, reliably locating both discontinuous Pareto frontiers as well as multiple Pareto frontiers in multi-modal search spaces. Other published multi-objective genetic algorithms are less robust in locating both global and local Pareto frontiers in a single optimization. For example, in a multi-modal test problem a previously published non-dominated sorting GA (NSGA) located the global Pareto frontier in 41% of the optimizations, while the proposed method located both global and local frontiers in all test runs. Additionally, the algorithm requires little problem specific tuning of parameters.     

Multi-objective scheduling problems: Determination of pruned Pareto sets

There are often multiple competing objectives for industrial scheduling and production planning problems. Two practical methods are presented to efficiently identify promising solutions from among a Pareto optimal set for multi-objective scheduling problems. Generally, multi-objective optimization problems can be solved by combining the objectives into a single objective using equivalent cost conversions, utility theory, etc., or by determination of a Pareto optimal set. Pareto optimal sets or representative subsets can be found by using a multi-objective genetic algorithm or by other means. Then, in practice, the decision maker ultimately has to select one solution from this set for system implementation. However, the Pareto optimal set is often large and cumbersome, making the post-Pareto analysis phase potentially difficult, especially as the number of objectives increase. Our research involves the post Pareto analysis phase, and two methods are presented to filter the Pareto optimal set to determine a subset of promising or desirable solutions. The first method is pruning using non-numerical objective function ranking preferences. The second approach involves pruning by using data clustering. The k-means algorithm is used to find clusters of similar solutions in the Pareto optimal set. The clustered data allows the decision maker to have just k general solutions from which to choose. These methods are general, and they are demonstrated using two multi-objective problems involving the scheduling of the bottleneck operation of a printed wiring board manufacturing line and a more general scheduling problem.     

Co-evolutionary algorithm: An efficient approach for bilevel programming problems

The bilevel programming problem involves two optimization problems, which is hierarchical, strongly NP-hard and very challenging for most existing optimization approaches. An efficient universal co-evolutionary algorithm is developed in this article to deal with various bilevel programming problems. In the proposed algorithm, evolutionary algorithms are used to explore the leader's and the follower's decision-making spaces interactively. Unlike other existing approaches, in the suggested procedure the follower's problem is solved in two phases. First, an evolutionary algorithm is run for a few generations to obtain an approximation of lower level solutions. In the second phase, from all approximate solutions obtained above, only a small number of good points are selected and evolved again by a newly designed multi-criteria evolutionary algorithm. The technique refines some candidate solutions and can efficiently reduce the computational cost of obtaining feasible solutions. Proof-of-principle experiments demonstrate the efficiency of the proposed approach.     

缓冲区容量约束下发动机混流装配线排序研究

为解决缓冲区容量约束下发动机混流装配排序问题,以关键部件消耗均匀化和最大完工时间最小化为目标,建立了优化数学模型,设计了一种多目标遗传算法,采用了混合交叉算子和启发式变异方法,并设计了基于帕累托分级和共享函数的适应度函数,将多目标遗传算法和多目标模拟退火算法的优化结果进行了比较。研究结果表明,多目标遗传算法在满意度和计算效率方面均优于多目标模拟退火算法,是一种有效的混流装配线排序问题求解算法。     

Real-parameter quantum evolutionary algorithm for economic load dispatch

A novel real-parameter optimisation algorithm called the 'real-parameter quantum evolutionary algorithm' is presented. The algorithm pieces together the ideas from evolutionary algorithms (EA) and quantum computing to provide a robust optimisation technique that can be utilised to optimise highly constrained non-linear real-parameter functions. Quantum bits have immense representational power due to their being in superposition of all the basic states at the same time. New quantum operators designed in this work enable the search to effectively handle the twin objectives of exploitation and exploration. This enables the search to be pursued with small population sizes, thereby speeding up the search process and also ensuring that there is no problem of premature convergence that often plagues pure EA implementations. The power of the proposed algorithm is demonstrated by solving the economic load dispatch (ELD) in power systems. ELD is to find the optimal loadings on the generators so as to achieve minimum operating cost while satisfying various system and unit-level constraints. The proposed method has been applied to standard load dispatch problems reported in the literature including the IEEE 30 bus system, IEEE 57 bus system and a 110-generator problem, and its performance has been compared with the results obtained by other methods. The results adequately demonstrate the enhanced search power of the proposed algorithm in terms of obtaining better solutions and provide motivation for its application to other real-parameter optimisation problems in power systems.     

The constraints satisfaction problem approach in the design of an architectural functional layout

A design support system with a new strategy for finding the optimal functional configurations of rooms for architectural layouts is presented. A set of configurations satisfying given constraints is generated and ranked according to multiple objectives. The method can be applied to problems in architectural practice, urban or graphic design—wherever allocation of related geometrical elements of known shape is optimized. Although the methodology is shown using simplified examples—a single story residential building with two apartments each having two rooms—the results resemble realistic functional layouts. One example of a practical size problem of a layout of three apartments with a total of 20 rooms is demonstrated, where the generated solution can be used as a base for a realistic architectural blueprint. The discretization of design space is discussed, followed by application of a backtrack search algorithm used for generating a set of potentially ‘good’ room configurations. Next the solutions are classified by a machine learning method (FFN) as ‘proper’ or ‘improper’ according to the internal communication criteria. Examples of interactive ranking of the ‘proper’ configurations according to multiple criteria and choosing ‘the best’ ones are presented. The proposed framework is general and universal—the criteria, parameters and weights can be individually defined by a user and the search algorithm can be adjusted to a specific problem.     

MONSS: A multi-objective nonlinear simplex search approach

This article presents a novel methodology for dealing with continuous box-constrained multi-objective optimization problems (MOPs). The proposed algorithm adopts a nonlinear simplex search scheme in order to obtain multiple elements of the Pareto optimal set. The search is directed by a well-distributed set of weight vectors, each of which defines a scalarization problem that is solved by deforming a simplex according to the movements described by Nelder and Mead's method. Considering an MOP with n decision variables, the simplex is constructed using n+1 solutions which minimize different scalarization problems defined by n+1 neighbor weight vectors. All solutions found in the search are used to update a set of solutions considered to be the minima for each separate problem. In this way, the proposed algorithm collectively obtains multiple trade-offs among the different conflicting objectives, while maintaining a proper representation of the Pareto optimal front. In this article, it is shown that a well-designed strategy using just mathematical programming techniques can be competitive with respect to the state-of-the-art multi-objective evolutionary algorithms against which it was compared.     

Microgenetic multiobjective reconfiguration algorithm considering power losses and reliability indices for medium voltage distribution network

This study proposes and applies an evolutionary-based approach for multiobjective reconfiguration in electrical power distribution networks. In this model, two types of indicators of power quality are minimised: (i) power system's losses and (ii) reliability indices. Four types of reliability indices are considered. A microgenetic algorithm ('GA) is used to handle the reconfiguration problem as a multiobjective optimisation problem with competing and non-commensurable objectives. In this context, experiments have been conducted on two standard test systems and a real network. Such problems characterise typical distribution systems taking into consideration several factors associated with the practical operation of medium voltage electrical power networks. The results show the ability of the proposed approach to generate well-distributed Pareto optimal solutions to the multiobjective reconfiguration problem. In the systems adopted for assessment purposes, our proposed approach was able to find the entire Pareto front. Furthermore, better performance indexes were found in comparison to the Pareto envelope-based selection algorithm 2 (PESA 2) technique, which is another well-known multiobjective evolutionary algorithm available in the specialised literature. From a practical point of view, the results established, in general, that a compact trade-off region exists between the power losses and the reliability indices. This means that the proposed approach can recommend to the decision maker a small set of possible solutions in order to select from them the most suitable radial topology.     

Unequal-area stochastic facility layout problems: solutions using improved covariance matrix adaptation evolution strategy,particle swarm optimisation,and genetic algorithm

Determining the locations of departments or machines in a shop floor is classified as a facility layout problem. This article studies unequal-area stochastic facility layout problems where the shapes of departments are fixed during the iteration of an algorithm and the product demands are stochastic with a known variance and expected value. These problems are non-deterministic polynomial-time hard and very complex, thus meta-heuristic algorithms and evolution strategies are needed to solve them. In this paper, an improved covariance matrix adaptation evolution strategy (CMA ES) was developed and its results were compared with those of two improved meta-heuristic algorithms (i.e. improved particle swarm optimisation [PSO] and genetic algorithm [GA]). In the three proposed algorithms, the swapping method and two local search techniques which altered the positions of departments were used to avoid local optima and to improve the quality of solutions for the problems. A real case and two problem instances were introduced to test the proposed algorithms. The results showed that the proposed CMA ES has found better layouts in contrast to the proposed PSO and GA.     

Methods for optimum and near optimum disassembly sequencing

This paper considers disassembly sequencing problems subjected to sequence dependent disassembly costs. In practice, the methods for dealing with such problems rely mainly on metaheuristic and heuristic methods, which intrinsically generate suboptimum solutions. Exact methods are NP-hard and therefore unsuitable to most of the practical problems. Nevertheless, it is useful to have exact methods available that can be applied in order to check, at least medium sized problems, to what extent the heuristically obtained solutions deviate from the optimum solution. The existing exact approaches, which are based on integer linear programming (ILP), become unmanageable, even for the cases of modest product complexity. To alleviate this problem to some extent, the iterative method that has been proposed by Lambert (2006) is applied here. This method is based on repeatedly solving a binary integer linear programming (BILP) problem instead of an ILP problem. The method appears to converge sufficiently quickly to be valuable for dealing with medium sized problems. We then use the iterative method for the validation of a new heuristic method that is also proposed in this paper. Finally, both the heuristic and the iterative BILP methods are implemented on a cellphone from practice consisting of 25 components that are represented, according to a set of precedence relationships, via a disassembly precedence graph.     

A synchronous reference point-based interactive method for stochastic multiobjective programming

Stochastic multiobjective programming models are highly complex problems, due to the presence of random parameters, together with several conflicting criteria that have to be optimized simultaneously. Even the widely used concept of efficiency has to be redefined for these problems. The use of interactive procedures can somehow ease this complexity, allowing the decision maker to learn about the problem itself, and to look for his most preferred solution. Reference point schemes can be adapted to stochastic problem, by asking the decision maker to provide, not only desirable levels for the objectives, but also the desired probability to achieve these values. In this paper, we analyze the different kinds of achievement scalarizing functions that can be used in this environment, and we study the efficiency (in the stochastic sense) of the different solutions obtained. As a result, a synchronous interactive method is proposed for a class of stochastic multiobjective problems, where only the objective functions are random. Several solutions can be generated by this new method, making use of the same preferential information, using the different achievement scalarizing functions. The preferential information (levels and probabilities for the objectives) is incorporated into the achievement scalarizing functions in a novel way to generate the new solutions. The special case of linear normal problems is addressed separately. The performance of the algorithm is illustrated with a numerical example.     

On the optimal control of steel annealing processes via various versions of genetic and particle swarm optimization algorithms

7 This paper elucidates the computation of optimal controls for steel annealing processes as hybrid systems which comprise of one or more furnaces integrated with plant-wide planning and scheduling operations. A class of hybrid system is considered to capture the trade-off between metallurgical quality requirement and timely product delivery. Various optimization algorithms including particle swarm optimization algorithm (PSO) with time varying inertia weight methods, PSO with globally and locally tuned parameters (GLBest PSO), parameter free PSO (pf-PSO) and PSO like algorithm via extrapolation (ePSO), real coded genetic algorithm (RCGA) and two-phase hybrid real coded genetic algorithm (HRCGA) are considered to solve the optimal control problems for the steel annealing processes (SAP). The optimal solutions including optimal line speed, optimal cost, and job completion time and convergence rate obtained through all these optimization algorithms are compared with each other and also those obtained via the existing method, forward algorithm (FA). Various statistical analyses and analysis of variance (ANOVA) test and hypothesis t-test are carried out in order to compare the performance of each method in solving the optimal control problems of SAP. The comparative study of the performance of the various algorithms indicates that the PSO like algorithms, pf-PSO and ePSO are equally good and are also better than all the other optimization methods considered in this chapter.     

An improved best-first branch-and-bound algorithm for constrained two-dimensional guillotine cutting problems

The constrained two-dimensional cutting problem involves maximising the sum of the profits obtained from small rectangular pieces cut from a large rectangular plate where the number of each type of cut piece cannot exceed a prescribed quantity. This paper proposes a best-first branch-and-bound algorithm to find the optimal solution to the problem. The proposed algorithm uses an efficient method to remove the duplicate patterns, and it improves the existing upper bounds. It also prevents the construction of dominated patterns and introduces a new bounding strategy that can prune more than one node at a time. Computational results are compared with a well-known exact algorithm to demonstrate the efficiency of the proposed algorithm. The proposed algorithm is as fast as or faster than the existing algorithm and reduces the average computing time by up to 99% for benchmark problems. For some problems, it can also find optimal solutions that existing algorithms are not able to find.     

Mixed discrete least squares meshless method for planar elasticity problems using regular and irregular nodal distributions

A Mixed Discrete Least Square Meshless (MDLSM) method is proposed for the solution of planar elasticity problems. In this approach, the differential equations governing the planar elasticity problems are written in terms of the stresses and displacements which are approximated independently using the same shape functions. Since the resulting governing equations are of the first order, both the displacement and stress boundary conditions are of the Dirichlet-type which is easily incorporated via a penalty method. Because least squares based algorithm of MDLSM method, the proposed method does not need to be satisfied by the LBB condition. The performance of the proposed method is tested on a benchmark example from theory of elasticity namely the problem of infinite plate with a circular hole and the results are presented and compared with those of the analytical solution and the solutions obtained using the irreducible DLSM formulation. The results indicate that the proposed MDLSM method is more accurate than the DLSM method. The results show that the numerical solutions of the MDLSM method can be obtained with lower computational cost and with higher accuracy. Also its performance is marginally affected by the irregularity of the nodal distribution.     

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.     

Integrated planning of loaded and empty container movements

Efficiently planning drayage operations is an important task for transportation companies since these operations constitute a large part of the cost of an intermodal transport. In this paper, a full truckload vehicle routing problem for transporting loaded and empty containers in drayage operations is studied. For empty container transports, either the origin or the destination is not predefined. The problem is formulated as an asymmetric multiple vehicle Travelling Salesman Problem with Time Windows (am-TSPTW). Two solution approaches are proposed: a sequential and an integrated approach. For both approaches, a single- and a two-phase deterministic annealing algorithm are presented. Results show that the proposed algorithms are able to find good quality solutions in a small amount of computation time. The integrated approach clearly outperforms the sequential one and the results confirm the advantage of using a two-phase algorithm for vehicle routing problems with hierarchical objectives. Finally, it is shown that the proposed integrated solution method improves previous results on a similar problem.     

A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times

In this paper, we contemplate the problem of scheduling a set of n jobs in a no-wait flexible flow shop manufacturing system with sequence dependent setup times to minimising the maximum completion time. With respect to NP-hardness of the considered problem, there seems to be no avoiding application of metaheuristic approaches to achieve near-optimal solutions for this problem. For this reason, three novel metaheuristic algorithms, namely population based simulated annealing (PBSA), adapted imperialist competitive algorithm (AICA) and hybridisation of adapted imperialist competitive algorithm and population based simulated annealing (AICA?+?PBSA), are developed to solve the addressed problem. Because of the sensitivity of our proposed algorithm to parameter's values, we employed the Taguchi method as an optimisation technique to extensively tune different parameters of our algorithm to enhance solutions accuracy. These proposed algorithms were coded and tested on randomly generated instances, then to validate the effectiveness of them computational results are examined in terms of relative percentage deviation. Moreover, some sensitive analyses are carried out for appraising the behaviour of algorithms versus different conditions. The computational evaluations manifestly support the high performance of our proposed novel hybrid algorithm against other algorithms which were applied in literature for related production scheduling problems.