Sequence-dependent setup times¶

If you’re using this notebook in Google Colab, be sure to install PyJobShop first by executing pip install pyjobshop in a cell.

This notebook demonstrates how to model sequence-dependent setup times in PyJobShop.

[1]:

from pyjobshop import Model
from pyjobshop.plot import plot_machine_gantt

Machines may require different configuration settings for processing different types of tasks. This results in sequence-dependent setup times, which is the time that is required to reconfigure machines between processing two tasks. Let’s showcase a small example here.

[2]:

model = Model()
tasks = [model.add_task() for _ in range(6)]
machines = [model.add_machine() for _ in range(2)]

for task in tasks:
    # The first machine is faster than the second machine.
    model.add_mode(task, machines[0], duration=1)
    model.add_mode(task, machines[1], duration=3)

for task1 in tasks:
    for task2 in tasks:
        # But the first machine has much longer setup times.
        model.add_setup_time(machines[0], task1, task2, duration=5)
        model.add_setup_time(machines[1], task1, task2, duration=1)

[3]:

result = model.solve(display=False)
print(result)

Solution results
================
  objective: 13.00
lower bound: 13.00
     status: Optimal
    runtime: 0.10 seconds

[4]:

data = model.data()
plot_machine_gantt(result.best, data, plot_labels=True)

Some notes:

• Instances with sequence-dependent setup times are generally hard to solve, and it’s even harder to solve to optimality. Consider using a time limit when solving such instances.

• Unlike CP Optimizer, OR-Tools does not have specialized constraints to deal with sequence-dependent setup times. This makes the implementation of OR-Tools substantially slower.