We address the job sequencing and tool switching problem associated with non-identical parallel machines - a variation of the well-known sequencing and switching problem (SSP) better adapted to reflect the challenges ...
详细信息
We address the job sequencing and tool switching problem associated with non-identical parallel machines - a variation of the well-known sequencing and switching problem (SSP) better adapted to reflect the challenges in modern production environments. The NP-hard problem is approached by considering two isolated objective functions: the minimization of the makespan and the minimization of the total flow time. We present two versions of a parallel biased random-key genetic algorithm hybridized with tailored local search procedures that are organized using variable neighborhood descent. The proposed methods are compared with state-of-the-art methods by considering 640 benchmark instances from literature. For both objective functions considered, the proposed methods consistently outperform the compared methods. All known optimal values for both objectives are achieved, and a substantial gap is reported for all instance groups when compared with the best previously published solution values.
This work addresses a practical problem concerning the daily scheduling of tasks for field technicians and route planning, taking into account time windows, task priority, technicians' skills, working hours, and l...
详细信息
This work addresses a practical problem concerning the daily scheduling of tasks for field technicians and route planning, taking into account time windows, task priority, technicians' skills, working hours, and lunch breaks. In line with the demands and expectations of large cities' customers, we pursue two goals simultaneously: to maximize the weighted sum of the attended tasks and to perform the highest-priority tasks as soon as possible within their time windows. This is done without disregarding the fact that more efficient routes reduce fuel consumption. This paper presents a bi-objective mixed integer programming model for the problem and introduces an innovative approach that combines a multi-objective BRKGA with the Q-Learning method. Q-Learning is a reinforcement learning method that controls the parameters of the BRKGA during the evolutionary process, learning the best configuration based on rewards. Extensive numerical experiments and comparisons with the Nondominated Sorting geneticalgorithm II and the Strength Pareto Evolutionary algorithm 2 show that the proposed multi-objective biased random-key genetic algorithm outperforms the other approaches in instances with up to 200 tasks and 30 technicians, which are typical instances encountered in practice. The developed approach facilitates parameter calibration and consistently attains a substantial portion of the Pareto frontier in the multi-objective STRSP.
The Minimum Broadcast Time (MBT) is a well-known data dissemination problem whose goal is to find a broadcast scheme that minimizes the number of steps needed to execute the broadcast operation. The problem has many a...
详细信息
The Minimum Broadcast Time (MBT) is a well-known data dissemination problem whose goal is to find a broadcast scheme that minimizes the number of steps needed to execute the broadcast operation. The problem has many applications in distributed systems and, in particular, the Industry 4.0 domain. Because Industry 4.0 applications rely primarily on the use of large-scale machine to machine communications, they need data dissemination techniques that combine high reliability with low communication latency. This work proposes a biased random-key genetic algorithm and a matheuristic for the MBT. We carry out experiments with our algorithms on instances commonly used in the literature (hypercube, shuffle exchange, cube-connected cycles, de Bruijn, Harary graphs), and also on massive synthetic instances (up to 1000 vertices), allowing to cover many possibilities of real industry topologies. Our proposal is also compared with state-of-the-art exact methods and heuristics. Experimental results show that our algorithm is able to outperform the best-known heuristics for the MBT, and also that it is a very good alternative for large instances that cannot be solved by current exact methods.
A graph is chordal if all its cycles of length greater than or equal to four contain a chord, i.e., an edge connecting two nonconsecutive vertices of the cycle. Given a graph G = (V, E), the chordal completion problem...
详细信息
A graph is chordal if all its cycles of length greater than or equal to four contain a chord, i.e., an edge connecting two nonconsecutive vertices of the cycle. Given a graph G = (V, E), the chordal completion problem consists in finding the minimum set of edges to be added to G to obtain a chordal graph. It has applications in sparse linear systems, database management and computer vision programming. In this article, we developed a biased random-key genetic algorithm (BRKGA) for solving the chordal completion problem, based on the strategy of manipulating permutations that represent perfect elimination orderings of triangulations. Computational results show that the proposed heuristic improve the results of the constructive heuristics fill-in and min-degree. We also developed a strategy for injecting externally constructed feasible solutions coded as randomkeys into the initial population of the BRKGA that significantly improves the solutions obtained and may benefit other implementations of biased random-key genetic algorithms.
This paper addresses the Set Orienteering Problem which is a generalization of the Orienteering Problem where the customers are grouped in clusters, and the profit associated with each cluster is collected by visiting...
详细信息
This paper addresses the Set Orienteering Problem which is a generalization of the Orienteering Problem where the customers are grouped in clusters, and the profit associated with each cluster is collected by visiting at least one of the customers in the respective cluster. The problem consists of finding a tour that maximizes the collected profit but, since the cost of the tour is limited by a threshold, only a subset of clusters can usually be visited. We propose a biased random-key genetic algorithm for solving the Set Orienteering Problem in which three local search procedures are applied to improve the fitness of the chromosomes. In addition, we introduced three rules useful to reduce the size of the instances and to speed up the resolution of the problem. Finally, a hashtable is used to quickly retrieve the information that are required several times during the computation. The computational results, carried out on benchmark instances, show that our algorithm is significantly faster than the other algorithms, proposed in the literature, and it provides solutions very close to the best-known ones. (C) 2020 Elsevier B.V. All rights reserved.
Every day many service companies need to plan the tasks that will be carried out by its field staff. Maintenance service technicians have to perform a set of jobs at different locations in a city or state. This proble...
详细信息
ISBN:
(纸本)9783030876722;9783030876715
Every day many service companies need to plan the tasks that will be carried out by its field staff. Maintenance service technicians have to perform a set of jobs at different locations in a city or state. This problem can be defined as the Service Technician Routing and Scheduling Problem in which tasks have different priorities and time windows, and technicians have different skills and working hours. Scheduling must account for technicians' lunch breaks, which must be respected. Each task is performed by only one technician. To ensure quality customer service and consumer rights are upheld, a novel approach is proposed: to address the problem in a multi-objective context aiming to execute the priority tasks and, simultaneously, to serve the customers at the beginning of their time windows. A Multi-objective biased random-key genetic algorithm (BRKGA) was customized to tackle this NP-hard optimization problem and then compared with the Non-dominated Sorting geneticalgorithm II (NSGA-II). The analyzed methods showed similar performance for small instances, but for medium- and large-sized instances the proposed method presented superior performance and more robust results.
This paper addresses a two-dimensional (2D) non-guillotine cutting problem, where a set of small rectangular items of given types has to be cut from a large rectangular stock plate having defective regions so as to ma...
详细信息
This paper addresses a two-dimensional (2D) non-guillotine cutting problem, where a set of small rectangular items of given types has to be cut from a large rectangular stock plate having defective regions so as to maximize the total value of the rectangles cut. The number of small items of each item type which can be cut from the large object is unrestricted. A novel MIP model and a hybrid approach combining a novel placement procedure with a biased random-key genetic algorithm (BRKGA) are presented. The parameters used by the novel placement procedure for the development of a cutting plan are evolved by the BRKGA. The management of the free spaces and of the defects uses a maximal-space representation. The approach is evaluated and compared to other approaches by means of a series of detailed numerical experiments using 5414 benchmark instances taken from the literature. The experimental results validate the quality of the solutions and the effectiveness of the proposed algorithm. (C) 2020 Elsevier B.V. All rights reserved.y
The problem of routing and wavelength assignment in optical networks consists in minimizing the number of wavelengths that are needed to route a set of demands, such that demands routed using lightpaths that share com...
详细信息
The problem of routing and wavelength assignment in optical networks consists in minimizing the number of wavelengths that are needed to route a set of demands, such that demands routed using lightpaths that share common links are assigned to different wavelengths. We present a biased random-key genetic algorithm for approximately solving the problem of routing and wavelength assignment of sliding scheduled lightpath demands in optical networks. In this problem variant, each demand is characterized not only by a source and a destination, but also by a duration and a time window in which it has to be met. Computational experiments show that the numerical results obtained by the proposed heuristic improved upon those obtained by a multistart constructive heuristic. In addition, the biased random-key genetic algorithm obtained much better results than an existing algorithm for the problem, finding solutions that use roughly 50% of the number of wavelengths determined by the latter.
In this paper, we advance the state of the art for solving the Permutation Flowshop Scheduling Problem with total flowtime minimization. For this purpose, we propose a biased random-key genetic algorithm (BRKGA) intro...
详细信息
In this paper, we advance the state of the art for solving the Permutation Flowshop Scheduling Problem with total flowtime minimization. For this purpose, we propose a biased random-key genetic algorithm (BRKGA) introducing on it a new feature called shaking. With the shaking, instead to full reset the population to escape from local optima, the shaking procedure perturbs all individuals from the elite set and resets the remaining population. We compare results for the standard and the shaking BRKGA with results from the Iterated Greedy Search, the Iterated Local Search, and a commercial mixed integer programming solver, in 120 traditional instances. For all algorithms, we use warm start solutions produced by the state-of-the-art Beam-Search procedure. Computational experiments show the efficiency of proposed BRKGA, in addition to identify lower and upper bounds, as well as some optimal values, among the solutions. (C) 2019 Elsevier Ltd. All rights reserved.
This paper presents a new metaheuristic approach for the two-stage capacitated facility location problem (TSCFLP), which the objective is to minimize the operation costs of the underlying two-stage transportation syst...
详细信息
This paper presents a new metaheuristic approach for the two-stage capacitated facility location problem (TSCFLP), which the objective is to minimize the operation costs of the underlying two-stage transportation system, satisfying demand and capacity constraints. In this problem, a single product must be transported from a set of plants to meet customers demands passing out by intermediate depots. Since this problem is known to be NP-hard, approximated methods become an efficient alternative to solve real industry problems. As far as we know, the TSCFLP is being solved in most cases by hybrid approaches supported by an exact method, and sometimes a commercial solver is used for this purpose. Bearing this in mind, a BRKGA metaheuristic and a new local search for TSCFLP are proposed. It is the first time that BRKGA had been applied to this problem and the computational results show the competitiveness of the approach developed in terms of quality of the solutions and required computational time when compared with those obtained by state-of-the-art heuristics. The approach proposed can be easily coupled in intelligent systems to help organizations enhance competitiveness by optimally placing facilities in order to minimize operational costs. (C) 2018 Elsevier Ltd. All rights reserved.
暂无评论