Robust Scheduling

This page contains the code of a solver to build optimized robust schedules for problems where tasks have fixed or even uncertain duration. The approach couples an off-line optimizer and an simple on-line scheduling policy and was moslty developed in the context of the FP7 Project SMECY.

The off-line optimizer is based on the Precedence Constraint Posting technique, i.e. a "schedule" is in fact a set of precedence constraints that make the original graph conflict free. The solver searches for feasible schedules by branching over Minimal Critical Sets, which can be identified using a number of different techniques.

The on-line scheduling policy can be arbitrarily chosen, provided that some basic specifications are satisfied. In detail, we support two broad classes of on-line schedulers:

• Non-delay schedulers: an policy in this classes never delays a task if all its predecessors have completed executions and enough resources are available. Many widely adopted methods fall into this category (e.g. First Come First Served, Fixed Priority Scheduling...). In case a non-delay scheduler is used, it is possible to instruct the off-line optimizer to take into account the policy behavior: this results in the addition of fewer precedence constraints and hence lower run-time overhead.
• General on-line schedulers: a policy in this class may abritrarily decide to delay a task. This may be useful if the optimized application is not the only one running on the system, so that a task may be delayed to perform some computation belonging to a different application. In this case, the on-line scheduler must also guarantee the satisfactio of a set of restricted deadlines, provided by the off-line optimizer.

The code is known to compile on Ubuntu Linux distributions. Dependencies include the boost library and the IBM ILOG CP suite (version 1.5 or above), available for free for academic use via the IBM Academic Initiative. The code is released with a detailed README file, containing instruction about how to build and run the software. Moreover, we include a subset of Resource Constraint Scheduling Problem instances from the PSPlib library, in the input format required by the PCP scheduler.

Here are the links to al available resources:

• Optimizer code + examples from the PSPlib (all with fixed durations)
• Synthetic task graph instances, pre-mapped on two different platforms (NOTE: you need to change some compile time options to make this work, in particular the minimum/maximum property names: check the README about this)

If you need further information, you can contact me via email or refer to references [bib]467[/bib][bib]lombardi2011robust[/bib][bib]DBLP:conf/cp/LombardiM10[/bib][bib]DBLP:conf/cp/LombardiM09[/bib]