-
Notifications
You must be signed in to change notification settings - Fork 0
/
instance2graph_translator.py
194 lines (188 loc) · 9.49 KB
/
instance2graph_translator.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
from model.instance import Instance
from model.graph import GraphInstance, ItemFeatures, OperationFeatures, ResourceFeatures, MaterialFeatures, NeedForMaterialFeatures, NeedForResourceFeatures, YES, NO, NOT_YET
from torch import Tensor
# ====================================================================
# =*= TRANSLATE INSTANCE 2 GRAPH =*=
# Complete code to translate a model.Instance to a model.GraphInstance
# ====================================================================
__author__ = "Anas Neumann - [email protected]"
__version__ = "1.0.0"
__license__ = "Apache 2.0 License"
def build_item(i: Instance, graph: GraphInstance, p: int, e: int, head: bool, estimated_start: int, must_be_outsourced: bool=False):
design_load, physical_load = i.item_processing_time(p, e, total_load=True)
design_mean_time, physical_mean_time = i.item_processing_time(p, e, total_load=False)
childrens = i.get_children(p, e, direct=False)
children_time = 0
childrens_physical_operations = 0
childrens_design_operations = 0
for children in childrens:
cdt, cpt = i.item_processing_time(p, e=children, total_load=True)
children_time += (cdt+cpt)
for child_op in i.loop_item_operations(p, e=children):
if not i.is_design[p][child_op]:
childrens_physical_operations += 1
else:
childrens_design_operations +=1
parents_physical_time = 0
ancestors = i.get_ancestors(p, e)
for ancestor in ancestors:
_, apt = i.item_processing_time(p, e=ancestor, total_load=True)
parents_physical_time += apt
item_id = graph.add_item(p, e, ItemFeatures(
head = head,
external = i.external[p][e],
outsourced = NOT_YET if i.external[p][e] else NO,
outsourcing_cost = i.external_cost[p][e],
outsourcing_time = i.outsourcing_time[p][e],
remaining_physical_time = physical_load,
remaining_design_time = design_load,
parents = len(ancestors),
children = len(childrens),
parents_physical_time = parents_physical_time,
children_time = children_time,
start_time = estimated_start,
end_time = -1,
is_possible = YES if head else NOT_YET))
if i.external[p][e]:
graph.oustourcable_items += 1
start, end = i.get_operations_idx(p,e)
for o in range(start, end):
if o > start:
op_start = op_start+operation_mean_time
else:
op_start = estimated_start
succs = end-(o+1)
operation_load = i.operation_time(p,o, total_load=True)
operation_mean_time = i.operation_time(p,o, total_load=False)
required_res = 0
required_mat = 0
for rt in i.required_rt(p, o):
resources_of_rt = i.resources_by_type(rt)
if resources_of_rt:
if i.finite_capacity[resources_of_rt[0]]:
required_res += 1
else:
required_mat += 1
else:
must_be_outsourced = True
op_id = graph.add_operation(p, o, OperationFeatures(
design = i.is_design[p][o],
sync = i.simultaneous[p][o],
timescale_hours = i.in_hours[p][o],
timescale_days = i.in_days[p][o],
direct_successors = succs,
total_successors = childrens_physical_operations + succs + (childrens_design_operations if i.is_design[p][o] else 0),
remaining_time = operation_load,
remaining_resources = required_res,
remaining_materials = required_mat,
available_time = op_start,
end_time = op_start+operation_mean_time,
is_possible = YES if (head and (o == start)) else NOT_YET))
graph.add_operation_assembly(item_id, op_id)
for rt in i.required_rt(p,o):
graph.nb_operations += 1
for r in i.resources_by_type(rt):
if i.finite_capacity[r]:
graph.add_need_for_resources(op_id, graph.resources_i2g[r], NeedForResourceFeatures(
status = NOT_YET,
basic_processing_time = i.execution_time[r][p][o],
current_processing_time = i.execution_time[r][p][o],
start_time = op_start,
end_time = op_start+i.execution_time[r][p][o]))
else:
graph.add_need_for_materials(op_id, graph.materials_i2g[r], NeedForMaterialFeatures(
status = NOT_YET,
execution_time = op_start,
quantity_needed = i.quantity_needed[r][p][o]))
estimated_start_child = estimated_start if i.external[p][e] else design_mean_time
estimated_childrend_end = 0
estimated_children_cost = 0
for children in i.get_children(p, e, direct=True):
graph, child_id, estimated_end_child, child_cost = build_item(i, graph, p, e=children, head=False, estimated_start=estimated_start_child, must_be_outsourced=must_be_outsourced)
graph.add_item_assembly(item_id, child_id)
estimated_childrend_end = max(estimated_childrend_end, estimated_end_child)
estimated_children_cost += child_cost
external_end = estimated_start + i.outsourcing_time[p][e]
internal_end = estimated_childrend_end + physical_mean_time
estimated_end = external_end if must_be_outsourced else min(external_end, internal_end) if i.external[p][e] else internal_end
graph.update_item(item_id, [('end_time', estimated_end)])
mandatory_cost = estimated_children_cost + (i.external_cost[p][e] if must_be_outsourced else 0)
return graph, item_id, estimated_end, mandatory_cost
def build_precedence(i: Instance, graph: GraphInstance):
for p in i.loop_projects():
for e in i.loop_items(p):
start, end = i.get_operations_idx(p, e)
parent_last_design = []
parent_first_physical = []
parent = i.get_direct_parent(p, e)
if parent > -1:
parent_last_design = i.last_design_operations(p, parent)
parent_first_physical = i.first_physical_operations(p, parent)
for o in range(start, end):
o_id = graph.operations_i2g[p][o]
preds = i.preds_or_succs(p, e, start, end, o, design_only=False, physical_only=False, preds=True)
for pred in preds:
pred_id = graph.operations_i2g[p][pred]
graph.add_precedence(pred_id, o_id)
for pld in parent_last_design:
pred_id = graph.operations_i2g[p][pld]
graph.add_precedence(pred_id, o_id)
for pfp in parent_first_physical:
succ_id = graph.operations_i2g[p][pfp]
graph.add_precedence(o_id, succ_id)
return graph
def discover_levels(i: Instance, p: int, e: int):
children: list[int] = i.get_children(p, e, direct=True)
max_sub_levels = 0
if children:
for child in children:
max_sub_levels = max(max_sub_levels, discover_levels(i, p, child))
return 1 + max_sub_levels
def discover_mean_levels(i: Instance):
sum_levels = 0
nb_projects = len(i.E_size)
for p in i.loop_projects():
sum_levels += discover_levels(i, p, i.project_head(p))
return sum_levels / nb_projects
def translate(i: Instance, device: str):
graph = GraphInstance(device=device)
for rt in range(i.nb_resource_types):
resources = i.resources_by_type(rt)
operations = i.operations_by_resource_type(rt)
res_idx = []
for r in resources:
if i.finite_capacity[r]:
res_id = graph.add_resource(r, i.nb_settings, ResourceFeatures(
utilization_ratio = 0,
available_time = 0,
executed_operations = 0,
remaining_operations = len(operations),
similar_resources = len(resources)))
for other_id in res_idx:
graph.add_same_types(other_id, res_id)
res_idx.append(res_id)
else:
remaining_quantity_needed = 0
for p, o in operations:
remaining_quantity_needed += i.quantity_needed[r][p][o]
graph.add_material(r, MaterialFeatures(
remaining_init_quantity = i.init_quantity[r],
arrival_time = i.purchase_time[r],
remaining_demand = remaining_quantity_needed))
graph.resources_i2g = graph.build_i2g_1D(graph.resources_g2i, i.nb_resources)
graph.materials_i2g = graph.build_i2g_1D(graph.materials_g2i, i.nb_resources)
Cmax_lower_bound = 0
cost_lower_bound = 0
for p in i.loop_projects():
graph, _, project_end, project_cost = build_item(i, graph, p, e=i.project_head(p), head=True, estimated_start=0, must_be_outsourced=False)
Cmax_lower_bound = max(Cmax_lower_bound, project_end)
cost_lower_bound += project_cost
graph.operations_i2g = graph.build_i2g_2D(graph.operations_g2i)
graph.items_i2g = graph.build_i2g_2D(graph.items_g2i)
graph.add_dummy_item(device=device)
graph = build_precedence(i, graph)
previous_operations, next_operations = i.build_next_and_previous_operations()
related_items: Tensor = graph.flatten_related_items(device)
parent_items: Tensor = graph.flatten_parents(device)
graph.mean_levels = discover_mean_levels(i)
return graph, Cmax_lower_bound, cost_lower_bound, previous_operations, next_operations, related_items, parent_items