Search

This paper introduces a method for the distribution of any and all population-based metaheuristics. It improves on the naive approach, independent multiple runs, while adding negligible overhead. Existing methods that coordinate instances across a cluster typically require some compromise of more complex design, higher communication loads, and solution propagation rate, requiring more work to develop and more resources to run. The aim of the new method is not to achieve state-of-the-art results, but rather to provide a better baseline method than multiple independent runs. The main concept of the method is that one of the instances receives updates with the current best solution of all other instances. This work describes the general approach and its particularization to both genetic algorithms and ant colony optimization for solving Traveling Salesman Problems (TSPs). It also includes extensive tests on the TSPLIB benchmark problems of resulting quality of the solutions and anytime performance (solution quality versus time to reach it). These tests show that the new method yields better solutions for about two thirds of the problems and equivalent solutions in the remaining third, and consistently exhibits better anytime performance.

Over 30 years, evolutionary multi- and many-objective optimization (EMO/EMaO) algorithms have been extensively applied to find well-distributed Pareto-optimal (PO) solutions in a single run. However, in real-world problems, the PO front may not always be a single continuous hyper-surface, rather several irregularities may exist involving disjointed surfaces, holes within the surface, or patches of mixed-dimensional surfaces. When a set of trade-off solutions are obtained by EMO/EMaO algorithms, there may exist less dense or no solutions (we refer as 'gaps') in certain parts of the front. This can happen for at least two reasons: (i) gaps naturally exist in the PO front, or (ii) no natural gaps exists, but the chosen EMO/EMaO algorithm is not able to find any solution in the apparent gaps. To make a confident judgement, we propose a three-step procedure here. First, we suggest a computational procedure to identify gaps, if any, in the EMO/EMaO-obtained PO front. Second, we propose a computational method to identify well-distributed gap-points in the gap regions. Third, we apply a focused EMO/EMaO algorithm to search for possible representative trade-off points in the gaps. We then propose two metrics to qualitatively establish whether a gap truly exists in the obtained dataset, and if yes, whether the gap naturally exists on the true Pareto-set. Procedures are supported by results on two to five-objective test problems and on a five-objective scheduling problem from a steel-making industry.

In multi-objective optimisation problems, optimal decisions need to be made in the presence of trade-offs among conflicting objectives which may sometimes be expressed in different units of measure...

The aim of this paper is to analyse, model, and solve the rescheduling problem in dynamic permutation flow shop environments while considering several criteria to optimize. Searching optimal solutions in multiobjective optimization problems may be difficult as these objectives are expressing different concepts and are not directly comparable. Thus, it is not possible to reduce the problem to a single-objective optimization, and a set of efficient (nondominated) solutions, a so-called Pareto front, must be found. Moreover, in manufacturing environments, disruptive changes usually emerge in scheduling problems, such as machine breakdowns or the arrival of new jobs, causing a need for fast schedule adaptation. In this paper, a mathematical model for this type of problem is proposed and a restarted iterated Pareto greedy (RIPG) metaheuristic is used to find the optimal Pareto front. To demonstrate the appropriateness of this approach, the algorithm is applied to a benchmark specifically designed in this study, considering three objective functions (makespan, total weighted tardiness, and steadiness) and three classes of disruptions (appearance of new jobs, machine faults, and changes in operational times). Experimental studies indicate the proposed approach can effectively solve rescheduling tasks in a multiobjective environment.

Metaheuristics include a wide range of optimization algorithms. Some of them are very well known and with proven value, as they solve successfully many examples of combinatorial NP-hard problems. Some examples of Metaheuristics are Genetic Algorithms (GA), Simulated Annealing (SA) or Ant Colony Optimization (ACO). Our company is devoted to making steel and is the biggest steelmaker in the world. Combining several industrial processes to produce 84.6 million tones (public official data of 2015) involves huge effort. Metaheuristics are applied to different scenarios inside our operations to optimize different areas: logistics, production scheduling or resource assignment, saving costs and helping to reach operational excellence, critical for our survival in a globalized world. Rather than obtaining the global optimal solution, the main interest of an industrial company is to have "good solutions", close to the optimal, but within a very short response time, and this latter requirement is the main difference with respect to the traditional research approach from the academic world. Production is continuous and it cannot be stopped or wait for calculations, in addition, reducing production speed implies decreasing productivity and making the facilities less competitive. Disruptions are common events, making rescheduling imperative while foremen wait for new instructions to operate. This position paper explains the problem of the time response in our industrial environment, the solutions we have investigated and some results already achieved.