Scheduling using constraint programming

点击翻译按钮获取中文摘要

Scheduling is the process of allocating tasks to a time slot and a resource. Resources should not encounter overloaded periods and tasks are often subject to deadlines. Many additional constraints make the problem intractable. Solvers are computer programs that take the problem parameters as input, explore the solution space of the problem, and produce a solution. This research program aims at designing more efficient solvers that are able to produce solutions in a shorter period of time. Reaching this long-term goal will impact the industry in many different ways. Industries that schedule their operations in a time critical environment will greatly beneficiate from this research since they will obtain better schedules in a shorter period of time. We see three ways that are promising for reaching this goal. First, we want to improve key algorithms that are currently used in schedulers. Some algorithms, whose complexity has been identified as suboptimal, can be greatly improved by using simple and efficient data structures. Second, we want to explore stronger relaxations and new global constraints that can be used in a solver. Relaxations, and their associated global constraints, limit the scope of the search and let the solver focus on the most promising candidate solutions. Finally, we propose a new way of modeling scheduling problems that will improve the computation time. With new implicit models, solvers will ignore multiple details of a solution and rather focus on solving the hard part of a problem. An implicit model leads to a partial solution that specialized algorithms can efficiently complete.