License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2022.41
URN: urn:nbn:de:0030-drops-166701
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16670/
Go to the corresponding LIPIcs Volume Portal

Winter, Felix ; Meiswinkel, Sebastian ; Musliu, Nysret ; Walkiewicz, Daniel

Modeling and Solving Parallel Machine Scheduling with Contamination Constraints in the Agricultural Industry

pdf-format:
LIPIcs-CP-2022-41.pdf (0.8 MB)

Abstract

Modern-day factories of the agricultural industry need to produce and distribute large amounts of compound feed to handle the daily demands of livestock farming. As a highly-automated production process is utilized to fulfill the large-scale requirements in this domain, finding efficient machine schedules is a challenging task which requires the consideration of complex constraints and the execution of optional cleaning jobs to prevent a contamination of the final products. Furthermore, it is critical to minimize job tardiness in the schedule, since the truck routes which are used to distribute the products to customers are sensitive to delays. Thus, there is a strong need for efficient automated methods which are able to produce optimized schedules in this domain.
This paper formally introduces a novel real-life problem from this area and investigates constraint-modeling techniques as well as a metaheuristic approach to efficiently solve practical scenarios. In particular, we investigate two innovative constraint programming model variants as well as a mixed integer quadratic programming formulation to model the contamination constraints which require an efficient utilization of variables with a continuous domain. To tackle large-scale instances, we additionally provide a local search approach based on simulated annealing that utilizes problem-specific neighborhood operators.
We provide a set of new real-life problem instances that we use in an extensive experimental evaluation of all proposed approaches. Computational results show that our models can be successfully used together with state-of-the-art constraint solvers to provide several optimal results as well as high-quality bounds for many real-life instances. Additionally, the proposed metaheuristic approach could reach many optimal results and delivers the best upper bounds on many of the large practical instances in our experiments.

BibTeX - Entry

@InProceedings{winter_et_al:LIPIcs.CP.2022.41,
  author =	{Winter, Felix and Meiswinkel, Sebastian and Musliu, Nysret and Walkiewicz, Daniel},
  title =	{{Modeling and Solving Parallel Machine Scheduling with Contamination Constraints in the Agricultural Industry}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{41:1--41: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/opus/volltexte/2022/16670},
  URN =		{urn:nbn:de:0030-drops-166701},
  doi =		{10.4230/LIPIcs.CP.2022.41},
  annote =	{Keywords: Parallel Machine Scheduling, Contamination Constraints, Constraint Programming, Mixed Integer Quadratic Progamming, Metaheuristics, Local Search, Simulated Annealing}
}

Keywords: Parallel Machine Scheduling, Contamination Constraints, Constraint Programming, Mixed Integer Quadratic Progamming, Metaheuristics, Local Search, Simulated Annealing
Collection: 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Issue Date: 2022
Date of publication: 23.07.2022
Supplementary Material: Software (Source Code, Benchmark Set, and Results): https://doi.org/10.5281/zenodo.6797397

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI