visu/setup_times.py example

  1# --------------------------------------------------------------------------
  2# Source file provided under Apache License, Version 2.0, January 2004,
  3# http://www.apache.org/licenses/
  4# (c) Copyright IBM Corp. 2015, 2022
  5# --------------------------------------------------------------------------
  6
  7"""
  8This example solves a scheduling problem on two alternative heterogeneous machines.
  9A set of tasks {a_1,...,a_n} has to be executed on either one of the two machines.
 10Different types of tasks are distinguished, the type of task a_i is denoted tp_i.
 11
 12A machine m needs a sequence dependent setup time setup(tp,tp') to switch from a
 13task of type tp to the next task of type tp'.
 14Furthermore some transitions tp->tp' are forbidden.
 15
 16The two machines are different: they process tasks with different speed and have
 17different setup times and forbidden transitions.
 18
 19The objective is to minimize the makespan.
 20
 21The model uses transition distances and no_overlap constraints to model machines
 22setup times.
 23The no_overlap constraint is specified to enforce transition distance between
 24immediate successors on the sequence.
 25Forbidden transitions are modeled with a very large transition distance.
 26
 27Please refer to documentation for appropriate setup of solving configuration.
 28"""
 29
 30from docplex.cp.model import *
 31
 32
 33#-----------------------------------------------------------------------------
 34# Initialize the problem data
 35#-----------------------------------------------------------------------------
 36
 37# Number of types
 38NB_TYPES = 5
 39
 40# Setup times of machine M1. -1 means forbidden transition
 41SETUP_M1 = [[0, 26,   8,  3, -1],
 42            [22,  0, -1,  4, 22],
 43            [28,  0,  0, 23,  9],
 44            [29, -1, -1,  0,  8],
 45            [26, 17, 11,  7,  0]]
 46
 47# Setup times of machine M2. -1 means forbidden transition
 48SETUP_M2 = [[0,   5, 28, -1,  2],
 49            [-1,  0, -1,  7, 10],
 50            [19, 22,  0, 28, 17],
 51            [7,  26, 13,  0, -1],
 52            [13, 17, 26, 20,  0]]
 53
 54# Task types
 55TASK_TYPE = [3, 3, 1, 1, 1, 1, 2, 0, 0, 2,
 56             4, 4, 3, 3, 2, 3, 1, 4, 4, 2,
 57             2, 1, 4, 2, 2, 0, 3, 3, 2, 1,
 58             2, 1, 4, 3, 3, 0, 2, 0, 0, 3,
 59             2, 0, 3, 2, 2, 4, 1, 2, 4, 3]
 60
 61# Number of tasks
 62NB_TASKS = len(TASK_TYPE)
 63
 64# Task duration if executed on machine M1
 65TASK_DUR_M1 = [ 4, 17,  4,  7, 17, 14,  2, 14, 2,  8,
 66               11, 14,  4, 18,  3,  2,  9,  2, 9, 17,
 67               18, 19,  5,  8, 19, 12, 17, 11, 6,  3,
 68               13,  6, 19,  7,  1,  3, 13,  5, 3,  6,
 69               11, 16, 12, 14, 12, 17,  8,  8, 6,  6]
 70
 71# Task duration if executed on machine M2
 72TASK_DUR_M2 = [12,  3, 12, 15,  4,  9, 14,  2,  5,  9,
 73               10, 14,  7,  1, 11,  3, 15, 19,  8,  2,
 74               18, 17, 19, 18, 15, 14,  6,  6,  1,  2,
 75                3, 19, 18,  2,  7, 16,  1, 18, 10, 14,
 76                2,  3, 14,  1,  1,  6, 19,  5, 17,  4]
 77
 78
 79#-----------------------------------------------------------------------------
 80# Prepare the data for modeling
 81#-----------------------------------------------------------------------------
 82
 83# Put max value for forbidden transitions in setup times
 84for i in range(NB_TYPES):
 85    for j in range(NB_TYPES):
 86        if SETUP_M1[i][j] < 0:
 87            SETUP_M1[i][j] = INTERVAL_MAX;
 88        if SETUP_M2[i][j] < 0:
 89            SETUP_M2[i][j] = INTERVAL_MAX;
 90
 91
 92#-----------------------------------------------------------------------------
 93# Build the model
 94#-----------------------------------------------------------------------------
 95
 96# Create model
 97mdl = CpoModel()
 98
 99# Build tasks for machine M1 and M2
100tasks_m1 = [interval_var(name='A{}_M1_TP{}'.format(i, TASK_TYPE[i]), optional=True, size=TASK_DUR_M1[i]) for i in range(NB_TASKS)]
101tasks_m2 = [interval_var(name='A{}_M2_TP{}'.format(i, TASK_TYPE[i]), optional=True, size=TASK_DUR_M1[i]) for i in range(NB_TASKS)]
102
103# Build actual tasks as an alternative between machines
104tasks = [interval_var(name='A{}_TP{}'.format(i, TASK_TYPE[i])) for i in range(NB_TASKS)]
105mdl.add(alternative(tasks[i], [tasks_m1[i], tasks_m2[i]]) for i in range(NB_TASKS))
106
107# Build a map to retrieve task id from variable name (for display purpose)
108task_id = dict()
109for i in range(NB_TASKS):
110    task_id[tasks_m1[i].get_name()] = i
111    task_id[tasks_m2[i].get_name()] = i
112
113# Constrain tasks to no overlap on each machine
114s1 = sequence_var(tasks_m1, types=TASK_TYPE, name='M1')
115s2 = sequence_var(tasks_m2, types=TASK_TYPE, name='M2')
116mdl.add(no_overlap(s1, SETUP_M1, 1))
117mdl.add(no_overlap(s2, SETUP_M2, 1))
118
119# Minimize the makespan
120mdl.add(minimize(max([end_of(tasks[i]) for i in range(NB_TASKS)])))
121
122
123#-----------------------------------------------------------------------------
124# Solve the model and display the result
125#-----------------------------------------------------------------------------
126
127def compact(name):
128    # Example: A31_M1_TP1 -> 31
129    task, foo = name.split('_', 1)
130    return task[1:]
131
132import docplex.cp.utils_visu as visu
133
134def showsequence(s, setup):
135    seq = res.get_var_solution(s)
136    visu.sequence(name=s.get_name())
137    vs = seq.get_value()
138    for v in vs:
139        nm = v.get_name()
140        visu.interval(v, TASK_TYPE[task_id[nm]], compact(nm))
141    for i in range(len(vs) - 1):
142        end = vs[i].get_end()
143        tp1 = TASK_TYPE[task_id[vs[i].get_name()]]
144        tp2 = TASK_TYPE[task_id[vs[i + 1].get_name()]]
145        visu.transition(end, end + setup[tp1][tp2])
146
147# Solve model
148print('Solving model...')
149res = mdl.solve(FailLimit=100000, TimeLimit=10)
150print('Solution: ')
151res.print_solution()
152
153if res and visu.is_visu_enabled():
154    visu.timeline('Solution for SchedSetup')
155    showsequence(s1, SETUP_M1)
156    showsequence(s2, SETUP_M2)
157    visu.show()