Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/59600| Type: | Dissertação |
| Title: | Modelo de arranjo linear e desigualdades válidas para o problema job shop com minimização do makespan |
| Authors: | Aguiar Júnior, Judecir Cavalcante |
| Advisor: | Andrade, Rafael Castro de |
| Co-advisor: | Duhamel, Christophe Didier |
| Keywords: | Otimização combinatória;Planejamento da produção;Desigualdades válidas;Programação inteira;Combinatorial optimization;Production planning;Valid inequalities;Integer programming |
| Issue Date: | 2021 |
| Citation: | AGUIAR JÚNIOR, Judecir Cavalcante. Modelo de arranjo linear e desigualdades válidas para o problema job shop com minimização do makespan. 2021. 84 f. Dissertação (Mestrado em Modelagem e Métodos Quantitativos) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2021. |
| Abstract in Brazilian Portuguese: | O problema do sequeciamento de trabalhos, do inglês job shop scheduling problem (JSSP), consiste em agendar n trabalhos (jobs) em m máquinas. Cada trabalho tem uma ordem de processamento nas máquinas, podendo inclusive ser uma ordem específica para cada um, e um tempo de processamento em cada uma delas. Além disso, cada trabalho não pode ser processado ao mesmo tempo em duas máquinas distintas, cada máquina não pode processar dois trabalhos ao mesmo tempo e se um trabalho iniciou seu processamento em uma máquina, então tem que ser concluído sem interrupções. Uma das funções objetivo para esse problema é minimizar a conclusão do último trabalho a ser processado, também conhecido como makespan. Para essa função objetivo o problema é NP-Difícil para pelo menos três máquinas e dois trabalhos e, por isso, é importante desenvolver novos modelos para conseguir resultados mais eficientes. Para tanto, exploramos uma modelagem de Andrade et al. (2017) para o problema do arranjo linear mínimo, do inglês minimum linear arrangement (MinLA), e adaptamos essa abordagem para desenvolver um novo modelo para o JSSP e denominado de (MLJ). De forma complementar, exploramos a estrutura da solução do problema para desenvolver novas desigualdades válidas para o JSSP com base no tempo de processamento acumulado a priori e a posteriori da execução de um trabalho em uma dada máquina. Adicionamos essas desigualdades nos modelos de Manne (1960), Liao e You (1992) e (MLJ), denominados esses novos modelos como (M2), (L2) e (MLJ2), respectivamente, e testamos em instâncias da literatura e para um novo conjunto de instâncias. Com base nos experimentos computacionais, quando comparamos os modelos com desigualdades válidas aos modelos originais, obtemos uma melhora na relaxação linear de (M2) e (L2) para as novas instâncias em cerca de 87% e conseguimos gaps tão bons quanto ou melhores em 50% delas para o modelo (M2) e de cerca de 67% delas para o modelo de (L2). Além disso, melhoramos a relaxação linear de (M2) em cerca de 84% das instâncias da literatura e conseguimos gaps tão bons quanto ou melhores em 80% delas. Por fim, verificamos que o modelo (MLJ2) teve comportamento semelhante ao de (M2). |
| Abstract: | The job-shop scheduling problem (JSSP) consists in scheduling n jobs on m machines. Each job has a processing order on the machines, it can even be a specific order for each one, and a processing time on each one. In addition, each job cannot be processed at the same time on two different machines, each machine cannot process two jobs at the same time, and if a job started processing on one machine, then this processing will be completed without interruptions. One of the objective functions for this problem is to minimize the completion of the last job processed, also known as makespan. Thus, for this objective function, the problem is NP-Hard for at least three machines and two jobs and, for this problem, the computational effort can be huge to solve the problem in real instances. Therefore, it is important to develop new models to achieve more efficient results, both in terms of the execution time and the quality of the problem solutions. For that, we explored the model of Andrade et al. (2017) for the minimal linear arrangement (MinLA) problem and we adapted the model for MinLA to develop a new model for JSSP, called (MLJ). In a complementary way, we explore the structure of the problem solution to develop new valid inequalities for JSSP based on the accumulated processing time a priori and a posteriori of the execution of a job on a given machine. We apply these inequalities for the models of Manne (1960), Liao and You (1992) and (MLJ), named of (M2),(L2) e (MLJ2), respectively, and tested them on benchmark instances from the literature and for a new set of instances. Based on the computational experiments, when we compare the models with valid inequalities to the original models, we obtain an improvement in the linear relaxation of (M2) and (L2) for the new instances by about 87% and we obtained gaps as good as or better in 50% of them for the model (M2) and about 67% of them for the model (L2). In addition, we improved the linear relaxation of (M2) in about 84% of the instances from the literature and achieved gaps as good as or better in 80% of them. Finally, we found that the model (MLJ2) had a similar behavior of model (M2). |
| URI: | http://www.repositorio.ufc.br/handle/riufc/59600 |
| Appears in Collections: | DEMA - Dissertações defendidas na UFC |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2021_dis_jcajunior.pdf | 1,71 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.