Horários de atendimento:
Terça-feira: 16:00h - 18:00h
Sexta-feira: 13:00h - 15:00h
Para garantir seu atendimento, reserve o horário com antecedência.
Artigos publicados em periódicos internacionais
Application of a hybrid evolutionary algorithm to resource-constrained parallel machine scheduling with setup times
Computers & Operations Research
Abstract
We address the problem of resource-constrained parallel machine scheduling with setup times in the practical context of microelectronic components manufacturing. This NP-hard problem is addressed using a biased random-key genetic algorithm hybridized with tailored local search procedures organized using variable neighborhood descent. The only benchmark available in the literature is utilized, and the optimal results are presented for all instances. Two new sets with 270 challenging instances are proposed to assess the quality of the solutions reported by the proposed method. A series of experiments are conducted to generate lower and upper bounds, including four models, two list processing heuristics from the literature and an implementation of a general variable neighborhood search metaheuristic. The bounds are used as reference values. The average percentage distances from the lower and upper bounds were 22.44% and −7.62%, respectively.
Heuristic methods to consecutive block minimization
Computers & Operations Research
Volume 120, August 2020, 104948
Abstract
Many combinatorial problems addressed in the literature are modeled using binary matrices. It is often of interest to verify whether these matrices hold the consecutive ones property (C1P), which implies that there exists a permutation of the columns of the matrix such that all nonzero elements can be placed contiguously, forming a unique 1-block in every row. The minimization of the number of 1-blocks is approached by a well-known problem in the literature called consecutive block minimization (CBM), an NP-hard problem. In this study, we propose a graph representation, a heuristic based on a classical algorithm in graph theory, the implementation of a metaheuristic for solving the CBM and the application of an exact method based on a reduction of the CBM to a particular version of the well-known traveling salesman problem. Computational experiments demonstrate that the proposed metaheuristic implementation is competitive, as it matches or improves the best known solution values for all benchmark instances available in the literature, except for a single instance. The proposed exact method reports, for the first time, optimal solutions for these benchmark instances. Consequently, the proposed methods outperform previous methods and become the new state-of-the-art for solving the CBM.
Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints
European Journal of Operational Research
Volume 285, Issue 3, 16 September 2020, Pages 955-964
Abstract
We address the problem of scheduling a set of n jobs on m parallel machines, with the objective of minimizing the makespan in a flexible manufacturing system. In this context, each job takes the same processing time in any machine. However, jobs have different tooling requirements, implying that setup times depend on all jobs previously scheduled on the same machine, owing to tool configurations. In this study, this NP-hard problem is addressed using a parallel biased random-key genetic algorithm hybridized with local search procedures organized using variable neighborhood descent. The proposed genetic algorithm is compared with the state-of-the-art methods considering 2,880 benchmark instances from the literature reddivided into two sets. For the set of small instances, the proposed method is compared with a mathematical model and better or equal results for 99.86% of instances are presented. For the set of large instances, the proposed method is compared to a metaheuristic and new best solutions are presented for 93.89% of the instances. In addition, the proposed method is 96.50% faster than the compared metaheuristic, thus comprehensively outperforming the current state-of-the-art methods.
Upcoming Events: