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.     

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.     

INTEREST: a reference-point-based interactive procedure for stochastic multiobjective programming problems

This paper presents a reference point-based interactive algorithm, which has been specifically designed to deal with stochastic multiobjective programming problems. This algorithm combines the classical information used in this kind of methods, i.e. values that the decision maker regards as desirable for each objective, with information about the probabilities the decision maker wishes to accept. This novel aspect allows the method to fully take into account the randomness of the final outcome throughout the whole solution process. These two pieces of information have been introduced in an adapted achievement-scalarizing function, which assures each solution obtained to be probability efficient.     

Practical solutions for multi-objective optimization: An application to system reliability design problems

For multiple-objective optimization problems, a common solution methodology is to determine a Pareto optimal set. Unfortunately, these sets are often large and can become difficult to comprehend and consider. Two methods are presented as practical approaches to reduce the size of the Pareto optimal set for multiple-objective system reliability design problems. The first method is a pseudo-ranking scheme that helps the decision maker select solutions that reflect his/her objective function priorities. In the second approach, we used data mining clustering techniques to group the data by using the k-means algorithm to find clusters of similar solutions. This provides the decision maker with just k general solutions to choose from. With this second method, from the clustered Pareto optimal set, we attempted to find solutions which are likely to be more relevant to the decision maker. These are solutions where a small improvement in one objective would lead to a large deterioration in at least one other objective. To demonstrate how these methods work, the well-known redundancy allocation problem was solved as a multiple objective problem by using the NSGA genetic algorithm to initially find the Pareto optimal solutions, and then, the two proposed methods are applied to prune the Pareto set.     

A genetic scheduling methodology for virtual cellular manufacturing systems: an industrial application

Effective solutions to the cell formation and the production scheduling problems are vital in the design of virtual cellular manufacturing systems (VCMSs). This paper presents a new mathematical model and a scheduling algorithm based on the techniques of genetic algorithms for solving such problems. The objectives are: (1) to minimize the total materials and components travelling distance incurred in manufacturing the products, and (2) to minimize the sum of the tardiness of all products. The proposed algorithm differs from the canonical genetic algorithms in that the populations of candidate solutions consist of individuals of different age groups, and that each individual's birth and survival rates are governed by predefined aging patterns. The condition governing the birth and survival rates is developed to ensure a stable search process. In addition, Markov Chain analysis is used to investigate the convergence properties of the genetic search process theoretically. The results obtained indicate that if the individual representing the best candidate solution obtained is maintained throughout the search process, the genetic search process converges to the global optimal solution exponentially.

The proposed methodology is applied to design the manufacturing system of a company in China producing component parts for internal combustion engines. The performance of the proposed age-based genetic algorithm is compared with that of the conventional genetic algorithm based on this industrial case. The results show that the methodology proposed in this paper provides a simple, effective and efficient method for solving the manufacturing cell formation and production scheduling problems for VCMSs.     

Using Interactive Multiobjective Optimization in Continuous Casting of Steel

We discuss some pros and cons of using different types of multiobjective optimization methods for demanding real-life problems like continuous casting of steel. In particular, we compare evolutionary approaches that are used for approximating the set of Pareto-optimal solutions to interactive methods where a decision maker actively takes part and can direct the solution process to such Pareto-optimal solutions that are interesting to her/him. Among the latter type of methods, we describe an interactive classification-based multiobjective optimization method: NIMBUS. NIMBUS converts the original objective functions together with preference information coming from the decision maker into scalar-valued optimization problems. These problems can be solved using any appropriate underlying solvers, like evolutionary algorithms. We also introduce an implementation of NIMBUS, called IND-NIMBUS, for solving demanding multiobjective optimization problems defined with different modelling and simulation tools. We apply NIMBUS and IND-NIMBUS in an optimal control problem related to the secondary cooling process in the continuous casting of steel. As an underlying solver we use a real-coded genetic algorithm. The aim in our problem is to find a control resulting with steel of the best possible quality, that is, minimizing the defects in the final product. Since the constraints describing technological and metallurgical requirements are so conflicting that they form an empty feasible set, we formulate the problem as a multiobjective optimization problem where constraint violations are minimized.     

Genetic-algorithms-based algorithm portfolio for inventory routing problem with stochastic demand

This paper presents an algorithm portfolio methodology based on evolutionary algorithms to solve complex dynamic optimisation problems. These problems are known to have computationally complex objective functions, which make their solutions computationally hard to find, when problem instances of large dimensions are considered. This is due to the inability of the algorithms to provide an optimal or near-optimal solution within an allocated time interval. Therefore, this paper employs a bundle of evolutionary algorithms (EAs) tied together with several processors, known as an algorithm portfolio, to solve a complex optimisation problem such as the inventory routing problem (IRP) with stochastic demands. EAs considered for algorithm portfolios are the genetic algorithm and its four variants such as the memetic algorithm, genetic algorithm with chromosome differentiation, age-genetic algorithm, and gender-specific genetic algorithm. In order to illustrate the applicability of the proposed methodology, a generic method for algorithm portfolios design, evaluation, and analysis is discussed in detail. Experiments were performed on varying dimensions of IRP instances to validate different properties of algorithm portfolio. A case study was conducted to illustrate that the set of EAs allocated to a certain number of processors performed better than their individual counterparts.     

Multi-objective genetic algorithm for solving N-version program design problem

N-version programming (NVP) is a programming approach for constructing fault tolerant software systems. Generally, an optimization model utilized in NVP selects the optimal set of versions for each module to maximize the system reliability and to constrain the total cost to remain within a given budget. In such a model, while the number of versions included in the obtained solution is generally reduced, the budget restriction may be so rigid that it may fail to find the optimal solution. In order to ameliorate this problem, this paper proposes a novel bi-objective optimization model that maximizes the system reliability and minimizes the system total cost for designing N-version software systems. When solving multi-objective optimization problem, it is crucial to find Pareto solutions. It is, however, not easy to obtain them. In this paper, we propose a novel bi-objective optimization model that obtains many Pareto solutions efficiently.We formulate the optimal design problem of NVP as a bi-objective 0–1 nonlinear integer programming problem. In order to overcome this problem, we propose a Multi-objective genetic algorithm (MOGA), which is a powerful, though time-consuming, method to solve multi-objective optimization problems. When implementing genetic algorithm (GA), the use of an appropriate genetic representation scheme is one of the most important issues to obtain good performance. We employ random-key representation in our MOGA to find many Pareto solutions spaced as evenly as possible along the Pareto frontier. To pursue improve further performance, we introduce elitism, the Pareto-insertion and the Pareto-deletion operations based on distance between Pareto solutions in the selection process.The proposed MOGA obtains many Pareto solutions along the Pareto frontier evenly. The user of the MOGA can select the best compromise solution among the candidates by controlling the balance between the system reliability and the total cost.     

A multi-objective genetic algorithm approach to the design of cellular manufacturing systems

In this paper, a multi-objective integer programming model is constructed for the design of cellular manufacturing systems with independent cells. A genetic algorithm with multiple fitness functions is proposed to solve the formulated problem. The proposed algorithm finds multiple solutions along the Pareto optimal frontier. There are some features that make the proposed algorithm different from other algorithms used in the design of cellular manufacturing systems. These include: (1) a systematic uniform design-based technique, used to determine the search directions, and (2) searching the solution space in multiple directions instead of single direction. Four problems are selected from the literature to evaluate the performance of the proposed approach. The results validate the effectiveness of the proposed method in designing the manufacturing cells.     

Optimisation of cutting parameters using a multi-objective genetic algorithm

This paper presents a new optimisation technique based on genetic algorithms (GA) for determination of cutting parameters in machining operations. The cutting parameters considered in this study are cutting speed, feed rate and cutting depth. The effect of these parameters on production time, production cost and roughness is mathematically formulated. A genetic algorithm with multiple fitness functions is proposed to solve the formulated problem. The proposed algorithm finds multiple solutions along the Pareto optimal frontier. Experimental results show that the proposed algorithm is both effective and efficient, and can be integrated into an intelligent process planning system for solving complex machining optimisation problems.     

Multiresponse Optimization and Pareto Frontiers

Methods that can capture evenly distributed solutions along the Pareto frontier are useful for multiresponse optimization problems because they provide a large variety of alternative solutions to the decision maker from among a set of nondominated solutions. However, methods often used for optimizing dual and multiple dual response problems have been rarely evaluated in terms of their ability to capture those solutions. This article provides this information by evaluating a global criterion–based method and the popular weighted mean square error method. Convex and nonconvex response surfaces were considered, and results of the methods were compared with those of a lexicographic approach on the basis of two examples from the literature. Regarding the results, it is shown that the user can be successful in capturing Pareto solutions in convex and nonconvex regions using the global criterion–based method. Moreover, it is shown that the starting point affects the distribution of solutions along the Pareto frontier but is not pivotal to obtain a complete representation of the Pareto frontier. For this purpose, it is necessary to decrease the weight increment and to compute for more solutions. Copyright © 2011 John Wiley & Sons, Ltd.     

Pareto navigator for interactive nonlinear multiobjective optimization

We describe a new interactive learning-oriented method called Pareto navigator for nonlinear multiobjective optimization. In the method, first a polyhedral approximation of the Pareto optimal set is formed in the objective function space using a relatively small set of Pareto optimal solutions representing the Pareto optimal set. Then the decision maker can navigate around the polyhedral approximation and direct the search for promising regions where the most preferred solution could be located. In this way, the decision maker can learn about the interdependencies between the conflicting objectives and possibly adjust one’s preferences. Once an interesting region has been identified, the polyhedral approximation can be made more accurate in that region or the decision maker can ask for the closest counterpart in the actual Pareto optimal set. If desired, (s)he can continue with another interactive method from the solution obtained. Pareto navigator can be seen as a nonlinear extension of the linear Pareto race method. After the representative set of Pareto optimal solutions has been generated, Pareto navigator is computationally efficient because the computations are performed in the polyhedral approximation and for that reason function evaluations of the actual objective functions are not needed. Thus, the method is well suited especially for problems with computationally costly functions. Furthermore, thanks to the visualization technique used, the method is applicable also for problems with three or more objective functions, and in fact it is best suited for such problems. After introducing the method in more detail, we illustrate it and the underlying ideas with an example.     

A branch-and-bound approach for machine selection in just-in-time manufacturing systems

Equipment selection issues are very important in the early stages of implementation of just-in-time (JIT) manufacturing systems. This paper addresses the problem of determining the number of machines for each stage of a JIT system by minimizing production, imbalance and investment costs. The problem is modelled as a mixed-integer nonlinear optimization program and a branch-and-bound algorithm is developed for its solution. This algorithm guarantees the global optimum of the problem and is enhanced by simple, yet very effective, upper bounding heuristics. The solutions obtained by the developed branch-and-bound approach are compared to solutions that have appeared in the literature using heuristic approaches. The comparisons indicate that the proposed algorithm leads to significant economic savings, averaging 17% on a set of problems from the literature. The paper also considers the application of the algorithm to large-scale, industrially-relevant, problems with up to 10 stages and 200 products. Even for the largest of these problems, the search for the integer optimum requires modest computational times. This demonstrates the potential practical impact of the proposed methodology.     

A Hopfield Neural Network Approach to the Dual Response Problem

The application of neural networks to optimization problems has been an active research area since the early 1980s. Unconstrained optimization, constrained optimization and combinatorial optimization problems have been solved using neural networks. This study presents a new approach using Hopfield neural networks (HNNs) for solving the dual response system (DRS) problems. The major aim of the proposed method is to produce a string of solutions, rather than a ‘one‐shot’ optimum solution, to make the trade‐offs available between the mean and standard deviation responses. This gives more flexibility to the decision‐maker in exploring alternative solutions. The proposed method has been tested on two examples. The HNN results are very close to those obtained by using the NIMBUS (Nondifferentiable Interactive Multiobjective Bundle‐based Optimization System) algorithm. Choosing an appropriate solution method for a certain multi‐objective optimization problem is not easy, as has been made abundantly clear. Unlike the NIMBUS method, the HNN approach does not set any specific assumptions on the behaviour or the preference structure of the decision maker. As a result, the proposed method will still work and generate alternative solutions whether or not the decision maker has enough time and capabilities for co‐operation. Copyright © 2005 John Wiley & Sons, Ltd.     

A MULTIOBJECTIVE INTERACTIVE SEQUENTIAL HYBRID OPTIMIZATION TECHNIQUE FOR DESIGN DECISION MAKING

The paper proposes an interactive method for obtaining a solution to a multiple objective design decision making problem. The focus is on generating Pareto solutions including those that are in the non-convex region, and are desirable to obtain in an engineering design context. After the generation of a small subset of the Pareto solutions, the designer's feedback is elicited in order to eliminate part of the subset. The process is repeated until il iteratively narrows down the Pareto solution set to a size small enough so that the designer is able to easily select a final solution. The advantage of this approach is that the designer can view a few sample points from the Pareto set before zooming into the region preferred and without expending computation time in generating a complete Pareto set. The process has been demonstrated with the help of an example, the design of a fleet of ships, that has mixed-discrete variables and hence a genetic algorithm is used as the optimizer.     

Determination of Pareto frontier in multi-objective maintenance optimization

The objective of a maintenance policy generally is the global maintenance cost minimization that involves not only the direct costs for both the maintenance actions and the spare parts, but also those ones due to the system stop for preventive maintenance and the downtime for failure. For some operating systems, the failure event can be dangerous so that they are asked to operate assuring a very high reliability level between two consecutive fixed stops. The present paper attempts to individuate the set of elements on which performing maintenance actions so that the system can assure the required reliability level until the next fixed stop for maintenance, minimizing both the global maintenance cost and the total maintenance time. In order to solve the previous constrained multi-objective optimization problem, an effective approach is proposed to obtain the best solutions (that is the Pareto optimal frontier) among which the decision maker will choose the more suitable one. As well known, describing the whole Pareto optimal frontier generally is a troublesome task. The paper proposes an algorithm able to rapidly overcome this problem and its effectiveness is shown by an application to a case study regarding a complex series-parallel system.     

混合整数双层线性规划的全局优化算法

本文讨论了上层决策变量为整数变量、下层决策变量为连续变量的混合整数双层线性规划问题,利用其可行解均落在约束域边界上的性质,提出了一种求解混合整数双层线性规划全局最优解的算法,并举例说明了算法的执行过程。     

Formation of independent manufacturing cells with the consideration of multiple identical machines

Cellular manufacturing is a manufacturing philosophy with the goal to produce low-medium volume products with high variety, while maintaining the high productivity of large-scale production. It is recognised as one of the most powerful management innovations in job-shop and batch production. Among the problems of designing a cellular manufacturing system, cell formation is the central and foremost issue. In the present paper, we investigate the formation of independent manufacturing cells with the consideration of multiple identical machines, in which inter-cell movements are completely eliminated by allocating identical machines in different manufacturing cells. Incorporating many real-life production factors including processing time, set-up time, alternative processing routes, machine capacity, batch size and cell size, we formulate a bi-objective mathematical model to minimise workload imbalance among manufacturing cells. Then, a genetic algorithm based on non-dominated sorting genetic algorithm II is developed to solve it. The computational results of numerical examples and the comparison analysis validated the performance of the proposed algorithm.     

An interactive decision framework for multiple objective production planning

The formation of realistic implementable medium-range production plans requires explicit recognition of the multiple conflicting objectives of production planning. However, suggested applications of multiobjective optimization to production planning have been limited to goal programming procedures which fail to capitalize on the intrinsic flexibility of a multiobjective model. Alternatively, interactive multiobjective solution techniques could be used to allow planners to enhance decision making without excessive computational effort. This study describes an interactive multiple objective decision framework and evaluates its effectiveness via a multiobjective capacitated lot sizing model based on a real manufacturing facility. The results suggest that this approach is an effective solution strategy and useful decision aid for complex production planning problems.