Skip to Main content Skip to Navigation
Conference papers

Using Approximation within Constraint Programming to Solve the Parallel Machine Scheduling Problem with Additional Unit Resources

Abstract : In this paper, we consider the Parallel Machine Scheduling Problem with Additional Unit Resources, which consists in scheduling a set of n jobs on m parallel unrelated machines and subject to exactly one of r unit resources. This problem arises from the download of acquisitions from satellites to ground stations. We first introduce two baseline constraint models for this problem. Then, we build on an approximation algorithm for this problem, and we discuss about the efficiency of designing an improved constraint model based on these approximation results. In particular, we introduce new constraints that restrict search to executions of the approximation algorithm. Finally, we report experimental data demonstrating that this model significantly outperforms the two reference models.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.laas.fr/hal-02907067
Contributor : Emmanuel Hebrard <>
Submitted on : Thursday, July 30, 2020 - 3:09:09 PM
Last modification on : Thursday, June 10, 2021 - 3:01:52 AM
Long-term archiving on: : Tuesday, December 1, 2020 - 7:19:13 AM

File

AAAI_2020 (4).pdf
Files produced by the author(s)

Identifiers

Citation

Arthur Godet, Xavier Lorca, Emmanuel Hébrard, Gilles Simonin. Using Approximation within Constraint Programming to Solve the Parallel Machine Scheduling Problem with Additional Unit Resources. AAAI'20 - Thirty-Fourth AAAI Conferance on Artificial Intelligence, Feb 2020, New-York, United States. pp.1512-1519, ⟨10.1609/aaai.v34i02.5510⟩. ⟨hal-02907067⟩

Share

Metrics

Record views

124

Files downloads

126