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 is a problem of building five houses. The masonry, roofing,
9painting, etc. must be scheduled. Some tasks must necessarily take
10place before others and these requirements are expressed through
11precedence constraints.
12
13There are two workers and each task requires a specific worker.
14The worker has a calendar of days off that must be taken into account.
15The objective is to minimize the overall completion date.
16
17Please refer to documentation for appropriate setup of solving configuration.
18"""
19
20from docplex.cp.model import *
21
22#-----------------------------------------------------------------------------
23# Initialize the problem data
24#-----------------------------------------------------------------------------
25
26# List of available workers together with their holidays as list of tuples (start_day, end_day)
27WORKERS = {
28 'Joe' : [ (5, 12), (124, 131), (215, 236), (369, 376), (495, 502), (579, 600) ],
29 'Jim' : [ (26, 40), (201, 225), (306, 313), (397, 411), (565, 579) ]
30}
31
32# List of tasks to be executed for each house
33TASKS = {
34 'masonry' : (35 , 'Joe', 1),
35 'carpentry' : (15 , 'Joe', 2),
36 'plumbing' : (40 , 'Jim', 3),
37 'ceiling' : (15 , 'Jim', 4),
38 'roofing' : ( 5 , 'Joe', 5),
39 'painting' : (10 , 'Jim', 6),
40 'windows' : ( 5 , 'Jim', 7),
41 'facade' : (10 , 'Joe', 8),
42 'garden' : ( 5 , 'Joe', 9),
43 'moving' : ( 5 , 'Jim', 10)
44}
45
46# Tasks precedence constraints (each tuple (X, Y) means X ends before start of Y)
47PRECEDENCES = [
48 ('masonry', 'carpentry'),
49 ('masonry', 'plumbing'),
50 ('masonry', 'ceiling'),
51 ('carpentry', 'roofing'),
52 ('ceiling', 'painting'),
53 ('roofing', 'windows'),
54 ('roofing', 'facade'),
55 ('plumbing', 'facade'),
56 ('roofing', 'garden'),
57 ('plumbing', 'garden'),
58 ('windows', 'moving'),
59 ('facade', 'moving'),
60 ('garden', 'moving'),
61 ('painting', 'moving'),
62]
63
64# Total number of houses to build
65NUMBER_OF_HOUSES = 5
66
67# Max number of calendar years
68MAX_YEARS = 2
69
70#-----------------------------------------------------------------------------
71# Prepare the data for modeling
72#-----------------------------------------------------------------------------
73
74# Initialize availability calendar for workers
75
76calendars = { w : CpoStepFunction() for w in WORKERS }
77for w in WORKERS:
78 calendars[w].set_value(0, MAX_YEARS * 365, 100)
79 # Remove week ends
80 for i in range(MAX_YEARS * 52):
81 calendars[w].set_value(5 + (7 * i), 7 + (7 * i), 0)
82 # Remove holidays
83 for s,e in WORKERS[w]:
84 calendars[w].set_value(s, e, 0)
85
86#-----------------------------------------------------------------------------
87# Build the model
88#-----------------------------------------------------------------------------
89
90# Create model
91mdl = CpoModel()
92
93# Initialize model variable sets
94worker_tasks = { w : [] for w in WORKERS} # Tasks assigned to workers (key is the worker)
95house_finish_times = [] # Array of house finishing times
96
97# Utility function
98def make_house(loc):
99 ''' Create model elements corresponding to the building of one house
100 loc: Identification (index) of the house to build
101 '''
102
103 # Create interval variable for each task for this house
104 tasks = { t: interval_var(size=TASKS[t][0], intensity=calendars[TASKS[t][1]], name='H{}-{}'.format(loc,t)) for t in TASKS }
105 for t in TASKS:
106 mdl.forbid_start(tasks[t], calendars[TASKS[t][1]])
107 mdl.forbid_end (tasks[t], calendars[TASKS[t][1]])
108
109 # Add precedence constraints
110 mdl.add(end_before_start(tasks[p], tasks[s]) for p,s in PRECEDENCES)
111
112 # Allocate tasks to workers
113 for t in TASKS:
114 worker_tasks[TASKS[t][1]].append(tasks[t])
115
116 # Update cost
117 house_finish_times.append(end_of(tasks['moving']))
118
119
120# Make houses
121for i in range(NUMBER_OF_HOUSES):
122 make_house(i)
123
124# Avoid each worker tasks overlapping
125mdl.add(no_overlap(worker_tasks[w]) for w in WORKERS)
126
127# Add minimization objective
128mdl.add(minimize(max(house_finish_times)))
129
130
131#-----------------------------------------------------------------------------
132# Solve the model and display the result
133#-----------------------------------------------------------------------------
134
135def compact(name):
136 # Example: H3-garden -> G3
137 # ^ ^
138 loc, task = name[1:].split('-', 1)
139 # Returns color index and compacted name
140 return int(TASKS[task][2]), (task[0].upper() + loc)
141
142# Solve model
143print('Solving model...')
144res = mdl.solve(TimeLimit=10)
145print('Solution:')
146res.print_solution()
147
148# Display result
149import docplex.cp.utils_visu as visu
150if res and visu.is_visu_enabled():
151 visu.timeline('Solution house building with calendars')
152 visu.panel()
153 for w in WORKERS:
154 visu.pause(calendars[w])
155 visu.sequence(name=w)
156 for t in worker_tasks[w]:
157 visu.interval(res.get_var_solution(t), *compact(t.get_name()))
158 visu.show()