×

zbMATH — the first resource for mathematics

Forward-checking filtering for nested cardinality constraints: application to an energy cost-aware production planning problem for tissue manufacturing. (English) Zbl 06598660
Quimper, Claude-Guy (ed.), Integration of AI and OR techniques in constraint programming. 13th international conference, CPAIOR 2016, Banff, AB, Canada, May 29 – June 1, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-33953-5/pbk; 978-3-319-33954-2/ebook). Lecture Notes in Computer Science 9676, 108-124 (2016).
Summary: 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 \( \mathtt {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 \(\mathcal {O}(log(p))\) instead of \(\mathcal {O}(p)\). We describe an energy cost-aware CP model for tissue manufacturing production planning including the \( \mathtt {nested \_ gcc} \). Our experiments on real historical data illustrates the scalability of the approach using a large neighborhood search (LNS).
For the entire collection see [Zbl 1337.68017].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI