Browsing by Author "Araujo, Janniele Aparecida Soares"

Now showing 1 - 3 of 3
  • No Thumbnail Available
    Item
    An integer programming approach to the multimode resource-constrained multiproject scheduling problem.
    (2015) Toffolo, Túlio Ângelo Machado; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Araujo, Janniele Aparecida Soares
    The project scheduling problem (PSP) is the subject of several studies in computer science, mathematics, and operations research because of the hardness of solving it and its practical importance. This work tackles an extended version of the problem known as the multimode resourceconstrained multiproject scheduling problem. A solution to this problem consists of a schedule of jobs from various projects, so that the job allocations do not exceed the stipulated limits of renewable and nonrenewable resources. To accomplish this, a set of execution modes for the jobs must be chosen, as the jobs’ duration and amount of needed resources vary depending on the mode selected. Finally, the schedule must also consider precedence constraints between jobs. This work proposes heuristic methods based on integer programming to solve the PSP considered in the Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA) 2013 Challenge. The developed solver was ranked third in the competition, being able to find feasible and competitive solutions for all instances and improving best known solutions for some problems.
  • No Thumbnail Available
    Item
    Mixed-integer linear programming based approaches for the resource constrained project scheduling problem.
    (2019) Araujo, Janniele Aparecida Soares; Santos, Haroldo Gambini; Santos, Haroldo Gambini; Barboza, Eduardo Uchoa; Souza, Marcone Jamilson Freitas; Jena, Sanjay Dominik; Toffolo, Túlio Ângelo Machado
    Resource Constrained Project Scheduling Problems (RCPSPs) without preemption are well-known NP-hard combinatorial optimization problems. A feasible RCPSP solution consists of a time-ordered schedule of jobs with corresponding execution modes, respecting precedence and resources constraints. First, in this thesis, we provide improved upper bounds for many hard instances from the literature by using methods based on Stochastic Local Search (SLS). As the most contribution part of this work, 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 conict 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-the-art mixed-integer linear programming solver to nd provably optimal solutions for 754 previously open instances of different variants of the RCPSPs, which was not possible using the original linear programming formulations.
  • No Thumbnail Available
    Item
    Strong bounds for resource constrained project scheduling : preprocessing and cutting planes.
    (2020) Araujo, Janniele Aparecida Soares; Santos, Haroldo Gambini; Gendron, Bernard; Jena, Sanjay Dominik; Brito, Samuel Souza; Souza, Danilo Santos
    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.