| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 4.77 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
Este trabalho tem como principal objetivo resolver o problema de escalonamento de trabalhos
em máquinas paralelas com trocas de ferramentas, considerando ainda setups dependentes da
sequência e recursos adicionais. Este estudo surgiu de um problema real, de uma empresa do
ramo metalúrgico, que produz ferramentas de alta precisão.
Em primeiro lugar, foi desenvolvido um novo modelo de programação linear inteira mista, com
o objetivo de minimizar o makespan, isto é, o tempo de conclusão de todos os trabalhos. O
modelo foi implementado em Python através da biblioteca Pulp e do solver CPLEX. Os
resultados demonstraram que este método é uma boa escolha para instâncias de menor
dimensão, devido à boa qualidade das soluções e ao baixo tempo computacional, menos de 1
segundo para uma instância com 3 trabalhos e cerca de 2 minutos para uma instância com 14
trabalhos. Contudo, não conseguiu fornecer soluções viáveis para instâncias maiores em
tempos computacionais aceitáveis.
Por forma a ultrapassar essa limitação, implementou-se o Simulated Annealing, uma metaheurística
que se diferencia das outras pelo facto de aceitar soluções piores com base em
probabilidades. Foram incorporadas outras características do problema que não tinham sido
desenvolvidas no modelo matemático, como a restrição de operadores para as etapas de setup.
Esta meta-heurística também foi implementada em Python e foram realizados vários cenários
de teste com objetivos diferentes e alguns casos de multiobjectivo. Os resultados da sua
implementação demonstraram admissibilidade e estabilidade das soluções, denotando uma
boa parametrização realizada. Este método permitiu encontrar soluções para as instâncias de
maiores dimensões e em tempo computacional razoável para a indústria. Por exemplo, para
uma instância real da indústria metalúrgica com 10 máquinas, 33 trabalhos e 40 ferramentas,
o tempo computacional foi aproximadamente de 15 minutos.
Por fim, foi ainda desenvolvida uma heurística construtiva com base numa regra de ordenação
dos trabalhos, colocando em primeiro aqueles que requerem mais ferramentas. Esta heurística
necessita do input prévio da atribuição dos trabalhos às máquinas. Os resultados refutaram a
ideia que colocando primeiramente os trabalhos com mais ferramentas, se evitavam trocas ao
longo do processo. Na maioria dos casos, os resultados não foram melhores em relação à
solução gerada pela meta-heurística sob as mesmas condições de objetivo de minimização do
número de trocas de ferramentas.
Este trabalho fornece algumas contribuições relevantes, nomeadamente a proposta de um
novo modelo matemático e a evidência que as meta-heurísticas podem ser muito úteis na
resolução deste tipo de problemas de escalonamento em ambiente industrial.
The main objective of this work is to solve the problem of scheduling jobs on parallel machines with tool switching, considering sequence-dependent setups and additional resources. This study emerged from a real problem in a metalworking company that produces high-precision tools. Firstly, a new mixed integer linear programming model was developed with the aim of minimizing makespan, meaning the time it takes to complete all the jobs. The model was implemented in Python using the Pulp library and the CPLEX solver. The results showed that this method is a good choice for smaller instances, due to the good quality of the solutions and the low computational time, less than 1 second for an instance with 3 jobs and around 2 minutes for an instance with 14 jobs. However, it failed to provide viable solutions for larger instances in acceptable computational times. To overcome this limitation, simulated annealing was implemented, a meta-heuristic that differs from others in that it accepts worse solutions based on probabilities. Other characteristics of the problem that had not been developed in the mathematical model were incorporated, such as the restriction of operators for the setup stages. This metaheuristic was also implemented in Python and several test scenarios were carried out with different objectives and some multi-objective cases. The results of its implementation showed that the solutions are feasible and stable, indicating that they have been well parameterized. This method made it possible to find solutions for the largest instances in a reasonable amount of computational time for the industry. For example, for a real instance in the metalworking industry with 10 machines, 33 jobs and 40 tools, the computational time was around 15 minutes. Finally, a constructive heuristic was developed based on a rule for ordering the jobs, placing those that require the most tools first. This heuristic requires prior input from the assignment of jobs to machines. The results disproved the idea that placing the jobs with the most tools first would avoid trade-offs throughout the process. In most cases, the results were not better than the solution generated by the meta-heuristic under the same objective conditions of minimizing the number of tool changes. This work provides some relevant contributions, namely the proposal of a new mathematical model and evidence that metaheuristics can be very useful in solving this type of scheduling problem in the industrial environment.
The main objective of this work is to solve the problem of scheduling jobs on parallel machines with tool switching, considering sequence-dependent setups and additional resources. This study emerged from a real problem in a metalworking company that produces high-precision tools. Firstly, a new mixed integer linear programming model was developed with the aim of minimizing makespan, meaning the time it takes to complete all the jobs. The model was implemented in Python using the Pulp library and the CPLEX solver. The results showed that this method is a good choice for smaller instances, due to the good quality of the solutions and the low computational time, less than 1 second for an instance with 3 jobs and around 2 minutes for an instance with 14 jobs. However, it failed to provide viable solutions for larger instances in acceptable computational times. To overcome this limitation, simulated annealing was implemented, a meta-heuristic that differs from others in that it accepts worse solutions based on probabilities. Other characteristics of the problem that had not been developed in the mathematical model were incorporated, such as the restriction of operators for the setup stages. This metaheuristic was also implemented in Python and several test scenarios were carried out with different objectives and some multi-objective cases. The results of its implementation showed that the solutions are feasible and stable, indicating that they have been well parameterized. This method made it possible to find solutions for the largest instances in a reasonable amount of computational time for the industry. For example, for a real instance in the metalworking industry with 10 machines, 33 jobs and 40 tools, the computational time was around 15 minutes. Finally, a constructive heuristic was developed based on a rule for ordering the jobs, placing those that require the most tools first. This heuristic requires prior input from the assignment of jobs to machines. The results disproved the idea that placing the jobs with the most tools first would avoid trade-offs throughout the process. In most cases, the results were not better than the solution generated by the meta-heuristic under the same objective conditions of minimizing the number of tool changes. This work provides some relevant contributions, namely the proposal of a new mathematical model and evidence that metaheuristics can be very useful in solving this type of scheduling problem in the industrial environment.
Description
Keywords
Scheduling Tool switching Parallel machines SSP MILP Simulated annealing Escalonamento Troca de ferramentas Máquinas paralelas Simulated annealing Programação linear inteira mista