KR2021Proceedings of the 18th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning

Online event. November 3-12, 2021.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-99-7

Sponsored by
Published by

Copyright © 2021 International Joint Conferences on Artificial Intelligence Organization

Randomized Problem-Relaxation Solving for Over-Constrained Schedules

  1. Patrick Rodler(Alpen-Adria Universität Klagenfurt)
  2. Erich Teppan(Alpen-Adria Universität Klagenfurt)
  3. Dietmar Jannach(Alpen-Adria Universität Klagenfurt)


  1. Applications of KR in logistics
  2. Development, deployment, and evaluation of KR systems to solve real-world problems


Optimal production planning in the form of job shop scheduling problems (JSSP) is a vital problem in many industries. In practice, however, it can happen that the volume of jobs (orders) exceeds the production capacity for a given planning horizon. A reasonable aim in such situations is the completion of as many jobs as possible in time (while postponing the rest). We call this the Job Set Optimization Problem (JOP). Technically, when constraint programming is used for solving JSSPs, the formulated objective in the constraint model can be adapted so that the constraint solver addresses JOP, i.e., searches for schedules that maximize the number of timely finished jobs. However, also highly specialized solvers which proved very powerful for JSSPs may struggle with the increased complexity of the reformulated problem and may fail to generate a JOP solution given practical computation timeouts. As a remedy, we suggest a framework for solving multiple randomly modified instances of a relaxation of the JOP, which allows to gradually approach a JOP solution. The main idea is to have one module compute subset-minimal job sets to be postponed, and another one effectuating that random job sets are found. Different algorithms from literature can be used to realize these modules. Using IBM’s cutting-edge CP Optimizer suite, experiments on well-known JSSP benchmark problems show that using the proposed framework consistently leads to more scheduled jobs for various computation timeouts than a standalone constraint solver approach.