A multi-phase covering Pareto-optimal front method to multi-objective parallel machine scheduling

This paper considers the problem of parallel machine scheduling with sequence-dependent setup times to minimise both makespan and total earliness/tardiness in the due window. To tackle the problem considered, a multi-phase algorithm is proposed. The goal of the initial phase is to obtain a good approximation of the Pareto-front. In the second phase, to improve the Pareto-front, non-dominated solutions are unified to constitute a big population. In this phase, based on the local search in the Pareto space concept, three multi-objective hybrid metaheuristics are proposed. Covering the whole set of Pareto-optimal solutions is a desired task of multi-objective optimisation methods. So in the third phase, a new method using an e-constraint hybrid metaheuristic is proposed to cover the gaps between the non-dominated solutions and improve the Pareto-front. Appropriate combinations of multi-objective methods in various phases are considered to improve the total performance. The multi-phase algorithm iterates over a genetic algorithm in the first phase and three hybrid metaheuristics in the second and third phases. Experiments on the test problems with different structures show that the multi-phase method is a better tool to approximate the efficient set than the global archive sub-population genetic algorithm presented previously.     

A multi-objective scatter search for the ladle scheduling problem

We consider the ladle scheduling problem, which can be regarded as a vehicle routing problem with semi-soft time windows and adjustment times. The problem concerns allocating ladles to serve molten steel based on a given steelmaking scheduling plan, and determining the modification operations for the empty ladles after the service process. In addition, combining the controllable processing time of molten steel, the other aspect of the problem is to determine the service start times taking into consideration the technological constraints imposed in practice. We present a non-linear mathematical programming model with the conflicting objectives of minimising the occupation ratio of the ladles and maximising the degree of satisfaction with meeting the soft windows. To solve the multi-objective model, we develop a new scatter search (SS) approach by re-designing the common components of SS and incorporating a diversification generator, a combination method and a diversification criterion to conduct a wide exploration of the search space. We analyse and compare the performance of the proposed approach with a multi-objective genetic algorithm and with manual scheduling adopted in practical production using three real-life instances from a well-known iron–steel production plant in China. The computational results demonstrate the effectiveness of the proposed SS approach for solving the ladle scheduling problem.     

Optimal power system generation scheduling by multi-objective genetic algorithms with preferences

Power system generation scheduling is an important issue both from the economical and environmental safety viewpoints. The scheduling involves decisions with regards to the units start-up and shut-down times and to the assignment of the load demands to the committed generating units for minimizing the system operation costs and the emission of atmospheric pollutants.As many other real-world engineering problems, power system generation scheduling involves multiple, conflicting optimization criteria for which there exists no single best solution with respect to all criteria considered. Multi-objective optimization algorithms, based on the principle of Pareto optimality, can then be designed to search for the set of nondominated scheduling solutions from which the decision-maker (DM) must a posteriori choose the preferred alternative. On the other hand, often, information is available a priori regarding the preference values of the DM with respect to the objectives. When possible, it is important to exploit this information during the search so as to focus it on the region of preference of the Pareto-optimal set.In this paper, ways are explored to use this preference information for driving a multi-objective genetic algorithm towards the preferential region of the Pareto-optimal front. Two methods are considered: the first one extends the concept of Pareto dominance by biasing the chromosome replacement step of the algorithm by means of numerical weights that express the DM’ s preferences; the second one drives the search algorithm by changing the shape of the dominance region according to linear trade-off functions specified by the DM.The effectiveness of the proposed approaches is first compared on a case study of literature. Then, a nonlinear, constrained, two-objective power generation scheduling problem is effectively tackled.     

A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems

This paper presents a hybrid Pareto-based local search (PLS) algorithm for solving the multi-objective flexible job shop scheduling problem. Three minimisation objectives are considered simultaneously, i.e. the maximum completion time (makespan), the total workload of all machines, and the workload of the critical machine. In this study, several well-designed neighbouring approaches are proposed, which consider the problem characteristics and thus can hold fast convergence ability while keep the population with a certain level of quality and diversity. Moreover, a variable neighbourhood search (VNS) based self-adaptive strategy is embedded in the hybrid algorithm to utilise the neighbouring approaches efficiently. Then, an external Pareto archive is developed to record the non-dominated solutions found so far. In addition, a speed-up method is devised to update the Pareto archive set. Experimental results on several well-known benchmarks show the efficiency of the proposed hybrid algorithm. It is concluded that the PLS algorithm is superior to the very recent algorithms, in term of both search quality and computational efficiency.     

MOEA/D-SQA: a multi-objective memetic algorithm based on decomposition

A multi-objective memetic algorithm based on decomposition is proposed in this article, in which a simplified quadratic approximation (SQA) is employed as a local search operator for enhancing the performance of a multi-objective evolutionary algorithm based on decomposition (MOEA/D). The SQA is used for a fast local search and the MOEA/D is used as the global optimizer. The multi-objective memetic algorithm based on decomposition, i.e. a hybrid of the MOEA/D with the SQA (MOEA/D-SQA), is designed to balance local versus global search strategies so as to obtain a set of diverse non-dominated solutions as quickly as possible. The emphasis of this article is placed on demonstrating how this local search scheme can improve the performance of MOEA/D for multi-objective optimization. MOEA/D-SQA has been tested on a wide set of benchmark problems with complicated Pareto set shapes. Experimental results indicate that the proposed approach performs better than MOEA/D. In addition, the results obtained are very competitive when comparing MOEA/D-SQA with other state-of-the-art techniques.     

Robust scheduling for multi-objective flexible job-shop problems with flexible workdays

This study determines a robust schedule for a flexible job-shop scheduling problem with flexible workdays. The performance criteria considered in this study are tardiness, overtime and robustness. Furthermore, the problem is addressed in a Pareto manner, and a set of Pareto-optimal solutions is determined for this purpose. In consideration of all the aforementioned features, a goal-guided neighbourhood function is proposed based on efficient problem-dependent move-filtering methods. Two metaheuristic algorithms, named goal-guided multi-objective tabu search and goal-guided multi-objective hybrid search, are proposed in this work based on this neighbourhood function. The effectiveness of these approaches is demonstrated via empirical studies.     

Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabu search method

This paper investigates an integrated bi-objective optimisation problem with non-resumable jobs for production scheduling and preventive maintenance in a two-stage hybrid flow shop with one machine on the first stage and m identical parallel machines on the second stage. Sequence-dependent set-up times and preventive maintenance (PM) on the first stage machine are considered. The scheduling objectives are to minimise the unavailability of the first stage machine and to minimise the makespan simultaneously. To solve this integrated problem, three decisions have to be made: determine the processing sequence of jobs on the first stage machine, determine whether or not to perform PM activity just after each job, and specify the processing machine of each job on the second stage. Due to the complexity of the problem, a multi-objective tabu search (MOTS) method is adapted with the implementation details. The method generates non-dominated solutions with several parallel tabu lists and Pareto dominance concept. The performance of the method is compared with that of a well-known multi-objective genetic algorithm, in terms of standard multi-objective metrics. Computational results show that the proposed MOTS yields a better approximation.     

A memetic algorithm for multi-objective flexible job-shop problem with worker flexibility

In existing scheduling models, the flexible job-shop scheduling problem mainly considers machine flexibility. However, human factor is also an important element existing in real production that is often neglected theoretically. In this paper, we originally probe into a multi-objective flexible job-shop scheduling problem with worker flexibility (MO-FJSPW). A non-linear integer programming model is presented for the problem. Correspondingly, a memetic algorithm (MA) is designed to solve the proposed MO-FJSPW whose objective is to minimise the maximum completion time, the maximum workload of machines and the total workload of all machines. A well-designed chromosome encoding/decoding method is proposed and the adaptive genetic operators are selected by experimental studies. An elimination process is executed to eliminate the repeated individuals in population. Moreover, a local search is incorporated into the non-dominated sorting genetic algorithm II. In experimental phase, the crossover operator and elimination operator in MA are examined firstly. Afterwards, some extensive comparisons are carried out between MA and some other multi-objective algorithms. The simulation results show that the MA performs better for the proposed MO-FJSPW than other algorithms.     

Self-adaptive multi-objective harmony search for optimal design of water distribution networks

In multi-objective optimization computing, it is important to assign suitable parameters to each optimization problem to obtain better solutions. In this study, a self-adaptive multi-objective harmony search (SaMOHS) algorithm is developed to apply the parameter-setting-free technique, which is an example of a self-adaptive methodology. The SaMOHS algorithm attempts to remove some of the inconvenience from parameter setting and selects the most adaptive parameters during the iterative solution search process. To verify the proposed algorithm, an optimal least cost water distribution network design problem is applied to three different target networks. The results are compared with other well-known algorithms such as multi-objective harmony search and the non-dominated sorting genetic algorithm-II. The efficiency of the proposed algorithm is quantified by suitable performance indices. The results indicate that SaMOHS can be efficiently applied to the search for Pareto-optimal solutions in a multi-objective solution space.     

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.     

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.     

A new heuristic for the flowshop scheduling problem to minimize makespan and maximum tardiness

This paper presents a new heuristic for solving the flowshop scheduling problem that aims to minimize makespan and maximize tardiness. The algorithm is able to take into account the aforementioned performance measures, finding a set of non-dominated solutions representing the Pareto front. This method is based on the integration of two different techniques: a multi-criteria decision-making method and a constructive heuristic procedure developed for makespan minimization in flowshop scheduling problems. In particular, the technique for order preference by similarity of ideal solution (TOPSIS) algorithm is integrated with the Nawaz–Enscore–Ham (NEH) heuristic to generate a set of potential scheduling solutions. To assess the proposed heuristic's performance, comparison with the best performing multi-objective genetic local search (MOGLS) algorithm proposed in literature is carried out. The test is executed on a large number of random problems characterized by different numbers of machines and jobs. The results show that the new heuristic frequently exceeds the MOGLS results in terms of both non-dominated solutions, set quality and computational time. In particular, the improvement becomes more and more significant as the number of jobs in the problem increases.     

一种工业机器人多目标轨迹优化算法

为解决工业机器人工作效率低、能耗损失严重和关节冲击磨损较大的问题,提出了一种基于布谷鸟搜索(cuckoo search,CS)算法和非支配排序遗传算法-II(non-dominated sorting genetic algorithm-II,NSGA-II)的混合算法(简称为CSNSGA-II),用于机器人的轨迹优化...     

A hybrid evolutionary graph-based multi-objective algorithm for layout optimization of truss structures

In this paper a new graph-based evolutionary algorithm, gM-PAES, is proposed in order to solve the complex problem of truss layout multi-objective optimization. In this algorithm a graph-based genotype is employed as a modified version of Memetic Pareto Archive Evolution Strategy (M-PAES), a well-known hybrid multi-objective optimization algorithm, and consequently, new graph-based crossover and mutation operators perform as the solution generation tools in this algorithm. The genetic operators are designed in a way that helps the multi-objective optimizer to cover all parts of the true Pareto front in this specific problem. In the optimization process of the proposed algorithm, the local search part of gM-PAES is controlled adaptively in order to reduce the required computational effort and enhance its performance. In the last part of the paper, four numeric examples are presented to demonstrate the performance of the proposed algorithm. Results show that the proposed algorithm has great ability in producing a set of solutions which cover all parts of the true Pareto front.     

Robust multi-objective optimization for energy production scheduling in microgrids

In order to achieve better economic and environmental benefits of microgrids (MGs) under multiple uncertainties in renewable energy resources and loads, a novel energy production scheduling method is proposed based on robust multi-objective optimization with minimax criterion. Firstly, a mixed integer minimax multi-objective formulation is developed to capture uncertainties as well as minimize economic and environmental objectives. Secondly, the primal problem is decomposed into a bi-level optimization problem, which attempts to seek robust scheduling scheme set under the worst-case realization of uncertainties in a multi-objective framework. Finally, a hierarchical meta-heuristic solution strategy, including multi-objective cross entropy algorithm and δ+ indicator, is designed to solve the reconstructed problem. Numerical results demonstrate that the proposed scheduling method can effectively attenuate the disturbance of uncertainties as well as reduce energy costs and emissions, as compared with single-objective robust optimization and multi-objective optimization scheduling approaches. This study could offer useful insights which help decision-makers balance robustness and comprehensive benefits in the operation of MGs.     

Scenario-based multi-objective robust scheduling for a semiconductor production line

Scheduling problems of semiconductor manufacturing systems (SMS) with the goal of optimising some classical performance indices (NP-hard), tend to be increasingly complicated due to stochastic uncertainties. This paper targets the robust scheduling problem of an SMS with uncertain processing times. A three-stage multi-objective robust optimisation (MORO) approach is proposed, that can collaboratively optimise the performance indices and their robustness measures. In the first stage, this paper studies the scheduling problem in the deterministic environment and obtains feasible scheduling strategies that perform well in four performance indices (the average cycle time (CT), the on-time delivery rate (ODR), the throughput (TP), and the total movement amount of wafers (MOV)). Then, in the second stage, the uncertainties are introduced into the production system. In the third stage, this paper proposes a hybrid method consisting of scenario planning, discrete simulation, and multi-objective optimisation to obtain an approximately and more robust optimal solution from the feasible scheduling strategy set. The proposed MORO approach is tested in a semiconductor experiment production line and makes a full analysis to illustrate the effectiveness of our method. The results show that our MORO is superior concerning the total robustness with multi-objective.     

Effective multi-objective optimization with the coral reefs optimization algorithm

In this article a new algorithm for multi-objective optimization is presented, the Multi-Objective Coral Reefs Optimization (MO-CRO) algorithm. The algorithm is based on the simulation of processes in coral reefs, such as corals' reproduction and fight for space in the reef. The adaptation to multi-objective problems is a process based on domination or non-domination during the process of fight for space in the reef. The final MO-CRO is an easily-implemented and fast algorithm, simple and robust, since it is able to keep diversity in the population of corals (solutions) in a natural way. The experimental evaluation of this new approach for multi-objective optimization problems is carried out on different multi-objective benchmark problems, where the MO-CRO has shown excellent performance in cases with limited computational resources, and in a real-world problem of wind speed prediction, where the MO-CRO algorithm is used to find the best set of features to predict the wind speed, taking into account two objective functions related to the performance of the prediction and the computation time of the regressor.     

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.     

Fuzzy multi-objective optimization of finance-based scheduling for construction projects with uncertainties in cost

This article employs a new approach to investigate multi-objective finance-based scheduling for construction projects under uncertainty. It takes into consideration the line of credit to provide cash for implementation of a construction project. Using a finance-based scheduling concept and NSGA-II, the article presents a multi-objective model to search the non-dominated solutions considering total duration, required credit, and financing cost as three objectives. Fuzzy-sets theory is used to account for uncertainties in direct cost of each activity for determining the required credit and financing cost. The model fully embeds fuzzy presentation of the uncertainties in direct cost into the model structure. The α -cut approach is used to account for the accepted risk level of the project manager, for which a separate Pareto front with set of non-dominated solutions has been developed. Fuzzy numbers ranking is performed by the Hamming distance method. An example project is presented to validate the model and emphasize its merits.