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()