NOPT042 Constraint programming: Tutorial 6 – Scheduling

First, leftovers from the previous tutorial...

%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

!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].

#!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