Horários de atendimento:
Terça-feira: 15:00h - 17:00h
Sexta-feira: 15:00h - 17:00h
Para garantir seu atendimento, reserve o horário com antecedência.
*Durante o ERE o atendimento será virtual.
Artigos publicados em periódicos internacionais
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:
Avaliação final de Desenvolvimento Back-end 21/11/2020
Avaliação final de LPII - 11/12/2020