Algorithm

algorithm.allocate_jobs_to_machines_nx(graph: DiGraph, num_machines=8)

Allocates jobs to machines based on a directed graph of job dependencies using NetworkX.

This function attempts to optimize job allocation by considering the critical path and job dependencies to minimize overall completion time across a specified number of machines.

Args: - graph (nx.DiGraph): A directed graph where nodes represent jobs, and edges represent dependencies. - num_machines (int, optional): The number of machines available for job allocation. Defaults to 8. Returns: - machines (list of lists of dicts): A nested list where each sublist represents the allocation of jobs to a machine. Each job is represented as a dictionary containing ‘start_time’, ‘end_time’,

‘duration’, and ‘job_index’.

algorithm.allocate_jobs_to_machines_with_heuristic_rx(graph: (<class 'rustworkx.PyDiGraph'>, <class 'dict'>), num_machines=8)

Allocates jobs to machines using a heuristic approach on a directed graph with retworkx.

This function takes a graph representing job dependencies and a dictionary of job durations, then allocates jobs to machines aiming to minimize overall completion time. It uses an optimized approach for determining the earliest start time for each job based on its dependencies.

Args: - graph (tuple): A tuple containing a retworkx PyDiGraph and a dictionary of job durations. - num_machines (int, optional): The number of machines available for allocation. Defaults to 8. Returns: - jobs (dict): A dictionary where each key is a job index and each value is a dictionary containing ‘start_time’, ‘end_time’, ‘duration’, and ‘machine_index’ for the job.

algorithm.calculate_rank(task, ranks, graph, memo={})

Recursively calculates the rank of a given task. Utilizes memoization to avoid recalculating ranks for tasks.

Parameters:

• task (Any) – The task for which to calculate the rank.

• ranks (dict) – A dictionary of precomputed ranks for some tasks.

• graph (nx.DiGraph) – The DAG of tasks.

• memo (dict, optional) – A dictionary used for memoization of task ranks. Defaults to {}.

Returns: Any: The rank of the specified task.

algorithm.calculate_ranks(graph: DiGraph)

Calculates the priority rank for each task in the graph, which is used to order tasks for scheduling. The rank of a task is the longest path from it to an exit task, including its own duration.

Parameters:

graph (nx.DiGraph) – The DAG of tasks.

Returns: dict: A dictionary mapping each task to its rank.

algorithm.earliest_start_time(task, graph, schedule)

Calculates the earliest start time for a task on any machine, considering the task dependencies and the current schedule.

Parameters:

• task (dict) – The task for which to calculate the earliest start time.

• graph (nx.DiGraph) – The DAG of tasks.

• schedule (Any) – The current schedule of tasks on machines.

Returns: float: The earliest time at which the specified task can start executing.

algorithm.earliest_start_time_optimized(task, graph, schedule)

Calculates the earliest start time for a given task based on its dependencies.

This function examines a task’s dependencies within a directed graph and determines the earliest time the task can start, based on the completion times of its dependencies.

Args: - task (int/str): The identifier for the task whose earliest start time is being calculated. - graph (Directed Graph): The graph representing task dependencies. - schedule (dict): A dictionary where keys are task identifiers and values are dictionaries containing ‘end_time’ among other scheduling details. Returns: - int: The earliest start time for the given task.

algorithm.heft(graph: DiGraph, num_machines: int)

Implements the core HEFT algorithm. It schedules tasks (nodes in the DAG) across a given number of machines to minimize the overall execution time.

Parameters:

• graph (nx.DiGraph) – A networkx directed acyclic graph where nodes represent tasks and edges represent dependencies between tasks. Each node has a ‘duration’ attribute indicating the task’s execution time.

• num_machines (int) – The number of machines available for executing these tasks.

Returns: Any: A schedule that is a list of lists. Each sublist represents the schedule for a machine, containing dictionaries with keys ‘start_time’, ‘end_time’, ‘duration’, and ‘job_index’, detailing each task’s scheduling.

algorithm.leveled_topological_sort(graph: PyDiGraph)

Performs a leveled topological sort on a directed graph.

This function iterates through the graph, removing nodes with no incoming edges (indicating no dependencies) and their associated edges, effectively sorting the nodes in a way that respects their dependencies. The sorting is “leveled” in the sense that it groups nodes by their distance from the start nodes (with no dependencies).

Args: - graph (rx.PyDiGraph): A directed graph where nodes represent tasks and edges represent dependencies. Returns: - None: This function modifies the graph in-place and does not return a value.

algorithm.pretty_print_allocated_jobs(machines)

Prints a visual representation of job allocations across multiple machines. Each machine’s allocated jobs are displayed as bars, where the length of the bar represents the job’s duration. The output is designed to give a quick visual overview of the workload distribution among the machines.

Args: - machines (list of lists of dicts): A nested list where each sublist represents a machine and contains dictionaries with job details, including ‘end_time’ and ‘duration’ keys. Returns: - None: This function prints the job allocations to stdout and does not return any value.

algorithm.select_machine(task, schedule, free_time)

algorithm.transform_allocation_format(jobs, num_machines)

Transforms the job allocation format from a dictionary with job indexes as keys to a list of lists of dictionaries, where each sublist represents the jobs allocated to a machine, sorted by their start times.

Args: - jobs (dict): A dictionary where each key is a job index and each value is a dictionary containing ‘start_time’, ‘end_time’, ‘duration’, and ‘machine_index’ for the job. - num_machines (int): The number of machines jobs are allocated to. Returns: - machines (list of lists of dicts): A nested list where each sublist represents the allocation of jobs to a machine, sorted by their start time. Each job is represented as a dictionary containing

‘start_time’, ‘end_time’, ‘duration’, and ‘job_index’.

verification.read_json(filepath)

Function to read JSON data from a file

Parameters:

filepath (str) – Path to the JSON file

Returns:

JSON data read from the file

Return type:

dict

verification.verifcation_overlap_machine(schedule)

Verify if there is any overlap in job scheduling for each machine

Parameters:

schedule (list) – List of schedules for each machine

Returns:

True if no overlap is found, False otherwise

Return type:

bool

verification.verification_dependencies(graph, schedule)

Verify if all job dependencies are satisfied in the schedule

Parameters:

• graph (networkx.DiGraph) – Directed acyclic graph representing job dependencies

• schedule (list) – List of schedules for each machine

Returns:

True if all dependencies are satisfied, False otherwise

Return type:

bool

applicated_criteria.SLR(G, nombre_machine)

Calculates the Schedule Length Ratio (SLR) for a graph and a given number of machines.

The SLR is the ratio of the makespan to the total duration of the critical path, indicating efficiency.

Parameters: - G (nx.DiGraph): The graph representing the set of jobs. - nombre_machine (int): The number of machines over which jobs are to be scheduled.

Returns: - float: The Schedule Length Ratio.

applicated_criteria.convertir_date(secondes)

Converts a duration in seconds into a more readable format (days, hours, minutes, seconds).

Parameters: - secondes (int): The duration in seconds.

Returns: - datetime.timedelta: The duration as a datetime.timedelta object.

applicated_criteria.critical_path(G)

Finds the critical path in the input graph, defined as the longest path in terms of total duration.

Parameters: - G (nx.DiGraph): The directed acyclic graph (DAG) in which to find the critical path.

Returns: - datetime.timedelta: The total duration of the critical path.

applicated_criteria.makespan(G, nombre_machine)

Calculates the makespan for a given graph and number of machines, using a heuristic allocation algorithm.

Parameters: - G (nx.DiGraph): The input graph representing jobs to be scheduled. - nombre_machine (int): The number of machines available for scheduling.

Returns: - datetime.timedelta: The makespan for the scheduling scenario.

applicated_criteria.total_weight(T)

Calculates the total weight of all edges in a graph.

Parameters: - T (nx.DiGraph): The directed graph whose edge weights are to be summed.

Returns: - datetime.timedelta: The sum of all edge weights in the graph.

applicated_criteria.transform_node_to_edge(G)

Transforms a graph by converting node weights into edge weights.

Each node’s weight in the input graph is applied as the weight of outgoing edges. Additionally, a special ‘end’ node is created, and all leaf nodes are connected to this ‘end’ node with their weights.

Parameters: - G (nx.DiGraph): The input directed acyclic graph (DAG) with nodes having ‘duration’ as their weight.

Returns: - nx.DiGraph: A transformed directed graph with node weights converted to edge weights.