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

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



PDF
Thumbnail PDF

File

LIPIcs.CP.2022.41.pdf
  • Filesize: 0.83 MB
  • 18 pages

Document Identifiers

Author Details

Felix Winter
  • Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, DBAI, TU Wien, Austria
Sebastian Meiswinkel
  • MCP Algorithm Factory, MCP GmbH, Wien, Austria
Nysret Musliu
  • Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, DBAI, TU Wien, Austria
Daniel Walkiewicz
  • MCP Algorithm Factory, MCP GmbH, Wien, Austria

Cite AsGet BibTex

Felix Winter, Sebastian Meiswinkel, Nysret Musliu, and Daniel Walkiewicz. Modeling and Solving Parallel Machine Scheduling with Contamination Constraints in the Agricultural Industry. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 41:1-41:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CP.2022.41

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.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Planning and scheduling
Keywords
  • Parallel Machine Scheduling
  • Contamination Constraints
  • Constraint Programming
  • Mixed Integer Quadratic Progamming
  • Metaheuristics
  • Local Search
  • Simulated Annealing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. IBM ILOG CPLEX Optimization Studio 20.1.0. User’s manual for cplex, November 2021. URL: https://www.ibm.com/docs/en/icos/20.1.0?topic=cplex-users-manual.
  2. Ali Allahverdi. The third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research, 246(2):345-378, October 2015. Google Scholar
  3. Ali Allahverdi, Jatinder N. D Gupta, and Tariq Aldowaisan. A review of scheduling research involving setup considerations. Omega, 27(2):219-239, April 1999. Google Scholar
  4. Ali Allahverdi, C. T. Ng, T. C. E. Cheng, and Mikhail Y. Kovalyov. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3):985-1032, June 2008. Google Scholar
  5. Abdoul Bitar, Stéphane Dauzère-Pérès, and Claude Yugma. Unrelated parallel machine scheduling with new criteria: Complexity and models. Computers & Operations Research, 132:105291, August 2021. Google Scholar
  6. Quang-Vinh Dang, Thijs van Diessen, Tugce Martagan, and Ivo Adan. A matheuristic for parallel machine scheduling with tool replacements. European Journal of Operational Research, 291(2):640-660, June 2021. Google Scholar
  7. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL: https://www.gurobi.com.
  8. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):671-680, May 1983. Google Scholar
  9. Chuleeporn Kusoncum, Kanchana Sethanan, Rapeepan Pitakaso, and Richard F. Hartl. Heuristics with novel approaches for cyclical multiple parallel machine scheduling in sugarcane unloading systems. International Journal of Production Research, 59(8):2479-2497, April 2021. Google Scholar
  10. Philippe Laborie. IBM ILOG CP Optimizer for Detailed Scheduling Illustrated on Three Problems. In Willem-Jan van Hoeve and John N. Hooker, editors, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, pages 148-162, Berlin, Heidelberg, 2009. Springer. Google Scholar
  11. Philippe Laborie, Jérôme Rogerie, Paul Shaw, and Petr Vilím. IBM ILOG CP optimizer for scheduling. Constraints, 23(2):210-250, April 2018. Google Scholar
  12. Maximilian Moser, Nysret Musliu, Andrea Schaerf, and Felix Winter. Exact and metaheuristic approaches for unrelated parallel machine scheduling. Journal of Scheduling, December 2021. Google Scholar
  13. Juan C. Yepes-Borrero, Federico Perea, Rubén Ruiz, and Fulgencia Villa. Bi-objective parallel machine scheduling with additional resources during setups. European Journal of Operational Research, 292(2):443-455, July 2021. Google Scholar
  14. Pinar Yunusoglu and Seyda Topaloglu Yildiz. Constraint programming approach for multi-resource-constrained unrelated parallel machine scheduling problem with sequence-dependent setup times. International Journal of Production Research, 0(0):1-18, February 2021. Google Scholar
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