job_shop_lib.graphs¶
Package for graph related classes and functions.
The main classes and functions available in this package are:
|
Represents a |
|
Represents a node in the |
|
Enumeration of node types. |
|
Builds and returns a disjunctive graph for the given job shop instance. |
|
Builds the agent-task graph of the instance. |
|
Builds the agent-task graph of the instance with job and global nodes. |
|
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
, andNodeType.JOB
have specific attributes associated with them in theNode
class.On the other hand, Nodes of type
NodeType.GLOBAL
,NodeType.SOURCE
, andNodeType.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
isNodeType.OPERATION
.machine_id (int | None) -- The id of the machine. Required if
node_type
isNodeType.MACHINE
.job_id (int | None) -- The id of the job. Required if
node_type
isNodeType.JOB
.
- Raises:
ValidationError -- If the
node_type
isNodeType.OPERATION
,NodeType.MACHINE
, orNodeType.JOB
and the correspondingoperation
,machine_id
, orjob_id
isNone
, respectively.
- 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 toFalse
, 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_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:
- 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:
- 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:
- 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 buildgraph. (the)
- Returns:
A JobShopGraph object representing the disjunctive graph of the job shop scheduling problem.
- Return type:
- 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:
- 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:
- 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:
- 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
Contains classes and functions for updating the graph representation of the job shop scheduling problem. |