Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/24733| Type: | TCC |
| Title: | Modelos de programação linear inteira para o problema de programação de tripulação |
| Authors: | Dantas, Ana Paula dos Santos |
| Advisor: | Souza, Críston Pereira de |
| Keywords: | Otimização combinatória;Programação inteira;Programação (Matemática) |
| Issue Date: | 2017 |
| Citation: | DANTAS, Ana Paula dos Santos. Modelos de programação linear inteira para o problema de programação de tripulação. 2017. TCC (Graduação em Ciência da Computação) - Universidade Federal do Ceará, Campus de Quixadá, Quixadá, 2017. |
| Abstract in Brazilian Portuguese: | Neste trabalho, propomos mudanças para o modelo apresentado em Nunes (2015), de modo a conseguir uma alocação de viagens quando consideramos todas as linhas da empresa de uma só vez. Foi feita uma análise do tempo de execução e da qualidade da solução do modelo de Nunes (2015) sem a inclusão de algumas restrições, comparando-a com o modelo quando é incluída uma solução viável inicial obtida por um modelo de Programação por Restrições desenvolvido em SOUZA (2016). Percebemos a necessidade de trabalhar individualmente as suas subdivisões do problema: Problema de Determinação de Tarefas (PDT) e Problema de Alocação de Escalas (PAE). Assim, o modelo de Nunes (2015) foi divido em dois, o modelo para o PDT é usado para criar tarefas, que são alocadas pela segunda parte, PAE. Para melhorar o PDT, foram desenvolvidas algumas heurísticas, com o intuito de diminuir o tamanho das entradas e para fornecer uma solução viável inicial ao modelo. Essas heurísticas conseguiram melhorar consideravelmente os resultados do modelo PDT. Por sua vez, o modelo PAE, que ficou mais simples devido a separação e às novas decisões de modelagem, apresentou bons resultados. |
| Abstract: | In this study, we propose adaptations to the model shown in Nunes (2015), so that this model creates workshift allocations considering all lines operated by the company. It was made an analysis on the execution time and on the quality of the solution given by the model without some of the restrictions, and comparing it to the same model with an initial feasible solution obtained by a Constraint Programming developed in SOUZA (2016). We recognize the necessity to work individually on each of the subproblems: Tasks Determination Problem (TDP) and Workshift Allocation Problem (WAP). Threfore, the model presented on Nunes (2015) was divided in two, the model for the TDP is used to create the tasks that will be allocated on the second part, WAP. To improve the TDP model, we developed two heuristics to reduce the size of the instances and provide the model with an initial feasible solution. These heuristics were able to improve the TDP model. The WAP model due to the separation and the modeling decisions, and thus, presented good results. |
| URI: | http://www.repositorio.ufc.br/handle/riufc/24733 |
| Appears in Collections: | CIÊNCIA DA COMPUTAÇÃO-QUIXADÁ - Monografias |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2017_tcc_apsdantas.pdf | 1,16 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.