How to solve a Constraint Satisfaction Problem for Scheduling

Question

This presentation describes several algorithms for solving a CSP for scheduling.

Say I have a few processes with some constraints:

a before c
c before b
b after d
c 50% more important than e
give d at least 20% of the total running time
f before and after d
g after f only if b is still running
run h if there is at least 20% free memory available.
interrupt h with i for a minute if h runs longer than 5 minutes.
etc.

Wondering how I go about writing that in constraints, if they can be written as binary constraints (not sure all of them are binary), and the rough idea of how to go about "solving" the system. That is, figuring out an ordering and duration of the processes that satisfies all the constraints. I tried to include a few various types of variables to make it more realistic:

• Time.
• Resources. (memory available).
• Prioritization. (50% more important).

If I were to write the constraints out I would do:

a.start < c.start
c.start < b.start
b.start > d.start
e.priority = 0.5 * c.priority
d.duration = 0.2 * system.duration
f.start < d.start && f.end > d.end
g.start > f.start if b.running
if system.memory < system.memory.total * 0.2 then start h (this one is trickier)
if h.duration > 5 min then interrupt h && start i && stop i when i.duration == 1 min

I am not sure how to write start i and stop i as constraints, and the if-then statements.

I would then say the variables are:

a.start
b.start
c.start
d.start
f.start
g.start
d.end
f.end
c.priority
e.priority
d.duration
h.duration
i.duration
system.duration
system.memory
system.memory.total

Then the domain of the variables I am not sure of. The times can be any integer timestamp, so maybe that's within a few million integers at ms resolution. Then the priority is a percent. And c.priority seems like it is read-only, so not sure if we need to initialize some of the variables before.

So we have the 3 components of a CSP = (V, D, C), variables, domains, and constraints. I am not sure I did them correctly.

After defining them correctly, I am looking to understand how the forward checking algorithm works. I don't see yet roughly how you navigate the "constraint graph" to assign values to the variables. Just looking for a basic explanation using the pieces from the example provided above.

To summarize, my questions are:

1. If I modeled the CSP = (V, D, C) components properly. Or what I did wrong.
2. A quick explanation of how any of the algorithms work by using the V/D/C from above as an example. I would like to see from something practical how to actually go about "solving" the constraint system at a high level, so I can then have the tools to figure out how to solve this specific problem.

Answer 1

There are a couple of problems with the modelling of this problem.

First, CSP work best as a formalism if there is a known, fixed number of values to determine. Your problem description states that h may have to be interrupted and restarted an unknown number of times, so there isn't one value to compute for h, but several (starting time, stopping time, and an unknown number of each).

Similarly, values like system.memory will be changing throughout the task - this is not so much a value to determine as an entire time series. Again, it's not even clear how many values this should be represented as.

You also seem to assume that the running time of each task cannot be determined in advance, but how do you determine it, then? Can you just decide "I'll give d 120 CPU seconds for executing, and if it doesn't complete, tough luck"? If so, what stops the algorithm from simply assigning no time to everything and output a trivial schedule? Presumably there are additional conditions of the form "complete as many tasks as possible", but that means that this isn't really a CSP anymore, but a constraint optimization problem.

Overall, I'm not sure that this problem is modeled best as constraint satisfaction. Probably it is better to use constraint logic only to compute the order of tasks to execute, and use a more general scheduling method to determine the concrete solution.