pyschedule

pyschedule is python package to compute resource-constrained task schedules. Some features are:

• precedence relations: e.g. task A should be done before task B
• resource requirements: e.g. task A can be done by resource X or Y
• resource capacities: e.g. resource X can only process a few tasks

Previous use-cases include:

• school timetables: assign teachers to classes
• beer brewing: assign equipment to brewing stages
• sport schedules: assign stadiums to games

A simple pyschedule scenario where three houshold tasks need to get assigned to two persons, Alice and Bob:

from pyschedule import Scenario, solvers, plotters, alt

# the planning horizon has 10 periods
S = Scenario('household',horizon=10)

# two resources: Alice and Bob
Alice, Bob = S.Resource('Alice'), S.Resource('Bob')

# three tasks: cook, wash, and clean
cook = S.Task('cook',length=1,delay_cost=1)
wash = S.Task('wash',length=2,delay_cost=1)
clean = S.Task('clean',length=3,delay_cost=2)

# every task can be done either by Alice or Bob
cook += Alice | Bob
wash += Alice | Bob
clean += Alice | Bob

# compute and print a schedule
solvers.mip.solve(S,msg=1)
print(S.solution())

INFO: execution time for solving mip (sec) = 0.025493860244750977
INFO: objective = 1.0
[(clean, Alice, 0, 3), (cook, Bob, 0, 1), (wash, Bob, 1, 3)]

We can also plot the schedule as a GANTT-chart and write it to a file:

plotters.matplotlib.plot(S,img_filename='pics/household.png')

There are example notebooks <a href="https://github.com/timnon/pyschedule/tree/master/example-notebooks">here</a> and simpler examples in the <a href="https://github.com/timnon/pyschedule/tree/master/examples">examples folder</a>. Install it with pip:

pip install pyschedule

Limits

Note that pyschedule aims to be a general solver for small to medium-sized scheduling problems. A typical scenario that pyschedule consists of 10 resources and 100 tasks with a planning horizon of 100 periods. If your requirements are much larger than this, then an out-of-the box solution is hard to obtain. There are some ways to speed-up pyschedule (e.g. see task groups and solver parameters). It is also possible to build heuristics on top of pyschedule to solve large-scaled scheduling problems.

How to start

When creating a scenario using pyschedule, the following imports are recommended:

from pyschedule import Scenario, solvers, plotters, alt

This allows the creation of a scenario:

S = Scenario('hello_world',horizon=10)

This scenario is named hello_world and has a time horizon of 10 periods. The granularity of the periods depends on your problem, e.g. a period could be an hour, a week, or a day. However, having far more than 100 periods makes the computation of a schedule quite hard. Some tricks to reduce the number of periods are:

• Remove periods which are not used, like hours during the night.
• Move to a higher granularity, e.g. try a granularity of 2 hours instead of 1 hour and round tasks up if necessary.

We need at least one resource in a scenario:

R = S.Resource('R')

It is convenient to have identical resource and variable names, like R. During each period, some task can be schedule this period. A resource can be anything from a person to an object like a machine in a factory. It is only required that a resource can be used by at most one task in every period.

Next we add a task to the scenario:

T = S.Task('T',length=1,delay_cost=1)

This task has length 1, that is, it requires only 1 period to finish. Since 1 is the default length of a task, we would not have to set this explicitely. Moreover, we set the delay cost to 1, that is, delaying this job for one period increases the cost of a schedule by 1, which motivates to finish this task as early as possible.

We define that task T requires resource R as follows:

T += R

Then we compute and print a schedule as follows:

solvers.mip.solve(S,msg=0)
print(S.solution())

INFO: execution time for solving mip (sec) = 0.014132976531982422
INFO: objective = 0.0
[(T, R, 0, 1)]

The output first shows the time required to solve the problem. Also the objective is plotted. Since the cost of this schedule is only the delay cost of task T, which is schedule in period 0, the total cost is 0 as well. The standard way to present a schedule is a list of task-resource pairs with time requirements. E.g. the output above says that task T should be scheduled on resource R from period 0 to 1.

Costs

It is not necessary to define cost in a scenario. In this case, a solver will simply try to find a feasible schedule. Not defining any cost will sometimes even speed up the computation. However, in most scenarios, setting at least some delay cost makes sense.

Delay Cost

We set the delay cost of a task to 1 as follows:

T = S.Task('T',delay_cost=1)

This means that if this task is scheduled in period 0, then there will no delay cost, if it is schedule in period 1, there will be total cost 1 and so on. Hence, it makes sense to schedule this task as early as possible. Note that delay cost can also be negative, in which case a task will be pushed to the end of a schedule. Also note that a task with a higher delay cost is more likely to be scheduled earlier if there are no other constraints that are preventing this. The default delay cost is None.

Schedule Cost

Schedule cost can be used for optional tasks, that is, we provide some positive or negative reward if a task is scheduled:

from pyschedule import Scenario, solvers, plotters, alt
S = Scenario('schedule_cost',horizon=10)
R = S.Resource('R')

# not setting a schedule cost will set it to None
T0 = S.Task('T0',length=2,delay_cost=1)
# setting the schedule cost of T1 to -1
T1 = S.Task('T1',length=2,delay_cost=1,schedule_cost=-1)

T0 += R
T1 += R
solvers.mip.solve(S,msg=1)
print(S.solution())

INFO: execution time for solving mip (sec) = 0.016648054122924805
INFO: objective = 0.0
[(T0, R, 0, 2)]

In the schedule above, scheduling task T1 with schedule cost -1 would decrease the total cost by 1, but then we would have to schedule both tasks T0 and T1, and hence one of them would have to start in period 2. This would result an additional delay cost of 2. Consequently, it makes more sense not to schedule T1.

Resource Cost

Using a resource for some periods might imply additional resource cost:

from pyschedule import Scenario, solvers, plotters, alt
S = Scenario('resource_cost',horizon=10)

# assign a cost per period of 5
R = S.Resource('R',cost_per_period=5)

T = S.Task('T',length=2,delay_cost=1)
T += R
solvers.mip.solve(S,msg=1)
print(S.solution())

INFO: execution time for solving mip (sec) = 0.01111602783203125
INFO: objective = 10.0
[(T, R, 0, 2)]

The total cost of the computed schedule is 5 although the single task is scheduled in the first period. This is due to the fact that scheduling any task costs 5 on resource R.

Task and Resource Lists

To simplify the definition of tasks, it is possible to define task lists:

from pyschedule import Scenario, solvers, plotters, alt
S = Scenario('many_tasks',horizon=10)

# create 5 tasks of the same type
T = S.Tasks('T',num=5,length=1,delay_cost=1)

print(T)

[T0, T1, T2, T3, T4]

We created 5 tasks of length 1 and delay cost 1. The index of the tasks is padded to the end of the given task name. Therefore, avoid task names ending with digits. Note that it would also be possible to create all tasks separately. But if they are similar, this simplifies the definition of scheduling problems. Finally, we can similarly define lists of resources:

from pyschedule import Scenario, solvers, plotters, alt
S = Scenario('many_resources',horizon=10)

# create 5 resources of the same type
R = S.Resources('R',num=5)

print(R)

[R0, R1, R2, R3, R4]

Resource Assignment

It is possible to assign multiple resources to a task, either we define that one of these resources is required or all:

from pyschedule import Scenario, solvers, plotters, alt
S = Scenario('resources_assignment',horizon=10)

R = S.Resources('R',num=2)
T = S.Tasks('T',num=2,delay_cost=1)

# T0 requires either resource R0 or R1
T[0] += R[0] | R[1]

# T1 requires resources R0 and R1
T[1] += R[0], R[1]

# print the resources requirement
print(T[0].resources_req)
print(T[1].resources_req)

[R0|R1]
[R0, R1]

Note that if we have a list of resources, like above, we can also use the alt-operator:

# T0 requires any of the resources
from pyschedule import alt
T[0] += alt(R)

# T1 requires all of the resources
T1 += R

Now we can solve this scenario:

solvers.mip.solve(S,msg=1)
print(S.solution())

INFO: execution time for solving mip (sec) = 0.05312514305114746
INFO: objective = 1.0
[(T0, R0, 0, 1), (T1, R0, 1, 2), (T1, R1, 1, 2)]

Therefore, T0 is scheduled on resource R0 in period 0 and T1 on resources R0 and R1 in period 1.

Resource Dependencies

It is often necessary to ensure that two tasks select the same resources:

from pyschedule import Scenario, solvers, plotters, alt
S = Scenario('resources_dep',horizon=10)

R = S.Resources('R',num=2)
T = S.Tasks('T',num=2,delay_cost=1)

# assign all resources to both resources
T += alt(R)

# if T[1] is assigned to any resource in R, then also T[0]
T[0] += T[1] * R
	
# plot the resource dependencies of task T0
print(T[0].tasks_req)

[T1*R0, T1*R1]

Now we can solve this scenario

solvers.mip.solve(S,msg=1)
print(S.solution())

INFO: execution time for solving mip (sec) = 0.02900981903076172
INFO: objective = 1.0
[(T1, R0, 0, 1), (T0, R0, 1, 2)]

It would be better to distribute the two tasks to the two resources. However, due