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 three workers, and each worker has a given non-negative
14skill level for each task. Each task requires one worker that will
15have to be selected among the ones who have a non null skill level for
16that task. A worker can be assigned to only one task at a time. Each
17house has a deadline. The objective is to maximize the skill levels of
18the workers assigned to the tasks while respecting the deadlines.
19
20Please refer to documentation for appropriate setup of solving configuration.
21"""
22
23from docplex.cp.model import *
24
25#-----------------------------------------------------------------------------
26# Initialize the problem data
27#-----------------------------------------------------------------------------
28
29NB_HOUSES = 5
30DEADLINE = 318
31WORKERS = ['Joe', 'Jack', 'Jim']
32NB_WORKERS = len(WORKERS)
33
34# List of tasks to be executed for each house
35TASKS = {
36 'masonry' : (35, [9, 5, 0], 1),
37 'carpentry' : (15, [7, 0, 5], 2),
38 'plumbing' : (40, [0, 7, 0], 3),
39 'ceiling' : (15, [5, 8, 0], 4),
40 'roofing' : ( 5, [6, 7, 0], 5),
41 'painting' : (10, [0, 9, 6], 6),
42 'windows' : ( 5, [8, 0, 5], 7),
43 'facade' : (10, [5, 5, 0], 8),
44 'garden' : ( 5, [5, 5, 9], 9),
45 'moving' : ( 5, [6, 0, 8], 10)
46}
47
48# Tasks precedence constraints (each tuple (X, Y) means X ends before start of Y)
49PRECEDENCES = [
50 ('masonry', 'carpentry'),
51 ('masonry', 'plumbing'),
52 ('masonry', 'ceiling'),
53 ('carpentry', 'roofing'),
54 ('ceiling', 'painting'),
55 ('roofing', 'windows'),
56 ('roofing', 'facade'),
57 ('plumbing', 'facade'),
58 ('roofing', 'garden'),
59 ('plumbing', 'garden'),
60 ('windows', 'moving'),
61 ('facade', 'moving'),
62 ('garden', 'moving'),
63 ('painting', 'moving'),
64]
65
66#-----------------------------------------------------------------------------
67# Build the model
68#-----------------------------------------------------------------------------
69
70# Create model
71mdl = CpoModel()
72
73# Initialize model variable sets
74total_skill = 0 # Expression computing total of skills
75worker_tasks = [[] for w in range(NB_WORKERS)] # Tasks (interval variables) assigned to a each worker
76
77# Utility function
78def make_house(loc, deadline):
79 ''' Create model elements corresponding to the building of a house
80 loc Identification of house location
81 deadline Deadline for finishing the house
82 '''
83
84 # Create interval variable for each task for this house
85 tasks = {t: interval_var(size=TASKS[t][0], end=(0, deadline), name='H{}-{}'.format(loc,t)) for t in TASKS}
86
87 # Add precedence constraints
88 mdl.add(end_before_start(tasks[p], tasks[s]) for p,s in PRECEDENCES)
89
90 # Allocate tasks to workers
91 global total_skill
92 allocs = { (t,w) : interval_var(optional=True, name='H{}-{}-{}'.format(loc, t, w)) for t in TASKS for w in range(NB_WORKERS) if TASKS[t][1][w] > 0 }
93 total_skill += sum((TASKS[t][1][w] * presence_of(allocs[t,w])) for t,w in allocs)
94 for t in TASKS:
95 mdl.add(alternative(tasks[t], [allocs[t2,w] for t2,w in allocs if t==t2]))
96 for t,w in allocs:
97 worker_tasks[w].append(allocs[t,w])
98
99# Make houses
100for h in range(NB_HOUSES):
101 make_house(h, DEADLINE)
102
103# Avoid overlapping between tasks of each worker
104for w in range(NB_WORKERS):
105 mdl.add(no_overlap(worker_tasks[w]))
106
107# Maximize total of skills
108mdl.add(maximize(total_skill))
109
110
111#-----------------------------------------------------------------------------
112# Solve the model and display the result
113#-----------------------------------------------------------------------------
114
115def compact(name):
116 # Example: H3-garden -> G3
117 # ^ ^
118 loc, task, worker = name[1:].split('-', 2)
119 # Returns color index and compacted name
120 return int(TASKS[task][2]), task[0].upper() + loc
121
122# Solve model
123print('Solving model...')
124res = mdl.solve(FailLimit=10000, TimeLimit=10)
125
126print('Solution:')
127res.print_solution()
128
129# Draw solution
130import docplex.cp.utils_visu as visu
131if res and visu.is_visu_enabled():
132 visu.timeline('Solution house building', 0, DEADLINE)
133 for w in range(NB_WORKERS):
134 visu.sequence(name=WORKERS[w])
135 for t in worker_tasks[w]:
136 wt = res.get_var_solution(t)
137 if wt.is_present():
138 visu.interval(wt, *compact(wt.get_name()))
139 visu.show()