Minimização de trocas de ferramentas considerando-se trocas por desgaste ou quebra.
Discentes:
Laura Cristina Silva e Rocha (FAPEMIG)
Horários de atendimento:
Quarta-feira: 13h - 17h
Para garantir seu atendimento, reserve o horário com antecedência.
Artigos publicados em periódicos internacionais
Biased random-key genetic algorithm for the job sequencing and tool switching problem with non-identical parallel machines
Computers & Operations Research
Volume 163, March 2024, 106509
Abstract
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.
Application of a hybrid evolutionary algorithm to resource-constrained parallel machine scheduling with setup times
Computers & Operations Research
Volume 139, March 2022, 105637
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.
Artigos publicados com alunos
A general variable neighborhood search approach for the job sequencing and tool switching problem
LVII Simpósio Brasileiro de Pesquisa Operacional
Abstract
The job sequencing and tool switching problem is a well-known NP-hard optimization problem with significant academic and industrial relevance. Although widely studied, the problem remains challenging, especially for large-scale instances. This paper presents the first application of the general variable neighborhood search metaheuristic for the problem, combining traditional and tailored local searches organized by a randomized variable neighborhood descent method. The approach is evaluated on large-scale benchmark instances, comparing the performance against the best-known solutions. Although not surpassing the state-of-the-art methods on average, the computational results show that the proposed method is competitive, achieving high-quality solutions with a notably low average gap of only 1.51%.
Geração eficiente de soluções iniciais de alta qualidade para o problema de minimização de trocas de ferramentas
Revista Brasileira de Computação Aplicada
Abstract
As an optimization problem, the job sequencing and tool switching problem has been the subject of several studies inoperations research on its different variations, emphasizing its academic and industrial relevance. Although currentmethods approaching this problem yield extremely high-quality solutions, the computational time required has provenprohibitive when considering the practical aspects of the problem. Thus, in this paper, a method is presented forgenerating valid, high-quality solutions in low computational time, which can be used as initial solutions by morerobust methods, aiming to accelerate them and contribute to the final quality of the solutions. The proposed approachconsists of a new implementation of the random variable-neighborhood descent method using traditional and tailoredlocal searches. Five traveling salesman problem heuristics were considered to generate the initial exploration pointfor the proposed method. The results obtained were compared with a recent strategy in the literature for generatinginitial solutions, which demonstrated significant improvement. Additionally, the proposed method was compared to thecurrent state-of-the-art method for the addressed problem, and an average gap of only 5.36% was reported, evidencingthe high quality of the solutions achieved for the proposed objective.