Forward-Checking Filtering for Nested Cardinality Constraints: Application to an Energy Cost-Aware Production Planning Problem for Tissue Manufacturing

Dejemeppe, Cyrille;Devolder, Olivier;Lecomte, Victor;Schaus, Pierre
(2016) CPAIOR 2016: Integration of AI and OR Techniques in Constraint Programming pp 108-124 — Location: Banff, AB, Canada

Files

cpaior16-gcc.pdf
  • Open Access
  • Adobe PDF
  • 272.67 KB
Download

Details

Authors
  • Dejemeppe, CyrilleUCLouvain
    Author
  • Devolder, OlivierUCLouvain
    Author
  • Lecomte, VictorUCLouvain
    Author
  • Schaus, Pierreorcid-logoUCLouvain
    Author
Abstract
Response to electricity price fluctuations becomes increasingly important for industries with high energy demands. Consumer tissue manufacturing (toilet paper, kitchen rolls, facial tissues) is such an industry. Its production process is flexible enough to leverage partial planning reorganization allowing to reduce electricity consumption. The idea is to shift the production of the tissues (rolls) requiring more energy when electricity prices (forecasts) are lower. As production plans are subject to many constraints, not every reorganization is possible. An important constraint is the order book that translates into hard production deadlines. A Constraint Programming (CP) model to enforce the due dates can be encoded with p Global Cardinality Constraints (GCC); one for each of the p prefixes of the production variable array. This decomposition into separate GCC’s hinders propagation and should rather be modeled using the global nested_gcc constraint introduced by Zanarini and Pesant. Unfortunately it is well known that the GAC propagation does not always pay off in practice for cardinality constraints when compared to lighter Forward-Checking (FWC) algorithms. We introduce a preprocessing step to tighten the cardinality bounds of the GCC’s potentially strengthening the pruning of the individual FWC filterings. We further improve the FWC propagation procedure with a global algorithm reducing the amortized computation cost to (log(p)) instead of (p) . We describe an energy cost-aware CP model for tissue manufacturing production planning including the nested_gcc. Our experiments on real historical data illustrates the scalability of the approach using a Large Neighborhood Search (LNS).
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Dejemeppe, C., Devolder, O., Lecomte, V., & Schaus, P. (2016). Forward-Checking Filtering for Nested Cardinality Constraints: Application to an Energy Cost-Aware Production Planning Problem for Tissue Manufacturing. Lecture Notes in Computer Science, 9676(9676), 108-124. https://doi.org/10.1007/978-3-319-33954-2_9 (Original work published 2016)