3 Presentations

• 
  03:30 PM - 03:55 PM

  Constraints for Calendars and Overtime in Ship Refitting Projects

  • Samuel Cloutier, presenter, Université Laval
  • Claude-Guy Quimper, Université Laval

  We study the problem of cumulative scheduling augmented with calendars and overtime. This problem is a variant of cumulative scheduling where the durations of the tasks are variables subject to other constraints such as holidays and scheduled overtime.
  To solve this problem, we propose new constraints to model these calendar constraints with overtime.
  We introduce a Calendar constraint which verifies that a task follows a given calendar with overtime and holidays. We also introduce a CumulativeOvertime constraint which is a variant of the Cumulative constraint that also reasons with the overtime and the holidays when propagating according to the resource consumption.
  Experimental results show that the use of the Calendar constraint offers a speedup greater than 2 on the instances optimally solved and finds better solutions on more than 78% of the remaining instances when compared to a decomposition of the constraint.
  We also show that the use of our CumulativeOvertime constraint further improves these results.

• 
  03:55 PM - 04:20 PM

  Advancements in priority rules based heuristics

  • Oussama Siwane, presenter, Polytechnique Montreal, Gerad
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal
  • Robert Pellerin, École Polytechnique de Montréal

  Scheduling problems belong to the strong NP-hard class of optimization problems. The attempts to solve them are focused primarily on heuristic approaches. Within these methods, we find the priority rules based heuristics, where tasks are ranked relatively to a priority calculated for each task using one or multiple network properties related to the project, the activities, or the resources. Some limitations of these heuristics reside in the replicated solutions generated from different rules and the excessive intensification work required to find a better solution. Our research focuses on diversifying the set of solutions generated by the priority rules based heuristics. In this work, we enhance the priority computation by developing a new graph decomposition and a selection buffer. Combined with the properties of the network, we increase the chances of reaching better solutions in fewer iterations. We tested this new procedure on instances of the Resource Constrained Project Scheduling Problem from the PSPLIB dataset and other real-life examples. The results show that this new procedure gives distinctive solutions and leads to better makespan in fewer iterations than the application of traditional priority rules .

• 
  04:20 PM - 04:45 PM

  A New RCCP Model for Improving Tactical Project Planning

  • Anis Noureddine, presenter, Polytechnique Montréal
  • Robert Pellerin, École Polytechnique de Montréal
  • Francois Soumis, GERAD et Polytechnique

  We introduce a new continuous-mixed model to address tactical project planning, known as the Rough Cut Capacity Planning (RCCP) model. Our study explores the Resource-driven variants of the RCCP model. We conduct a detailed comparison with one of the best models found in the literature, testing various instances to emphasize the benefits and effectiveness of each approach. The new model generally performs better, achieving resolution times up to seven times faster. We employ a destructive method to arrive at the optimal solution to enhance the resolution process. This method is developed after analyzing the results of solving the model with a Mixed Integer Programming (MIP) solver. Initially, 81 out of 480 instances were unresolved within 5 000 seconds. Applying the destructive method has allowed us to reduce the number of unresolved instances to 18.