job_shop_lib.graphs

Package for graph related classes and functions.

The main classes and functions available in this package are:

JobShopGraph(instance[, add_operation_nodes])

Represents a JobShopInstance as a heterogeneous directed graph.

Node(node_type[, operation, machine_id, job_id])

Represents a node in the JobShopGraph.

NodeType(value[, names, module, qualname, ...])

Enumeration of node types.

build_disjunctive_graph(instance)

Builds and returns a disjunctive graph for the given job shop instance.

build_agent_task_graph(instance)

Builds the agent-task graph of the instance.

build_complete_agent_task_graph(instance)

Builds the agent-task graph of the instance with job and global nodes.

build_agent_task_graph_with_jobs(instance)

Builds the agent-task graph of the instance with job nodes.

class EdgeType(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)[source]

Bases: Enum

Enumeration of edge types.

CONJUNCTIVE = 0
DISJUNCTIVE = 1
class NodeType(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)[source]

Bases: Enum

Enumeration of node types.

Nodes of type NodeType.OPERATION, NodeType.MACHINE, and NodeType.JOB have specific attributes associated with them in the Node class.

On the other hand, Nodes of type NodeType.GLOBAL, NodeType.SOURCE, and NodeType.SINK are used to represent different concepts in the graph and accesing them, but they do not have specific attributes associated with them.

Tip

While uncommon, it can be useful to extend this enumeration with additional node types. This can be achieved using aenum's extend_enum (requires using Python 3.11+).

OPERATION = 1
MACHINE = 2
JOB = 3
GLOBAL = 4
SOURCE = 5
SINK = 6
class Node(node_type, operation=None, machine_id=None, job_id=None)[source]

Bases: object

Represents a node in the JobShopGraph.

A node is hashable by its id. The id is assigned when the node is added to the graph. The id must be unique for each node in the graph, and should be used to identify the node in the networkx graph.

Depending on the type of the node, it can have different attributes. The following table shows the attributes of each type of node:

Node Type

Required Attribute

OPERATION

operation

MACHINE

machine_id

JOB

job_id

In terms of equality, two nodes are equal if they have the same id. Additionally, one node is equal to an integer if the integer is equal to its id. It is also hashable by its id.

This allows for using the node as a key in a dictionary, at the same time we can use its id to index that dictionary. Example:

node = Node(NodeType.SOURCE)
node.node_id = 1
graph = {node: "some value"}
print(graph[node])  # "some value"
print(graph[1])  # "some value"
Parameters:
  • node_type (NodeType) -- The type of the node. See NodeType for theavailable types.

  • operation (Operation | None) -- The operation of the node. Required if node_type is NodeType.OPERATION.

  • machine_id (int | None) -- The id of the machine. Required if node_type is NodeType.MACHINE.

  • job_id (int | None) -- The id of the job. Required if node_type is NodeType.JOB.

Raises:

ValidationError -- If the node_type is NodeType.OPERATION, NodeType.MACHINE, or NodeType.JOB and the corresponding operation, machine_id, or job_id is None, respectively.

node_type: NodeType

The type of the node.

property node_id: int

Returns a unique identifier for the node.

property operation: Operation

Returns the operation of the node.

This property is mandatory for nodes of type NodeType.OPERATION.

Raises:

UninitializedAttributeError -- If the node has no operation.

property machine_id: int

Returns the machine_id of the node.

This property is mandatory for nodes of type MACHINE.

Raises:

UninitializedAttributeError -- If the node has no machine_id.

property job_id: int

Returns the job_id of the node.

This property is mandatory for nodes of type JOB.

Raises:

UninitializedAttributeError -- If the node has no job_id.

class JobShopGraph(instance, add_operation_nodes=True)[source]

Bases: object

Represents a JobShopInstance as a heterogeneous directed graph.

Provides a comprehensive graph-based representation of a job shop scheduling problem, utilizing the networkx library to model the complex relationships between jobs, operations, and machines. This class transforms the abstract scheduling problem into a directed graph, where various entities (jobs, machines, and operations) are nodes, and the dependencies (such as operation order within a job or machine assignment) are edges.

This transformation allows for the application of graph algorithms to analyze and solve scheduling problems.

Parameters:
  • instance (JobShopInstance) -- The job shop instance that the graph represents.

  • add_operation_nodes (bool) -- Whether to add nodes of type NodeType.OPERATION to the to the graph. If set to False, the graph will be empty, and operation nodes will need to be added manually.

graph

The directed graph representing the job shop, where nodes are operations, machines, jobs, or abstract concepts like global, source, and sink, with edges indicating dependencies.

instance

The job shop instance that the graph represents.

removed_nodes: list[bool]

List of boolean values indicating whether a node has been removed from the graph.

property nodes: list[Node]

List of all nodes added to the graph.

It may contain nodes that have been removed from the graph.

property nodes_by_type: dict[NodeType, list[Node]]

Dictionary mapping node types to lists of nodes.

It may contain nodes that have been removed from the graph.

property nodes_by_machine: list[list[Node]]

List of lists mapping machine ids to operation nodes.

It may contain nodes that have been removed from the graph.

property nodes_by_job: list[list[Node]]

List of lists mapping job ids to operation nodes.

It may contain nodes that have been removed from the graph.

property num_edges: int

Number of edges in the graph.

property num_job_nodes: int

Number of job nodes in the graph.

add_operation_nodes()[source]

Adds operation nodes to the graph.

Return type:

None

add_node(node_for_adding)[source]

Adds a node to the graph and updates relevant class attributes.

This method assigns a unique identifier to the node, adds it to the graph, and updates the nodes list and the nodes_by_type dictionary. If the node is of type OPERATION, it also updates nodes_by_job and nodes_by_machine based on the operation's job_id and machine_ids.

Parameters:

node_for_adding (Node) -- The node to be added to the graph.

Raises:
  • ValueError -- If the node type is unsupported or if required

  • attributes for the node type are missing. --

Return type:

None

Note

This method directly modifies the graph attribute as well as several other class attributes. Thus, adding nodes to the graph should be done exclusively through this method to avoid inconsistencies.

add_edge(u_of_edge, v_of_edge, **attr)[source]

Adds an edge to the graph.

Parameters:
  • u_of_edge (Node | int) -- The source node of the edge. If it is a Node, its node_id is used as the source. Otherwise, it is assumed to be the node_id of the source.

  • v_of_edge (Node | int) -- The destination node of the edge. If it is a Node, its node_id is used as the destination. Otherwise, it is assumed to be the node_id of the destination.

  • **attr -- Additional attributes to be added to the edge.

Raises:

JobShopLibError -- If u_of_edge or v_of_edge are not in the graph.

Return type:

None

remove_node(node_id)[source]

Removes a node from the graph and the isolated nodes that result from the removal.

Parameters:

node_id (int) -- The id of the node to remove.

Return type:

None

is_removed(node)[source]

Returns whether the node is removed from the graph.

Parameters:

node (int | Node) -- The node to check. If it is a Node, its node_id is used as the node to check. Otherwise, it is assumed to be the node_id of the node to check.

Return type:

bool

non_removed_nodes()[source]

Returns the nodes that are not removed from the graph.

Return type:

list[Node]

get_machine_node(machine_id)[source]

Returns the node representing the machine with the given id.

Parameters:

machine_id (int) -- The id of the machine.

Returns:

The node representing the machine with the given id.

Return type:

Node

get_job_node(job_id)[source]

Returns the node representing the job with the given id.

Parameters:

job_id (int) -- The id of the job.

Returns:

The node representing the job with the given id.

Return type:

Node

get_operation_node(operation_id)[source]

Returns the node representing the operation with the given id.

Parameters:

operation_id (int) -- The id of the operation.

Returns:

The node representing the operation with the given id.

Return type:

Node

get_node_by_type_and_id(node_type, node_id, id_attr)[source]

Generic method to get a node by type and id.

Parameters:
  • node_type (NodeType) -- The type of the node.

  • node_id (int) -- The id of the node.

  • id_attr (str) -- The attribute name to compare the id. Can be nested like 'operation.operation_id'.

Returns:

The node with the given id.

Return type:

Node

build_disjunctive_graph(instance)[source]

Builds and returns a disjunctive graph for the given job shop instance.

This function creates a complete disjunctive graph from a JobShopInstance. It starts by initializing a JobShopGraph object and proceeds by adding disjunctive edges between operations using the same machine, conjunctive edges between successive operations in the same job, and finally, special source and sink nodes with their respective edges to and from all other operations.

Edges have a "type" attribute indicating whether they are disjunctive or conjunctive.

Parameters:
  • instance (JobShopInstance) -- The job shop instance for which to build

  • graph. (the)

Returns:

A JobShopGraph object representing the disjunctive graph of the job shop scheduling problem.

Return type:

JobShopGraph

add_disjunctive_edges(graph)[source]

Adds disjunctive edges to the graph.

Parameters:

graph (JobShopGraph)

Return type:

None

add_conjunctive_edges(graph)[source]

Adds conjunctive edges to the graph.

Parameters:

graph (JobShopGraph)

Return type:

None

add_source_sink_nodes(graph)[source]

Adds source and sink nodes to the graph.

Parameters:

graph (JobShopGraph)

Return type:

None

add_source_sink_edges(graph)[source]

Adds edges between source and sink nodes and operations.

Parameters:

graph (JobShopGraph)

Return type:

None

build_agent_task_graph(instance)[source]

Builds the agent-task graph of the instance.

The agent-task graph was introduced by Junyoung Park et al. (2021).

In contrast to the disjunctive graph, instead of connecting operations that share the same resources directly by disjunctive edges, operation nodes are connected with machine ones.

All machine nodes are connected between them, and all operation nodes from the same job are connected by non-directed edges too.

Parameters:

instance (JobShopInstance) -- The job shop instance in which the agent-task graph will be built.

Returns:

The agent-task graph of the instance.

Return type:

JobShopGraph

build_complete_agent_task_graph(instance)[source]

Builds the agent-task graph of the instance with job and global nodes.

The complete agent-task graph is a generalization of the agent-task graph that includes job nodes and a global node.

Job nodes are connected to all operation nodes of the same job, and the global node is connected to all machine and job nodes.

This representation does not include edges between job or machine nodes with the same type because they are connected indirectly by the global node.

Parameters:

instance (JobShopInstance) -- The job shop instance in which the agent-task graph will be built.

Returns:

The complete agent-task graph of the instance.

Return type:

JobShopGraph

build_agent_task_graph_with_jobs(instance)[source]

Builds the agent-task graph of the instance with job nodes.

The agent-task graph with job nodes is a generalization of the agent-task graph that includes job nodes.

Job nodes are connected to all operation nodes of the same job, and their are connected between them.

Parameters:

instance (JobShopInstance) -- The job shop instance in which the agent-task graph will be built.

Returns:

The agent-task graph of the instance with job nodes.

Return type:

JobShopGraph

add_same_job_operations_edges(graph)[source]

Adds edges between all operations of the same job.

Parameters:

graph (JobShopGraph)

Return type:

None

add_machine_nodes(graph)[source]

Adds a machine node for each machine in the instance.

Parameters:

graph (JobShopGraph)

Return type:

None

add_operation_machine_edges(graph)[source]

Adds edges between operation and machine nodes.

Parameters:

graph (JobShopGraph)

Return type:

None

add_machine_machine_edges(graph)[source]

Adds edges between all machine nodes.

Parameters:

graph (JobShopGraph)

Return type:

None

add_job_nodes(graph)[source]

Adds a job node for each job in the instance.

Parameters:

graph (JobShopGraph)

Return type:

None

add_operation_job_edges(graph)[source]

Adds edges between operation and job nodes.

Parameters:

graph (JobShopGraph)

Return type:

None

add_global_node(graph)[source]

Adds a global node to the graph.

Parameters:

graph (JobShopGraph)

Return type:

None

add_machine_global_edges(graph)[source]

Adds edges between machine and global nodes.

Parameters:

graph (JobShopGraph)

Return type:

None

add_job_global_edges(graph)[source]

Adds edges between job and global nodes.

Parameters:

graph (JobShopGraph)

Return type:

None

Modules

graph_updaters

Contains classes and functions for updating the graph representation of the job shop scheduling problem.