Search Results

Documents authored by Quimper, Claude-Guy

Document
DOI: 10.4230/LIPIcs.CP.2024.7
Cumulative Scheduling with Calendars and Overtime

Authors: Samuel Cloutier and Claude-Guy Quimper

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
In project scheduling, calendar considerations can increase the duration of a task when its execution overlaps with holidays. On the other hand, the use of overtime may decrease the task’s duration. We introduce the CalendarOvertime constraint which verifies that a task follows a calendar with overtime and holidays. We also introduce the CumulativeOvertime constraint, a variant of the Cumulative constraint, that also reasons with the calendars when propagating according to the resource consumption, the overtime, and the holidays. Experimental results of a RCPSP model on the PSPLIB, BL, and PACK instances augmented with calendars and overtime show that the use of the CalendarOvertime constraint offers a speedup greater than 2.9 on the instances optimally solved and finds better solutions on more than 79% 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.
Cite as

Samuel Cloutier and Claude-Guy Quimper. Cumulative Scheduling with Calendars and Overtime. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cloutier_et_al:LIPIcs.CP.2024.7,
  author =	{Cloutier, Samuel and Quimper, Claude-Guy},
  title =	{{Cumulative Scheduling with Calendars and Overtime}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.7},
  URN =		{urn:nbn:de:0030-drops-206927},
  doi =		{10.4230/LIPIcs.CP.2024.7},
  annote =	{Keywords: Constraint programming, Scheduling, Global constraints, Calendars, Overtime, Cumulative constraint, Time-Tabling}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.30
Learning Precedences for Scheduling Problems with Graph Neural Networks

Authors: Hélène Verhaeghe, Quentin Cappart, Gilles Pesant, and Claude-Guy Quimper

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
The resource constrained project scheduling problem (RCPSP) consists of scheduling a finite set of resource-consuming tasks within a temporal horizon subject to resource capacities and precedence relations between pairs of tasks. It is NP-hard and many techniques have been introduced to improve the efficiency of CP solvers to solve it. The problem is naturally represented as a directed graph, commonly referred to as the precedence graph, by linking pairs of tasks subject to a precedence. In this paper, we propose to leverage the ability of graph neural networks to extract knowledge from precedence graphs. This is carried out by learning new precedences that can be used either to add new constraints or to design a dedicated variable-selection heuristic. Experiments carried out on RCPSP instances from PSPLIB show the potential of learning to predict precedences and how they can help speed up the search for solutions by a CP solver.
Cite as

Hélène Verhaeghe, Quentin Cappart, Gilles Pesant, and Claude-Guy Quimper. Learning Precedences for Scheduling Problems with Graph Neural Networks. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{verhaeghe_et_al:LIPIcs.CP.2024.30,
  author =	{Verhaeghe, H\'{e}l\`{e}ne and Cappart, Quentin and Pesant, Gilles and Quimper, Claude-Guy},
  title =	{{Learning Precedences for Scheduling Problems with Graph Neural Networks}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{30:1--30:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.30},
  URN =		{urn:nbn:de:0030-drops-207150},
  doi =		{10.4230/LIPIcs.CP.2024.30},
  annote =	{Keywords: Scheduling, Precedence graph, Graph neural network}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.6
Acquiring Maps of Interrelated Conjectures on Sharp Bounds

Authors: Nicolas Beldiceanu, Jovial Cheukam-Ngouonou, Rémi Douence, Ramiz Gindullin, and Claude-Guy Quimper

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
To automate the discovery of conjectures on combinatorial objects, we introduce the concept of a map of sharp bounds on characteristics of combinatorial objects, that provides a set of interrelated sharp bounds for these combinatorial objects. We then describe a Bound Seeker, a CP-based system, that gradually acquires maps of conjectures. The system was tested for searching conjectures on bounds on characteristics of digraphs: it constructs sixteen maps involving 431 conjectures on sharp lower and upper-bounds on eight digraph characteristics.
Cite as

Nicolas Beldiceanu, Jovial Cheukam-Ngouonou, Rémi Douence, Ramiz Gindullin, and Claude-Guy Quimper. Acquiring Maps of Interrelated Conjectures on Sharp Bounds. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{beldiceanu_et_al:LIPIcs.CP.2022.6,
  author =	{Beldiceanu, Nicolas and Cheukam-Ngouonou, Jovial and Douence, R\'{e}mi and Gindullin, Ramiz and Quimper, Claude-Guy},
  title =	{{Acquiring Maps of Interrelated Conjectures on Sharp Bounds}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.6},
  URN =		{urn:nbn:de:0030-drops-166353},
  doi =		{10.4230/LIPIcs.CP.2022.6},
  annote =	{Keywords: Acquisition of conjectures, digraphs, bounds}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.10
A Constraint Programming Approach to Ship Refit Project Scheduling

Authors: Raphaël Boudreault, Vanessa Simard, Daniel Lafond, and Claude-Guy Quimper

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Ship refit projects require ongoing plan management to adapt to arising work and disruptions. Planners must sequence work activities in the best order possible to complete the project in the shortest time or within a defined period while minimizing overtime costs. Activity scheduling must consider milestones, resource availability constraints, and precedence relations. We propose a constraint programming approach for detailed ship refit planning at two granularity levels, daily and hourly schedule. The problem was modeled using the Cumulative global constraint, and the Solution-Based Phase Saving heuristic was used to speedup the search, thus achieving the industrialization goals. Based on the evaluation of seven realistic instances over three objectives, the heuristic strategy proved to be significantly faster to find better solutions than using a baseline search strategy. The method was integrated into Refit Optimizer, a cloud-based prototype solution that can import projects from Primavera P6 and optimize plans.
Cite as

Raphaël Boudreault, Vanessa Simard, Daniel Lafond, and Claude-Guy Quimper. A Constraint Programming Approach to Ship Refit Project Scheduling. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{boudreault_et_al:LIPIcs.CP.2022.10,
  author =	{Boudreault, Rapha\"{e}l and Simard, Vanessa and Lafond, Daniel and Quimper, Claude-Guy},
  title =	{{A Constraint Programming Approach to Ship Refit Project Scheduling}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.10},
  URN =		{urn:nbn:de:0030-drops-166396},
  doi =		{10.4230/LIPIcs.CP.2022.10},
  annote =	{Keywords: Ship refit, planning, project management, constraint programming, scheduling, optimization, resource-constrained project scheduling problem}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.15
Constraint Acquisition Based on Solution Counting

Authors: Christopher Coulombe and Claude-Guy Quimper

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
We propose CABSC, a system that performs Constraint Acquisition Based on Solution Counting. In order to learn a Constraint Satisfaction Problem (CSP), the user provides positive examples and a Meta-CSP, i.e. a model of a combinatorial problem whose solution is a CSP. This Meta-CSP allows listing the potential constraints that can be part of the CSP the user wants to learn. It also allows stating the parameters of the constraints, such as the coefficients of a linear equation, and imposing constraints over these parameters. The CABSC reads the Meta-CSP using an augmented version of the language MiniZinc and returns the CSP that accepts the fewest solutions among the CSPs accepting all positive examples. This is done using a branch and bound where the bounding mechanism makes use of a model counter. Experiments show that CABSC is successful at learning constraints and their parameters from positive examples.
Cite as

Christopher Coulombe and Claude-Guy Quimper. Constraint Acquisition Based on Solution Counting. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{coulombe_et_al:LIPIcs.CP.2022.15,
  author =	{Coulombe, Christopher and Quimper, Claude-Guy},
  title =	{{Constraint Acquisition Based on Solution Counting}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.15},
  URN =		{urn:nbn:de:0030-drops-166449},
  doi =		{10.4230/LIPIcs.CP.2022.15},
  annote =	{Keywords: Constraint acquisition, CSP, Model counting, Solution counting}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.380
A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times

Authors: Alejandro Lopez-Ortiz and Claude-Guy Quimper

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
Consider the problem of scheduling a set of tasks of length p without preemption on $m$ identical machines with given release and deadline times. We present a new algorithm for computing the schedule with minimal completion times and makespan. The algorithm has time complexity O(min(1,p/m)n^2) which improves substantially over the best known algorithm with complexity O(mn^2).
Cite as

Alejandro Lopez-Ortiz and Claude-Guy Quimper. A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 380-391, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{lopezortiz_et_al:LIPIcs.STACS.2011.380,
  author =	{Lopez-Ortiz, Alejandro and Quimper, Claude-Guy},
  title =	{{A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{380--391},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.380},
  URN =		{urn:nbn:de:0030-drops-30282},
  doi =		{10.4230/LIPIcs.STACS.2011.380},
  annote =	{Keywords: Scheduling}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact