Scheduling in Python with Constraint Programming

4 min readNov 6, 2019

Decision Optimization in Watson Studio includes both Mathematical and Constraint Programming. Constraint Programming (CP) is particularly efficient and useful to solve Scheduling problems. You can formulate and solve Scheduling problems with CP with any of the supported experiences, python notebooks, python and OPL in the model builder, and using the modeling assistant.

In this post, you will see how you can easily formulate and solve a simple scheduling problem with docplex.cp python package in a Jupyter notebook.

House Construction

The problem you will solve is about scheduling the construction of several houses by some workers with different skills. A set of tasks is required to build a house (masonry, etc), with a given duration, and some required precedences between the tasks. Different workers are available who have different skill levels for different tasks. For a given number of houses to build, and a given deadline when all houses must be completed, the objective is to maximize the total skill level of workers assigned to tasks.

This notebooks is inspired from the standard docplex example that you can find here.

Data includes:

workers available to build the houses,
tasks required to build one house, with their duration,
precedences between these tasks,
skills measure the level of skill for each combination of task and worker,
parameters such as the number of houses to build or the deadline to build these houses.

You can find the data here.

Formulate and solve the model

The model is created using the docplex.cp package as Constraint Programming will be used.

from docplex.cp.model import CpoModel, INTERVAL_MIN# Create model
mdl = CpoModel()

Create the decision variables and constraints

Scheduling problems in docplex.cp are modeled using interval variables: an interval decision variable represents an unknown of a scheduling problem, in particular an interval of time during which something happens (an activity is carried out) whose position in time is unknown.

For each house, the make_house function is called and will:

create interval variables, using mdl.interval_var(), for each task to build the house. Interval variables are created with a fixed duration, and an end date which should be less than the deadline,
add precedence constraints, using mdl.end_before_start(), between all the tasks to build the house,
for each task, create an interval variable for each worker corresponding to this worker doing this task, and add an alternative constraint, using mdl.alternative(), to ensure at least one of these worker tasks will be scheduled,

Then, for each worker:

add a non overlap constraint, using mdl.no_overlap(), so that a worker is not assigned two overlapping activities.

# Initialize model variable sets
total_skill = 0    # Expression computing total of skills
worker_tasks = {}  # Tasks (interval variables) assigned to a each worker
desc = dict()      # Map retrieving task from interval variable# Utility function
def make_house(loc, deadline):
    ''' Create model elements corresponding to the building of a house
    loc      Identification of house location
    deadline Deadline for finishing the house
    '''# Create interval variable for each task for this house
    tasks = {t:mdl.interval_var(size=task.duration,
                          end=(INTERVAL_MIN, deadline),
                          name='H' + str(loc) + '-' + t) 
             for t, task in df_tasks.iterrows()}# Add precedence constraints
    for i, precedence in df_precedences.iterrows():
        mdl.add(mdl.end_before_start(tasks[precedence.before], tasks[precedence.after]))# Allocate tasks to workers
    global total_skill
    for t, task in df_tasks.iterrows():
        allocs = []
        for w, worker in df_workers.iterrows():
            if df_skills.skill[t, w] > 0:
                wt = mdl.interval_var(optional=True, name="H{}-{}({})".format(loc, t, w))
                if (w not in worker_tasks):
                    worker_tasks[w] = []
                worker_tasks[w].append(wt)
                allocs.append(wt)
                total_skill += (df_skills.skill[t, w] * mdl.presence_of(wt))
                desc[wt] = t
        mdl.add(mdl.alternative(tasks[t], allocs))# Make houses
for h in range(NB_HOUSES):
    make_house(h, DEADLINE)# Avoid overlapping between tasks of each worker
for w, worker in df_workers.iterrows():
    mdl.add(mdl.no_overlap(worker_tasks[w]))

KPIs and objectives

In this case, the sum of the skills of the assigned workers to each task will be maximized.

# KPIs
makespan = mdl.max([mdl.end_of(task) for task in worker_tasks[w] for w, workers in df_workers.iterrows()])mdl.add_kpi(makespan, 'makespan')mdl.add_kpi(total_skill, 'total_skill')# Maximize total of skills
mdl.add(mdl.maximize(total_skill))mdl.print_information()

Solve and get solution

print("Solving model....")
msol = mdl.solve(TimeLimit=10)print("Solution: ")
msol.print_solution()

In the complete notebook, you can also see how to create a Gantt chart using dedicated functions from the docplex.cp.utils_visu package.

Using the Model Builder and run What-if analysis

With Decision Optimization for Watson Studio, you can also import this notebook in a model builder, so that you can use visualizations (e.g. to represent the schedule for each house) and create multiple scenarios (e.g. to do some analysis).

You can also use a standard python notebook to create multiple copies of the Baseline scenario with different values of the deadline to see how this impact the optimal total_skill and the effective makespan.

This is illustrated in this other notebook.

The model builder visualizations can be used to analyze the outcome over all scenarios as follow:

This analysis shows that as you increase the input deadline parameter, the total_skill objective increases up to a point (385) where it cannot increase more. At the same time, the effective makespan increases although, sometimes, an optimal solution is found (with respect to the total_skill objective) with a sub optimal solution in terms of makespan.

Based on this analysis, a business compromise can be found which correspond to a good trade-off between deadline and quality.

For more details on how to create Constraint Programming models with docplex.cp package, refer to the Reference Manual.

You can start playing with such notebooks now, look at this post to start.

email: alain.chabrier@ibm.com

linkedin: https://www.linkedin.com/in/alain-chabrier-5430656/

twitter: https://twitter.com/AlainChabrier