Publication
Escalonamento de trabalhos com trocas de ferramentas
| datacite.subject.fos | Engenharia e Tecnologia | pt_PT |
| dc.contributor.advisor | Mota, Alzira Maria Teixeira da | |
| dc.contributor.author | Santos, Renata da Costa | |
| dc.date.accessioned | 2024-12-12T14:19:46Z | |
| dc.date.available | 2024-12-12T14:19:46Z | |
| dc.date.issued | 2024-10-14 | |
| dc.description.abstract | 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. | pt_PT |
| dc.description.abstract | 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. | pt_PT |
| dc.identifier.tid | 203733991 | pt_PT |
| dc.identifier.uri | http://hdl.handle.net/10400.22/26795 | |
| dc.language.iso | por | pt_PT |
| dc.subject | Scheduling | pt_PT |
| dc.subject | Tool switching | pt_PT |
| dc.subject | Parallel machines | pt_PT |
| dc.subject | SSP | pt_PT |
| dc.subject | MILP | pt_PT |
| dc.subject | Simulated annealing | pt_PT |
| dc.subject | Escalonamento | pt_PT |
| dc.subject | Troca de ferramentas | pt_PT |
| dc.subject | Máquinas paralelas | pt_PT |
| dc.subject | Simulated annealing | pt_PT |
| dc.subject | Programação linear inteira mista | pt_PT |
| dc.title | Escalonamento de trabalhos com trocas de ferramentas | pt_PT |
| dc.title.alternative | Job sequencing and tool switching problem | pt_PT |
| dc.type | master thesis | |
| dspace.entity.type | Publication | |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | masterThesis | pt_PT |
| thesis.degree.name | Mestrado em Engenharia e Gestão Industrial | pt_PT |