Disjunctive Graph representation¶

The disjunctive graph is created by first adding nodes representing each operation in the jobs, along with two special nodes: a source \(S\) and a sink \(T\). Each operation node is linked to the next operation in its job sequence by conjunctive edges, forming a path from the source to the sink. These edges represent the order in which operations of a single job must be performed.

Additionally, the graph includes disjunctive edges between operations that use the same machine but belong to different jobs. These edges are bidirectional, indicating that either of the connected operations can be performed first. The disjunctive edges thus represent the scheduling choices available: the order in which operations sharing a machine can be processed. Solving the job shop scheduling problem involves choosing a direction for each disjunctive edge such that the overall processing time is minimized.

[1]:

from job_shop_lib import JobShopInstance, Operation
from job_shop_lib.graphs import build_disjunctive_graph
from job_shop_lib.visualization.graphs import plot_disjunctive_graph

CPU = 0
GPU = 1
DATA_CENTER = 2

job_1 = [Operation(CPU, 1), Operation(GPU, 1), Operation(DATA_CENTER, 7)]
job_2 = [Operation(GPU, 5), Operation(DATA_CENTER, 1), Operation(CPU, 1)]
job_3 = [Operation(DATA_CENTER, 1), Operation(CPU, 3), Operation(GPU, 2)]

jobs = [job_1, job_2, job_3]

instance = JobShopInstance(jobs, name="Example")

[2]:

graph = build_disjunctive_graph(instance)

[3]:

graph.nodes

[3]:

[Node(node_type=OPERATION, id=0, operation=O(m=0, d=1, j=0, p=0)),
 Node(node_type=OPERATION, id=1, operation=O(m=1, d=1, j=0, p=1)),
 Node(node_type=OPERATION, id=2, operation=O(m=2, d=7, j=0, p=2)),
 Node(node_type=OPERATION, id=3, operation=O(m=1, d=5, j=1, p=0)),
 Node(node_type=OPERATION, id=4, operation=O(m=2, d=1, j=1, p=1)),
 Node(node_type=OPERATION, id=5, operation=O(m=0, d=1, j=1, p=2)),
 Node(node_type=OPERATION, id=6, operation=O(m=2, d=1, j=2, p=0)),
 Node(node_type=OPERATION, id=7, operation=O(m=0, d=3, j=2, p=1)),
 Node(node_type=OPERATION, id=8, operation=O(m=1, d=2, j=2, p=2)),
 Node(node_type=SOURCE, id=9),
 Node(node_type=SINK, id=10)]

[4]:

graph.nodes_by_type

[4]:

defaultdict(list,
            {<NodeType.OPERATION: 1>: [Node(node_type=OPERATION, id=0, operation=O(m=0, d=1, j=0, p=0)),
              Node(node_type=OPERATION, id=1, operation=O(m=1, d=1, j=0, p=1)),
              Node(node_type=OPERATION, id=2, operation=O(m=2, d=7, j=0, p=2)),
              Node(node_type=OPERATION, id=3, operation=O(m=1, d=5, j=1, p=0)),
              Node(node_type=OPERATION, id=4, operation=O(m=2, d=1, j=1, p=1)),
              Node(node_type=OPERATION, id=5, operation=O(m=0, d=1, j=1, p=2)),
              Node(node_type=OPERATION, id=6, operation=O(m=2, d=1, j=2, p=0)),
              Node(node_type=OPERATION, id=7, operation=O(m=0, d=3, j=2, p=1)),
              Node(node_type=OPERATION, id=8, operation=O(m=1, d=2, j=2, p=2))],
             <NodeType.SOURCE: 5>: [Node(node_type=SOURCE, id=9)],
             <NodeType.SINK: 6>: [Node(node_type=SINK, id=10)]})

[5]:

graph.nodes_by_machine

[5]:

[[Node(node_type=OPERATION, id=0, operation=O(m=0, d=1, j=0, p=0)),
  Node(node_type=OPERATION, id=5, operation=O(m=0, d=1, j=1, p=2)),
  Node(node_type=OPERATION, id=7, operation=O(m=0, d=3, j=2, p=1))],
 [Node(node_type=OPERATION, id=1, operation=O(m=1, d=1, j=0, p=1)),
  Node(node_type=OPERATION, id=3, operation=O(m=1, d=5, j=1, p=0)),
  Node(node_type=OPERATION, id=8, operation=O(m=1, d=2, j=2, p=2))],
 [Node(node_type=OPERATION, id=2, operation=O(m=2, d=7, j=0, p=2)),
  Node(node_type=OPERATION, id=4, operation=O(m=2, d=1, j=1, p=1)),
  Node(node_type=OPERATION, id=6, operation=O(m=2, d=1, j=2, p=0))]]

[6]:

graph.nodes_by_job

[6]:

[[Node(node_type=OPERATION, id=0, operation=O(m=0, d=1, j=0, p=0)),
  Node(node_type=OPERATION, id=1, operation=O(m=1, d=1, j=0, p=1)),
  Node(node_type=OPERATION, id=2, operation=O(m=2, d=7, j=0, p=2))],
 [Node(node_type=OPERATION, id=3, operation=O(m=1, d=5, j=1, p=0)),
  Node(node_type=OPERATION, id=4, operation=O(m=2, d=1, j=1, p=1)),
  Node(node_type=OPERATION, id=5, operation=O(m=0, d=1, j=1, p=2))],
 [Node(node_type=OPERATION, id=6, operation=O(m=2, d=1, j=2, p=0)),
  Node(node_type=OPERATION, id=7, operation=O(m=0, d=3, j=2, p=1)),
  Node(node_type=OPERATION, id=8, operation=O(m=1, d=2, j=2, p=2))]]

[7]:

_ = plot_disjunctive_graph(graph, figsize=(6, 4))

../_images/examples_04-Disjunctive-Graph_7_0.png

[8]:

# You cal also pass the instance directly
_ = plot_disjunctive_graph(
    instance,
    figsize=(6, 4),
    draw_disjunctive_edges="single_edge",
    disjunctive_edges_additional_params={
        "arrowstyle": "<|-|>",
        "connectionstyle": "arc3,rad=0.15",
    },
)

../_images/examples_04-Disjunctive-Graph_8_0.png

[9]:

# Let's remove some nodes
graph.remove_node(0)
graph.remove_node(3)
graph.remove_node(4)
_ = plot_disjunctive_graph(graph, figsize=(6, 4))

../_images/examples_04-Disjunctive-Graph_9_0.png

[10]:

_ = plot_disjunctive_graph(
    instance,
    title="",
    machine_labels=[
        "GPU",
        "CPU",
        "Data Center",
    ],
    edge_width=1.5,
    draw_disjunctive_edges="single_edge",
    disjunctive_edges_additional_params={
        "connectionstyle": "arc3,rad=0.15",
        "arrowstyle": "<|-|>",
    },
)

../_images/examples_04-Disjunctive-Graph_10_0.png

[ ]: