NOPT042 Constraint programming: Tutorial 6 – Scheduling¶
First, leftovers from the previous tutorial...¶
In [1]:
%load_ext ipicat
Picat version 3.7
Scheduling¶
Example: moving¶
A simple scheduling problem: Four friends are moving. The table shows how much time and how many people are necessary to move each item. Schedule the moving to minimize total time. (Adapted from R. Barták's tutorial; check the SICStus Prolog model.)
| Item | Time (min) | People |
|---|---|---|
| piano | 45 | 4 |
| chair | 10 | 1 |
| bed | 25 | 3 |
| table | 15 | 2 |
| couch | 30 | 3 |
| cat | 15 | 1 |
In [2]:
!cat moving/instance.pi
instance(NumPeople, Items, Duration, People) =>
NumPeople = 4,
Items = ["piano", "chair", "bed", "table", "couch", "cat"],
Duration = [45, 10, 25, 15, 30, 15],
People = [4, 1, 3, 2, 3, 1].
In [3]:
#!cat moving/moving.pi
How to improve the model?
The cumulative global constraint¶
For the above problem we can use the following global constraint:
cumulative(StartTimes, Durations, Resources, Limit)
which means that we have Limit of resource available, each item starts at StartTimes[i], takes Durations[i] time and consumes Resources[i] of the resource.
More about the constraint cumulative:
- Picat on GitHub (unofficial)
- Global Constraint Catalog: the cumulative constraint - see the references
NOPT042 Constraint programming: Tutorial 6 – Scheduling