Use este identificador para citar ou linkar para este item:
http://www.repositorio.ufop.br/jspui/handle/123456789/12841
Título: | Strong bounds for resource constrained project scheduling : preprocessing and cutting planes. |
Autor(es): | Araujo, Janniele Aparecida Soares Santos, Haroldo Gambini Gendron, Bernard Jena, Sanjay Dominik Brito, Samuel Souza Souza, Danilo Santos |
Palavras-chave: | Mixed-integer linear programming |
Data do documento: | 2020 |
Referência: | ARAUJO, J. A. S. et al. Strong bounds for resource constrained project scheduling: preprocessing and cutting planes. Computers & Operations Research, v. 113, jan. 2020. Disponível em: <https://www.sciencedirect.com/science/article/pii/S0305054819302242>. Acesso em: 10 mar. 2020. |
Resumo: | Resource Constrained Project Scheduling Problems (RCPSPs) without preemption are well-known N Phard combinatorial optimization problems. A feasible RCPSP solution consists of a time-ordered schedule of jobs with corresponding execution modes, respecting precedence and resources constraints. In this paper, we propose a cutting plane algorithm to separate five different cut families, as well as a new preprocessing routine to strengthen resource-related constraints. New lifted versions of the well-known precedence and cover inequalities are employed. At each iteration, a dense conflict graph is built considering feasibility and optimality conditions to separate cliques, odd-holes and strengthened Chvátal-Gomory cuts. The proposed strategies considerably improve the linear relaxation bounds, allowing a state-of-theart mixed-integer linear programming solver to find provably optimal solutions for 754 previously open instances of different variants of the RCPSPs, which was not possible using the original linear programming formulations. |
URI: | http://www.repositorio.ufop.br/handle/123456789/12841 |
Link para o artigo: | https://www.sciencedirect.com/science/article/abs/pii/S0305054819302242?via%3Dihub |
DOI: | https://doi.org/10.1016/j.cor.2019.104782 |
ISSN: | 0305-0548 |
Aparece nas coleções: | DECSI - Artigos publicados em periódicos |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
ARTIGO_StrongBoundsResource.pdf Restricted Access | 1,14 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.