# Copyright (c) 2022 AIRBUS and its affiliates.
# This source code is licensed under the MIT license found in the
# LICENSE file in the root directory of this source tree.
import logging
import numba.typed
import numba.types
import numpy as np
import numpy.typing as npt
from numba import njit # type: ignore
logger = logging.getLogger(__name__)
int_array = numba.types.Array(numba.types.int_, 1, "C")
[docs]
@njit
def sgs_fast(
permutation_task: npt.NDArray[np.int_], # permutation_task=array(task)->task index
modes_array: npt.NDArray[np.int_], # modes=array(task)->0, 1...
consumption_array: npt.NDArray[
np.int_
], # consumption_array=array3D(task, mode, res),
duration_array: npt.NDArray[np.int_],
predecessors: npt.NDArray[np.int_], # array(task, task) -> bool
successors: npt.NDArray[np.int_], # array(task, task)->bool
horizon: int,
ressource_available: npt.NDArray[np.int_],
ressource_renewable: npt.NDArray[np.bool_],
minimum_starting_time_array: npt.NDArray[np.int_],
) -> tuple[dict[int, tuple[int, int]], bool]:
activity_end_times = {}
unfeasible_non_renewable_resources = False
new_horizon = horizon
resource_avail_in_time = {}
for index in range(ressource_available.shape[0]):
resource_avail_in_time[index] = np.copy(
ressource_available[index][: new_horizon + 1]
)
minimum_starting_time = {}
for act in range(permutation_task.shape[0]):
minimum_starting_time[act] = minimum_starting_time_array[act]
done = 0
nb_task = permutation_task.shape[0]
pred_links = np.sum(predecessors[permutation_task, :], axis=1)
done_np = np.zeros((permutation_task.shape[0]), dtype=np.int_)
while done < nb_task and not unfeasible_non_renewable_resources:
act_id = 0
index_id = 0
found = False
for i in range(nb_task):
if pred_links[i] == 0 and done_np[i] == 0:
act_id = permutation_task[i]
index_id = i
found = True
break
if not found:
break
current_min_time = minimum_starting_time[act_id]
valid = False
while not valid:
valid = True
end_time = current_min_time + duration_array[act_id, modes_array[act_id]]
for t in range(current_min_time, end_time):
for res in range(ressource_available.shape[0]):
if t < new_horizon:
if (
resource_avail_in_time[res][t]
< consumption_array[act_id, modes_array[act_id], res]
): # 11
valid = False
break
else:
unfeasible_non_renewable_resources = True
break
if not valid:
break
if not valid:
current_min_time += 1
if not unfeasible_non_renewable_resources:
end_t = current_min_time + duration_array[act_id, modes_array[act_id]]
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
current_min_time:end_t
] -= consumption_array[act_id, modes_array[act_id], res]
else:
resource_avail_in_time[res][current_min_time:] -= consumption_array[
act_id, modes_array[act_id], res
]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
activity_end_times[act_id] = end_t
done_np[index_id] = 1
done += 1
# for s in range(successors.shape[1]):
for j in range(nb_task):
if successors[act_id, permutation_task[j]] == 1:
minimum_starting_time[permutation_task[j]] = max(
int(minimum_starting_time[permutation_task[j]]),
int(activity_end_times[act_id]),
)
pred_links[j] -= 1
rcpsp_schedule: dict[int, tuple[int, int]] = {}
for act_id in activity_end_times:
rcpsp_schedule[act_id] = (
activity_end_times[act_id] - duration_array[act_id, modes_array[act_id]],
activity_end_times[act_id],
)
return rcpsp_schedule, unfeasible_non_renewable_resources
[docs]
@njit
def sgs_fast_preemptive(
permutation_task: npt.NDArray[np.int_], # permutation_task=array(task)->task index
modes_array: npt.NDArray[np.int_], # modes=array(task)->0, 1...
consumption_array: npt.NDArray[
np.int_
], # consumption_array=array3D(task, mode, res),
duration_array: npt.NDArray[np.int_],
preemptive_tag: npt.NDArray[np.bool_], # array(task)->bool
predecessors: npt.NDArray[np.int_], # array(task, task) -> bool
successors: npt.NDArray[np.int_], # array(task, task)->bool
horizon: int,
ressource_available: npt.NDArray[np.int_],
ressource_renewable: npt.NDArray[np.bool_],
minimum_starting_time_array: npt.NDArray[np.int_],
) -> tuple[dict[int, npt.NDArray[np.int_]], dict[int, npt.NDArray[np.int_]], bool]:
activity_end_times = {}
unfeasible_non_renewable_resources = False
new_horizon = horizon
resource_avail_in_time = {}
starts_dict = numba.typed.Dict.empty(
key_type=numba.types.intp,
value_type=int_array,
)
ends_dict = numba.typed.Dict.empty(
key_type=numba.types.intp,
value_type=int_array,
)
for index in range(ressource_available.shape[0]):
resource_avail_in_time[index] = np.copy(
ressource_available[index][: new_horizon + 1]
)
minimum_starting_time = {}
for act in range(permutation_task.shape[0]):
minimum_starting_time[act] = minimum_starting_time_array[act]
done = 0
nb_task = permutation_task.shape[0]
pred_links = np.sum(predecessors, axis=1)
done_np = np.zeros((permutation_task.shape[0]), dtype=np.int_)
done_duration = np.zeros((permutation_task.shape[0]), dtype=np.int_)
while done < nb_task and not unfeasible_non_renewable_resources:
act_id = 0
for i in range(nb_task):
if (
pred_links[permutation_task[i]] == 0
and done_np[permutation_task[i]] == 0
):
act_id = permutation_task[i]
break
current_min_time = int(minimum_starting_time[act_id])
valid = False
starts = []
ends = []
while not valid:
valid = True
reached_t = None
reached_end = True
if duration_array[act_id, modes_array[act_id]] == 0:
starts.append(current_min_time)
ends.append(current_min_time)
done_duration[act_id] = 0
else:
for t in range(
current_min_time,
current_min_time
+ duration_array[act_id, modes_array[act_id]]
- done_duration[act_id],
):
if t >= new_horizon:
reached_end = False
unfeasible_non_renewable_resources = True
break
for res in range(ressource_available.shape[0]):
if t < new_horizon:
if (
resource_avail_in_time[res][t]
< consumption_array[act_id, modes_array[act_id], res]
):
reached_end = False
break
else:
unfeasible_non_renewable_resources = True
break
if reached_end:
reached_t = t
else:
break
if (
reached_t is not None
and preemptive_tag[act_id]
and (reached_t + 1 - current_min_time >= 1 or reached_end)
):
starts.append(current_min_time)
ends.append(reached_t + 1)
done_duration[act_id] += ends[-1] - starts[-1]
if reached_end and not preemptive_tag[act_id] and reached_t is not None:
starts.append(current_min_time)
ends.append(reached_t + 1)
done_duration[act_id] += ends[-1] - starts[-1]
valid = (
done_duration[act_id] == duration_array[act_id, modes_array[act_id]]
)
if not valid:
current_min_time = (
reached_t + 2 if reached_t is not None else current_min_time + 1
)
if unfeasible_non_renewable_resources:
break
if unfeasible_non_renewable_resources:
break
if not unfeasible_non_renewable_resources:
end_t = ends[-1]
for i in range(len(starts)):
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
starts[i] : ends[i]
] -= consumption_array[act_id, modes_array[act_id], res]
else:
if i == 0:
resource_avail_in_time[res][
starts[i] :
] -= consumption_array[act_id, modes_array[act_id], res]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
activity_end_times[act_id] = end_t
starts_dict[act_id] = np.array(starts, dtype=np.int_)
ends_dict[act_id] = np.array(ends, dtype=np.int_)
done_np[act_id] = 1
done += 1
for s in range(successors.shape[1]):
if successors[act_id, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[act_id])
)
pred_links[s] -= 1
return starts_dict, ends_dict, unfeasible_non_renewable_resources
[docs]
@njit
def sgs_fast_preemptive_some_special_constraints(
permutation_task: npt.NDArray[np.int_], # permutation_task=array(task)->task index
modes_array: npt.NDArray[np.int_], # modes=array(task)->0, 1...
consumption_array: npt.NDArray[
np.int_
], # consumption_array=array3D(task, mode, res),
duration_array: npt.NDArray[np.int_],
preemptive_tag: npt.NDArray[np.bool_], # array(task)->bool
predecessors: npt.NDArray[np.int_], # array(task, task) -> bool
successors: npt.NDArray[np.int_], # array(task, task)->bool
start_at_end_plus_offset: npt.NDArray[
np.int_
], # array(N, 3) -> (task1, task2, offset)
start_after_nunit: npt.NDArray[np.int_], # array(N, 3) -> (task1, task2, offset)
minimum_starting_time_array: npt.NDArray[np.int_],
horizon: int,
ressource_available: npt.NDArray[np.int_],
ressource_renewable: npt.NDArray[np.bool_],
) -> tuple[dict[int, npt.NDArray[np.int_]], dict[int, npt.NDArray[np.int_]], bool]:
activity_end_times = {}
unfeasible_non_renewable_resources = False
new_horizon = horizon
resource_avail_in_time = {}
starts_dict = numba.typed.Dict.empty(
key_type=numba.types.intp,
value_type=int_array,
)
ends_dict = numba.typed.Dict.empty(
key_type=numba.types.intp,
value_type=int_array,
)
for index in range(ressource_available.shape[0]):
resource_avail_in_time[index] = np.copy(
ressource_available[index][: new_horizon + 1]
)
minimum_starting_time = {}
nb_task = permutation_task.shape[0]
for act in range(nb_task):
minimum_starting_time[act] = minimum_starting_time_array[act]
start_after_nunit_links = np.zeros(nb_task)
for task in range(nb_task):
start_after_nunit_links[task] = np.sum(start_after_nunit[:, 1] == task)
start_at_end_plus_offset_links = np.zeros(nb_task)
for task in range(nb_task):
start_at_end_plus_offset_links[task] = np.sum(
start_at_end_plus_offset[:, 1] == task
)
done = 0
nb_task = permutation_task.shape[0]
pred_links = np.sum(predecessors, axis=1)
done_np = np.zeros((permutation_task.shape[0]), dtype=np.int_)
done_duration = np.zeros((permutation_task.shape[0]), dtype=np.int_)
while done < nb_task and not unfeasible_non_renewable_resources:
act_id = 0
found = False
for i in range(nb_task):
if (
pred_links[permutation_task[i]] == 0
and done_np[permutation_task[i]] == 0
and start_after_nunit_links[permutation_task[i]] == 0
and start_at_end_plus_offset_links[permutation_task[i]] == 0
):
act_id = permutation_task[i]
found = True
break
if not found:
for i in range(nb_task):
if (
pred_links[permutation_task[i]] == 0
and done_np[permutation_task[i]] == 0
):
act_id = permutation_task[i]
break
current_min_time = int(minimum_starting_time[act_id])
valid = False
starts = []
ends = []
while not valid:
valid = True
reached_t = None
reached_end = True
if duration_array[act_id, modes_array[act_id]] == 0:
starts.append(current_min_time)
ends.append(current_min_time)
done_duration[act_id] = 0
else:
for t in range(
current_min_time,
current_min_time
+ duration_array[act_id, modes_array[act_id]]
- done_duration[act_id],
):
if t >= new_horizon:
reached_end = False
unfeasible_non_renewable_resources = True
break
for res in range(ressource_available.shape[0]):
if t < new_horizon:
if (
resource_avail_in_time[res][t]
< consumption_array[act_id, modes_array[act_id], res]
):
reached_end = False
break
else:
unfeasible_non_renewable_resources = True
break
if reached_end:
reached_t = t
else:
break
if (
reached_t is not None
and preemptive_tag[act_id]
and (
reached_t + 1 - current_min_time
>= duration_array[act_id, modes_array[act_id]] / 8
or reached_end
)
):
starts.append(current_min_time)
ends.append(reached_t + 1)
done_duration[act_id] += ends[-1] - starts[-1]
if reached_end and not preemptive_tag[act_id] and reached_t is not None:
starts.append(current_min_time)
ends.append(reached_t + 1)
done_duration[act_id] += ends[-1] - starts[-1]
valid = (
done_duration[act_id] == duration_array[act_id, modes_array[act_id]]
)
if not valid:
current_min_time = (
reached_t + 2 if reached_t is not None else current_min_time + 1
)
if unfeasible_non_renewable_resources:
break
if not unfeasible_non_renewable_resources:
end_t = ends[-1]
for i in range(len(starts)):
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
starts[i] : ends[i]
] -= consumption_array[act_id, modes_array[act_id], res]
else:
if i == 0:
resource_avail_in_time[res][
starts[i] :
] -= consumption_array[act_id, modes_array[act_id], res]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
activity_end_times[act_id] = end_t
starts_dict[act_id] = np.array(starts, dtype=np.int_)
ends_dict[act_id] = np.array(ends, dtype=np.int_)
done_np[act_id] = 1
done += 1
for s in range(successors.shape[1]):
if successors[act_id, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[act_id])
)
pred_links[s] -= 1
for t in range(start_after_nunit.shape[0]):
if start_after_nunit[t, 0] == act_id:
task = start_after_nunit[t, 1]
off = start_after_nunit[t, 2]
minimum_starting_time[task] = max(
int(minimum_starting_time[task]), starts_dict[act_id][0] + off
)
start_after_nunit_links[task] -= 1
for t in range(start_at_end_plus_offset.shape[0]):
if start_at_end_plus_offset[t, 0] == act_id:
task = start_at_end_plus_offset[t, 1]
off = start_at_end_plus_offset[t, 2]
minimum_starting_time[task] = max(
int(minimum_starting_time[task]),
activity_end_times[act_id] + off,
)
start_at_end_plus_offset_links[task] -= 1
return starts_dict, ends_dict, unfeasible_non_renewable_resources
[docs]
@njit
def sgs_fast_preemptive_minduration(
permutation_task: npt.NDArray[np.int_], # permutation_task=array(task)->task index
modes_array: npt.NDArray[np.int_], # modes=array(task)->0, 1...
consumption_array: npt.NDArray[
np.int_
], # consumption_array=array3D(task, mode, res),
duration_array: npt.NDArray[np.int_],
preemptive_tag: npt.NDArray[np.bool_], # array(task)->bool
predecessors: npt.NDArray[np.int_], # array(task, task) -> bool
successors: npt.NDArray[np.int_], # array(task, task)->bool
horizon: int,
ressource_available: npt.NDArray[np.int_],
ressource_renewable: npt.NDArray[np.bool_],
min_duration_preemptive_bool: npt.NDArray[np.bool_],
min_duration_preemptive: npt.NDArray[np.int_],
) -> tuple[dict[int, npt.NDArray[np.int_]], dict[int, npt.NDArray[np.int_]], bool]:
activity_end_times = {}
unfeasible_non_renewable_resources = False
new_horizon = horizon
resource_avail_in_time = {}
starts_dict = numba.typed.Dict.empty(
key_type=numba.types.intp,
value_type=int_array,
)
ends_dict = numba.typed.Dict.empty(
key_type=numba.types.intp,
value_type=int_array,
)
for index in range(ressource_available.shape[0]):
resource_avail_in_time[index] = np.copy(
ressource_available[index][: new_horizon + 1]
)
minimum_starting_time = {}
for act in range(permutation_task.shape[0]):
minimum_starting_time[act] = 0
done = 0
nb_task = permutation_task.shape[0]
pred_links = np.sum(predecessors, axis=1)
done_np = np.zeros((permutation_task.shape[0]), dtype=np.int_)
done_duration = np.zeros((permutation_task.shape[0]), dtype=np.int_)
while done < nb_task and not unfeasible_non_renewable_resources:
act_id = 0
for i in range(nb_task):
if (
pred_links[permutation_task[i]] == 0
and done_np[permutation_task[i]] == 0
):
act_id = permutation_task[i]
break
current_min_time = int(minimum_starting_time[act_id])
valid = False
starts = []
ends = []
while not valid:
valid = True
reached_t = None
reached_end = True
if duration_array[act_id, modes_array[act_id]] == 0:
starts.append(current_min_time)
ends.append(current_min_time)
done_duration[act_id] = 0
else:
for t in range(
current_min_time,
current_min_time
+ duration_array[act_id, modes_array[act_id]]
- done_duration[act_id],
):
if t >= new_horizon:
reached_end = False
unfeasible_non_renewable_resources = True
break
for res in range(ressource_available.shape[0]):
if t < new_horizon:
if (
resource_avail_in_time[res][t]
< consumption_array[act_id, modes_array[act_id], res]
):
reached_end = False
break
else:
unfeasible_non_renewable_resources = True
break
if reached_end:
reached_t = t
else:
break
if reached_t is not None and preemptive_tag[act_id]:
if (
not reached_end
and min_duration_preemptive_bool[act_id]
and (
min_duration_preemptive[act_id]
> (reached_t + 1 - current_min_time)
or (
duration_array[act_id, modes_array[act_id]]
- done_duration[act_id]
< min_duration_preemptive[act_id]
)
)
):
pass
else:
starts.append(current_min_time)
ends.append(reached_t + 1)
done_duration[act_id] += ends[-1] - starts[-1]
if reached_end and not preemptive_tag[act_id] and reached_t is not None:
starts.append(current_min_time)
ends.append(reached_t + 1)
done_duration[act_id] += ends[-1] - starts[-1]
valid = (
done_duration[act_id] == duration_array[act_id, modes_array[act_id]]
)
if not valid:
current_min_time = (
reached_t + 2 if reached_t is not None else current_min_time + 1
)
if unfeasible_non_renewable_resources:
break
if unfeasible_non_renewable_resources:
break
if not unfeasible_non_renewable_resources:
end_t = ends[-1]
for i in range(len(starts)):
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
starts[i] : ends[i]
] -= consumption_array[act_id, modes_array[act_id], res]
else:
if i == 0:
resource_avail_in_time[res][
starts[i] :
] -= consumption_array[act_id, modes_array[act_id], res]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
activity_end_times[act_id] = end_t
starts_dict[act_id] = np.array(starts, dtype=np.int_)
ends_dict[act_id] = np.array(ends, dtype=np.int_)
done_np[act_id] = 1
done += 1
for s in range(successors.shape[1]):
if successors[act_id, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[act_id])
)
pred_links[s] -= 1
return starts_dict, ends_dict, unfeasible_non_renewable_resources
[docs]
@njit
def sgs_fast_partial_schedule(
current_time: int,
permutation_task: npt.NDArray[np.int_], # permutation_task=array(task)->task index
modes_array: npt.NDArray[np.int_], # modes=array(task)->0, 1...
completed_task_indicator: npt.NDArray[np.int_],
completed_task_times: npt.NDArray[np.int_],
scheduled_task: npt.NDArray[np.int_],
consumption_array: npt.NDArray[
np.int_
], # consumption_array=array3D(task, mode, res),
duration_array: npt.NDArray[np.int_],
predecessors: npt.NDArray[np.int_], # array(task, task) -> bool
successors: npt.NDArray[np.int_], # array(task, task)->bool
horizon: int,
ressource_available: npt.NDArray[np.int_],
ressource_renewable: npt.NDArray[np.bool_],
minimum_starting_time_array: npt.NDArray[np.int_],
) -> tuple[dict[int, tuple[int, int]], bool]:
activity_end_times: dict[int, int] = {}
unfeasible_non_renewable_resources = False
new_horizon = horizon
resource_avail_in_time = {}
for index in range(ressource_available.shape[0]):
resource_avail_in_time[index] = np.copy(
ressource_available[index][: new_horizon + 1]
)
minimum_starting_time = {}
for act in range(permutation_task.shape[0]):
minimum_starting_time[act] = max(minimum_starting_time_array[act], current_time)
done = 0
nb_task = permutation_task.shape[0]
pred_links = np.sum(predecessors, axis=1)
done_np = np.zeros(nb_task, dtype=np.int_)
for t in range(nb_task):
if scheduled_task[t] != -1:
activity_end_times[t] = (
scheduled_task[t] + duration_array[t, modes_array[t]]
)
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
scheduled_task[t] : activity_end_times[t]
] -= consumption_array[t, modes_array[t], res]
else:
resource_avail_in_time[res][
scheduled_task[t] :
] -= consumption_array[t, modes_array[t], res]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
for s in range(successors.shape[1]):
if successors[t, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[t])
)
pred_links[s] -= 1
done += 1
done_np[t] = 1
if completed_task_indicator[t] == 1:
done += 1
done_np[t] = 1
activity_end_times[t] = completed_task_times[t]
for s in range(successors.shape[1]):
if successors[t, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[t])
)
pred_links[s] -= 1
while done < nb_task and not unfeasible_non_renewable_resources:
act_id = 0
for i in range(nb_task):
if (
pred_links[permutation_task[i]] == 0
and done_np[permutation_task[i]] == 0
):
act_id = permutation_task[i]
break
current_min_time = minimum_starting_time[act_id]
valid = False
while not valid:
valid = True
end_time = current_min_time + duration_array[act_id, modes_array[act_id]]
for t in range(current_min_time, end_time):
for res in range(ressource_available.shape[0]):
if t < new_horizon:
if (
resource_avail_in_time[res][t]
< consumption_array[act_id, modes_array[act_id], res]
):
valid = False
else:
unfeasible_non_renewable_resources = True
break
if not valid:
current_min_time += 1
if unfeasible_non_renewable_resources:
break
if not unfeasible_non_renewable_resources:
end_t = current_min_time + duration_array[act_id, modes_array[act_id]]
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
current_min_time:end_t
] -= consumption_array[act_id, modes_array[act_id], res]
else:
resource_avail_in_time[res][current_min_time:] -= consumption_array[
act_id, modes_array[act_id], res
]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
activity_end_times[act_id] = end_t
done_np[act_id] = 1
done += 1
for s in range(successors.shape[1]):
if successors[act_id, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[act_id])
)
pred_links[s] -= 1
rcpsp_schedule: dict[int, tuple[int, int]] = {}
for act_id in activity_end_times:
rcpsp_schedule[act_id] = (
activity_end_times[act_id] - duration_array[act_id, modes_array[act_id]],
activity_end_times[act_id],
)
return rcpsp_schedule, unfeasible_non_renewable_resources
[docs]
@njit
def sgs_fast_partial_schedule_incomplete_permutation_tasks(
current_time: int,
permutation_task: npt.NDArray[np.int_], # permutation_task=array(task)->task index
modes_array: npt.NDArray[np.int_], # modes=array(task)->0, 1...
completed_task_indicator: npt.NDArray[np.int_],
completed_task_times: npt.NDArray[np.int_],
scheduled_task: npt.NDArray[np.int_],
consumption_array: npt.NDArray[
np.int_
], # consumption_array=array3D(task, mode, res),
duration_array: npt.NDArray[np.int_],
predecessors: npt.NDArray[np.int_], # array(task, task) -> bool
successors: npt.NDArray[np.int_], # array(task, task)->bool
horizon: int,
ressource_available: npt.NDArray[np.int_],
ressource_renewable: npt.NDArray[np.bool_],
minimum_starting_time_array: npt.NDArray[np.int_],
) -> tuple[dict[int, tuple[int, int]], bool]:
activity_end_times = {}
unfeasible_non_renewable_resources = False
new_horizon = horizon
resource_avail_in_time = {}
for index in range(ressource_available.shape[0]):
resource_avail_in_time[index] = np.copy(
ressource_available[index][: new_horizon + 1]
)
minimum_starting_time = {}
for act in range(permutation_task.shape[0]):
minimum_starting_time[permutation_task[act]] = max(
current_time, minimum_starting_time_array[act]
)
done = 0
nb_task = permutation_task.shape[0]
pred_links = np.sum(predecessors[permutation_task, :], axis=1)
done_np = np.zeros((predecessors.shape[0]), dtype=np.int_)
for t in range(nb_task):
activity_end_times[t] = 0
for t in range(nb_task):
if scheduled_task[t] != -1:
activity_end_times[t] = (
scheduled_task[t] + duration_array[t, modes_array[t]]
)
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
scheduled_task[t] : activity_end_times[t]
] -= consumption_array[t, modes_array[t], res]
else:
resource_avail_in_time[res][
scheduled_task[t] :
] -= consumption_array[t, modes_array[t], res]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
for j in range(nb_task):
s = permutation_task[j]
if successors[t, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[t])
)
pred_links[j] -= 1
done += 1
done_np[t] = 1
if completed_task_indicator[t] == 1:
done += 1
done_np[t] = 1
activity_end_times[t] = completed_task_times[t]
for j in range(nb_task):
s = permutation_task[j]
if successors[t, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[t])
)
pred_links[j] -= 1
while done < nb_task and not unfeasible_non_renewable_resources:
act_id = 0
found = False
for i in range(nb_task):
if pred_links[i] == 0 and done_np[permutation_task[i]] == 0:
act_id = permutation_task[i]
found = True
break
if not found:
break
current_min_time = minimum_starting_time[act_id]
valid = False
while not valid:
valid = True
end_time = current_min_time + duration_array[act_id, modes_array[act_id]]
for t in range(current_min_time, end_time):
for res in range(ressource_available.shape[0]):
if t < new_horizon:
if (
resource_avail_in_time[res][t]
< consumption_array[act_id, modes_array[act_id], res]
):
valid = False
break
else:
unfeasible_non_renewable_resources = True
break
if not valid:
current_min_time += 1
if unfeasible_non_renewable_resources:
break
if not unfeasible_non_renewable_resources:
end_t = current_min_time + duration_array[act_id, modes_array[act_id]]
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
current_min_time:end_t
] -= consumption_array[act_id, modes_array[act_id], res]
else:
resource_avail_in_time[res][current_min_time:] -= consumption_array[
act_id, modes_array[act_id], res
]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
activity_end_times[act_id] = end_t
done_np[act_id] = 1
done += 1
for j in range(nb_task):
if successors[act_id, permutation_task[j]] == 1:
minimum_starting_time[permutation_task[j]] = max(
int(minimum_starting_time[permutation_task[j]]),
int(activity_end_times[act_id]),
)
pred_links[j] -= 1
rcpsp_schedule = {}
for act_id in activity_end_times:
rcpsp_schedule[act_id] = (
activity_end_times[act_id] - duration_array[act_id, modes_array[act_id]],
activity_end_times[act_id],
)
return rcpsp_schedule, unfeasible_non_renewable_resources
[docs]
@njit
def sgs_fast_partial_schedule_preemptive(
current_time: int,
permutation_task: npt.NDArray[np.int_], # permutation_task=array(task)->task index
modes_array: npt.NDArray[np.int_], # modes=array(task)->0, 1...
completed_task_indicator: npt.NDArray[np.int_],
partial_schedule_starts: npt.NDArray[np.int_], # array(task, 5)
partial_schedule_ends: npt.NDArray[np.int_], # array(task, 5)
preemptive_tag: npt.NDArray[np.bool_], # array(task)->bool
consumption_array: npt.NDArray[
np.int_
], # consumption_array=array3D(task, mode, res),
duration_array: npt.NDArray[np.int_],
predecessors: npt.NDArray[np.int_], # array(task, task) -> bool
successors: npt.NDArray[np.int_], # array(task, task)->bool
horizon: int,
ressource_available: npt.NDArray[np.int_],
ressource_renewable: npt.NDArray[np.bool_],
minimum_starting_time_array: npt.NDArray[np.int_],
) -> tuple[dict[int, npt.NDArray[np.int_]], dict[int, npt.NDArray[np.int_]], bool]:
activity_end_times = {}
unfeasible_non_renewable_resources = False
new_horizon = horizon
resource_avail_in_time = {}
for index in range(ressource_available.shape[0]):
resource_avail_in_time[index] = np.copy(
ressource_available[index][: new_horizon + 1]
)
minimum_starting_time = {}
for act in range(permutation_task.shape[0]):
minimum_starting_time[act] = max(minimum_starting_time_array[act], current_time)
starts_dict = numba.typed.Dict.empty(
key_type=numba.types.intp,
value_type=int_array,
)
ends_dict = numba.typed.Dict.empty(
key_type=numba.types.intp,
value_type=int_array,
)
done = 0
nb_task = permutation_task.shape[0]
pred_links = np.sum(predecessors, axis=1)
done_np = np.zeros(nb_task, dtype=np.int_)
done_duration = np.zeros(nb_task, dtype=np.int_)
for t in range(nb_task):
end = None
for i in range(partial_schedule_starts.shape[1]):
if partial_schedule_starts[t, i] != -1:
end = partial_schedule_ends[t, i]
done_duration[t] += (
partial_schedule_ends[t, i] - partial_schedule_starts[t, i]
)
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
partial_schedule_starts[t, i] : partial_schedule_ends[t, i]
] -= consumption_array[t, modes_array[t], res]
else:
if done_duration[t] == duration_array[t, modes_array[t]]:
resource_avail_in_time[res][
partial_schedule_starts[t, i] :
] -= consumption_array[t, modes_array[t], res]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
if (
done_duration[t] == duration_array[t, modes_array[t]]
and duration_array[t, modes_array[t]] >= 1
):
completed_task_indicator[t] = 1
if end is not None:
for s in range(successors.shape[1]):
if successors[t, s] == 1:
minimum_starting_time[s] = max(int(minimum_starting_time[s]), end)
if completed_task_indicator[t] == 1:
done += 1
done_np[t] = 1
activity_end_times[t] = end
starts_dict[t] = np.array(
[k for k in partial_schedule_starts[t, :] if k != -1], dtype=np.int_
)
ends_dict[t] = np.array(
[k for k in partial_schedule_ends[t, :] if k != -1], dtype=np.int_
)
for s in range(successors.shape[1]):
if successors[t, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[t])
)
pred_links[s] -= 1
while done < nb_task and not unfeasible_non_renewable_resources:
act_id = 0
for i in range(nb_task):
if (
pred_links[permutation_task[i]] == 0
and done_np[permutation_task[i]] == 0
):
act_id = permutation_task[i]
break
current_min_time = minimum_starting_time[act_id]
valid = False
starts = []
ends = []
while not valid:
valid = True
reached_t = None
reached_end = True
if duration_array[act_id, modes_array[act_id]] == 0:
starts.append(current_min_time)
ends.append(current_min_time)
done_duration[act_id] = 0
else:
for t in range(
current_min_time,
current_min_time
+ duration_array[act_id, modes_array[act_id]]
- done_duration[act_id],
):
if t >= new_horizon:
reached_end = False
unfeasible_non_renewable_resources = True
break
for res in range(ressource_available.shape[0]):
if t < new_horizon:
if (
resource_avail_in_time[res][t]
< consumption_array[act_id, modes_array[act_id], res]
):
reached_end = False
break
else:
unfeasible_non_renewable_resources = True
break
if reached_end:
reached_t = t
else:
break
if reached_t is not None and preemptive_tag[act_id]:
starts.append(current_min_time)
ends.append(reached_t + 1)
done_duration[act_id] += ends[-1] - starts[-1]
if reached_end and not preemptive_tag[act_id] and reached_t is not None:
starts.append(current_min_time)
ends.append(reached_t + 1)
done_duration[act_id] += ends[-1] - starts[-1]
valid = (
done_duration[act_id] == duration_array[act_id, modes_array[act_id]]
)
if not valid:
current_min_time = (
reached_t + 2 if reached_t is not None else current_min_time + 1
)
if not unfeasible_non_renewable_resources:
end_t = ends[-1]
for i in range(len(starts)):
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
starts[i] : ends[i]
] -= consumption_array[act_id, modes_array[act_id], res]
else:
if i == 0:
resource_avail_in_time[res][
starts[i] :
] -= consumption_array[act_id, modes_array[act_id], res]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
activity_end_times[act_id] = end_t
starts_dict[act_id] = np.array(
[k for k in partial_schedule_starts[act_id, :] if k != -1] + starts,
dtype=np.int_,
)
ends_dict[act_id] = np.array(
[k for k in partial_schedule_ends[act_id, :] if k != -1] + ends,
dtype=np.int_,
)
done_np[act_id] = 1
done += 1
for s in range(successors.shape[1]):
if successors[act_id, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[act_id])
)
pred_links[s] -= 1
return starts_dict, ends_dict, unfeasible_non_renewable_resources
[docs]
@njit
def sgs_fast_partial_schedule_preemptive_minduration(
current_time: int,
permutation_task: npt.NDArray[np.int_], # permutation_task=array(task)->task index
modes_array: npt.NDArray[np.int_], # modes=array(task)->0, 1...
completed_task_indicator: npt.NDArray[np.int_],
partial_schedule_starts: npt.NDArray[np.int_], # array(task, 5)
partial_schedule_ends: npt.NDArray[np.int_], # array(task, 5)
preemptive_tag: npt.NDArray[np.bool_], # array(task)->bool
consumption_array: npt.NDArray[
np.int_
], # consumption_array=array3D(task, mode, res),
duration_array: npt.NDArray[np.int_],
predecessors: npt.NDArray[np.int_], # array(task, task) -> bool
successors: npt.NDArray[np.int_], # array(task, task)->bool
horizon: int,
ressource_available: npt.NDArray[np.int_],
ressource_renewable: npt.NDArray[np.bool_],
min_duration_preemptive_bool: npt.NDArray[np.bool_],
min_duration_preemptive: npt.NDArray[np.int_],
) -> tuple[dict[int, npt.NDArray[np.int_]], dict[int, npt.NDArray[np.int_]], bool]:
activity_end_times = {}
unfeasible_non_renewable_resources = False
new_horizon = horizon
resource_avail_in_time = {}
for index in range(ressource_available.shape[0]):
resource_avail_in_time[index] = np.copy(
ressource_available[index][: new_horizon + 1]
)
minimum_starting_time = {}
for act in range(permutation_task.shape[0]):
minimum_starting_time[act] = current_time
starts_dict = numba.typed.Dict.empty(
key_type=numba.types.intp,
value_type=int_array,
)
ends_dict = numba.typed.Dict.empty(
key_type=numba.types.intp,
value_type=int_array,
)
done = 0
nb_task = permutation_task.shape[0]
pred_links = np.sum(predecessors, axis=1)
done_np = np.zeros(nb_task, dtype=np.int_)
done_duration = np.zeros(nb_task, dtype=np.int_)
for t in range(nb_task):
end = None
for i in range(partial_schedule_starts.shape[1]):
if partial_schedule_starts[t, i] != -1:
end = partial_schedule_ends[t, i]
done_duration[t] += (
partial_schedule_ends[t, i] - partial_schedule_starts[t, i]
)
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
partial_schedule_starts[t, i] : partial_schedule_ends[t, i]
] -= consumption_array[t, modes_array[t], res]
else:
if done_duration[t] == duration_array[t, modes_array[t]]:
resource_avail_in_time[res][
partial_schedule_starts[t, i] :
] -= consumption_array[t, modes_array[t], res]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
if (
done_duration[t] == duration_array[t, modes_array[t]]
and duration_array[t, modes_array[t]] >= 1
):
completed_task_indicator[t] = 1
if end is not None:
for s in range(successors.shape[1]):
if successors[t, s] == 1:
minimum_starting_time[s] = max(int(minimum_starting_time[s]), end)
if completed_task_indicator[t] == 1:
done += 1
done_np[t] = 1
activity_end_times[t] = end
starts_dict[t] = np.array(
[k for k in partial_schedule_starts[t, :] if k != -1], dtype=np.int_
)
ends_dict[t] = np.array(
[k for k in partial_schedule_ends[t, :] if k != -1], dtype=np.int_
)
for s in range(successors.shape[1]):
if successors[t, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[t])
)
pred_links[s] -= 1
while done < nb_task and not unfeasible_non_renewable_resources:
act_id = 0
for i in range(nb_task):
if (
pred_links[permutation_task[i]] == 0
and done_np[permutation_task[i]] == 0
):
act_id = permutation_task[i]
break
current_min_time = minimum_starting_time[act_id]
valid = False
starts = []
ends = []
while not valid:
valid = True
reached_t = None
reached_end = True
if duration_array[act_id, modes_array[act_id]] == 0:
starts.append(current_min_time)
ends.append(current_min_time)
done_duration[act_id] = 0
else:
for t in range(
current_min_time,
current_min_time
+ duration_array[act_id, modes_array[act_id]]
- done_duration[act_id],
):
if t >= new_horizon:
reached_end = False
unfeasible_non_renewable_resources = True
break
for res in range(ressource_available.shape[0]):
if t < new_horizon:
if (
resource_avail_in_time[res][t]
< consumption_array[act_id, modes_array[act_id], res]
):
reached_end = False
break
else:
unfeasible_non_renewable_resources = True
break
if reached_end:
reached_t = t
else:
break
if reached_t is not None and preemptive_tag[act_id]:
if (
not reached_end
and min_duration_preemptive_bool[act_id]
and (
min_duration_preemptive[act_id]
> (reached_t + 1 - current_min_time)
or (
duration_array[act_id, modes_array[act_id]]
- done_duration[act_id]
< min_duration_preemptive[act_id]
)
)
):
logger.debug("passed")
else:
starts.append(current_min_time)
ends.append(reached_t + 1)
done_duration[act_id] += ends[-1] - starts[-1]
if reached_end and not preemptive_tag[act_id] and reached_t is not None:
starts.append(current_min_time)
ends.append(reached_t + 1)
done_duration[act_id] += ends[-1] - starts[-1]
valid = (
done_duration[act_id] == duration_array[act_id, modes_array[act_id]]
)
if not valid:
current_min_time = (
reached_t + 2 if reached_t is not None else current_min_time + 1
)
if not unfeasible_non_renewable_resources:
end_t = ends[-1]
for i in range(len(starts)):
for res in range(ressource_available.shape[0]):
if ressource_renewable[res]:
resource_avail_in_time[res][
starts[i] : ends[i]
] -= consumption_array[act_id, modes_array[act_id], res]
else:
if i == 0:
resource_avail_in_time[res][
starts[i] :
] -= consumption_array[act_id, modes_array[act_id], res]
if resource_avail_in_time[res][-1] < 0:
unfeasible_non_renewable_resources = True
break
if unfeasible_non_renewable_resources:
break
activity_end_times[act_id] = end_t
starts_dict[act_id] = np.array(
[k for k in partial_schedule_starts[act_id, :] if k != -1] + starts,
dtype=np.int_,
)
ends_dict[act_id] = np.array(
[k for k in partial_schedule_ends[act_id, :] if k != -1] + ends,
dtype=np.int_,
)
done_np[act_id] = 1
done += 1
for s in range(successors.shape[1]):
if successors[act_id, s] == 1:
minimum_starting_time[s] = max(
int(minimum_starting_time[s]), int(activity_end_times[act_id])
)
pred_links[s] -= 1
return starts_dict, ends_dict, unfeasible_non_renewable_resources
[docs]
@njit
def compute_mean_ressource(
modes_array: npt.NDArray[np.int_], # modes=array(task)->0, 1...
consumption_array: npt.NDArray[
np.int_
], # consumption_array=array3D(task, mode, res),
start_array: npt.NDArray[np.int_],
end_array: npt.NDArray[np.int_],
horizon: int,
ressource_available: npt.NDArray[np.int_],
ressource_renewable: npt.NDArray[np.bool_],
) -> float:
new_horizon = horizon
resource_avail_in_time = {}
for index in range(ressource_available.shape[0]):
resource_avail_in_time[index] = np.copy(
ressource_available[index, : new_horizon + 1]
)
nb_task = start_array.shape[0]
for t in range(nb_task):
start_time = start_array[t]
end_time = end_array[t]
for res_index in resource_avail_in_time:
if ressource_renewable[res_index]:
resource_avail_in_time[res_index][
start_time:end_time
] -= consumption_array[t, modes_array[t], res_index]
else:
resource_avail_in_time[res_index][start_time:] -= consumption_array[
t, modes_array[t], res_index
]
mean_avail = {}
for res in resource_avail_in_time:
mean_avail[res] = np.mean(resource_avail_in_time[res])
mean_resource_reserve = np.mean(
np.array(
[
mean_avail[res_index] / np.max(ressource_available[res_index, :])
for res_index in range(ressource_available.shape[0])
]
)
)
return float(mean_resource_reserve)
[docs]
@njit
def compute_ressource_consumption(
modes_array: npt.NDArray[np.int_], # modes=array(task)->0, 1...
consumption_array: npt.NDArray[
np.int_
], # consumption_array=array3D(task, mode, res),
start_array: npt.NDArray[np.int_],
end_array: npt.NDArray[np.int_],
horizon: int,
ressource_available: npt.NDArray[np.int_],
ressource_renewable: npt.NDArray[np.bool_],
) -> dict[int, npt.NDArray[np.int_]]:
new_horizon = horizon
resource_avail_in_time: dict[int, npt.NDArray[np.int_]] = {}
for index in range(ressource_available.shape[0]):
resource_avail_in_time[index] = np.zeros(new_horizon + 1, dtype=np.int_)
nb_task = start_array.shape[0]
for t in range(nb_task):
start_time = start_array[t]
end_time = end_array[t]
for res_index in resource_avail_in_time:
if ressource_renewable[res_index]:
resource_avail_in_time[res_index][
start_time:end_time
] += consumption_array[t, modes_array[t], res_index]
else:
resource_avail_in_time[res_index][start_time:] += consumption_array[
t, modes_array[t], res_index
]
return resource_avail_in_time