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:
- 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:
- If I modeled the CSP = (V, D, C) components properly. Or what I did wrong.
- 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.