Comparing Performance: Dispatcher Method vs. Observer Method for Unscheduled Operations

In this tutorial, we’ll compare the performance of two methods for accessing unscheduled operations in a job shop scheduling problem: 1. Using the dispatcher.unscheduled_operations() method 2. Using the UnscheduledOperationsObserver class

We’ll solve multiple instances and measure the time taken to access unscheduled operations after each dispatching step.

Setup

First, let’s import the necessary modules and define our helper functions.

import time
from collections.abc import Callable
from job_shop_lib import JobShopInstance
from job_shop_lib.dispatching import Dispatcher, UnscheduledOperationsObserver
from job_shop_lib.dispatching.rules import DispatchingRuleSolver
from job_shop_lib.benchmarking import load_benchmark_instance


def solve_instances_and_measure_time(
    instances: list[JobShopInstance],
    access_unscheduled: Callable[[Dispatcher], None],
) -> float:
    total_time = 0
    for instance in instances:
        dispatcher = Dispatcher(instance)
        solver = DispatchingRuleSolver(dispatching_rule="random")

        start_time = time.perf_counter()
        while not dispatcher.schedule.is_complete():
            solver.step(dispatcher)
            access_unscheduled(dispatcher)
        end_time = time.perf_counter()

        total_time += end_time - start_time

    return total_time


# Load benchmark instances
instances = [load_benchmark_instance(f"ta{i:02d}") for i in range(1, 11)]

Method 1: Using dispatcher.unscheduled_operations()

Let’s first measure the time taken when using the dispatcher’s method directly.

def access_with_method(dispatcher: Dispatcher):
    _ = dispatcher.unscheduled_operations()


method_time = solve_instances_and_measure_time(instances, access_with_method)
print(f"Time taken using dispatcher method: {method_time:.4f} seconds")

Time taken using dispatcher method: 0.0174 seconds

Method 2: Using UnscheduledOperationsObserver

Now, let’s measure the time taken when using the UnscheduledOperationsObserver.

def access_with_observer(dispatcher: Dispatcher):
    observer = dispatcher.create_or_get_observer(UnscheduledOperationsObserver)
    _ = observer.unscheduled_operations


observer_time = solve_instances_and_measure_time(
    instances, access_with_observer
)
print(f"Time taken using observer: {observer_time:.4f} seconds")

Time taken using observer: 0.0134 seconds

Results Analysis

Let’s compare the results and calculate the speedup factor.

speedup = method_time / observer_time
print(f"Speedup factor: {speedup:.2f}x")

if speedup > 1:
    print(
        f"The observer method is {speedup:.2f} times faster than the dispatcher method."
    )
else:
    print(
        f"The dispatcher method is {1/speedup:.2f} times faster than the observer method."
    )

Speedup factor: 1.30x
The observer method is 1.30 times faster than the dispatcher method.

from typing import Any


def benchmark_unscheduled_operations(
    instances: list[JobShopInstance],
    dispatching_rule: str = "random",
) -> dict[str, Any]:
    """
    Benchmark the performance of dispatcher method vs observer method for
    accessing unscheduled operations.

    This function solves each instance twice, once using the dispatcher's
    unscheduled_operations method and once using the UnscheduledOperationsObserver.
    It measures the time taken to access unscheduled operations after each
    dispatching step.

    Args:
        instances: A list of JobShopInstance objects to benchmark.
        dispatching_rule: The dispatching rule to use for solving instances.

    Returns:
        A dictionary containing:
        - 'dispatcher_times': List of times for dispatcher method per instance.
        - 'observer_times': List of times for observer method per instance.
        - 'total_dispatcher_time': Total time for all instances using dispatcher method.
        - 'total_observer_time': Total time for all instances using observer method.
        - 'speedup': Overall speedup factor (dispatcher_time / observer_time).
        - 'instance_speedups': List of speedup factors per instance.
    """
    dispatcher_times = []
    observer_times = []
    instance_speedups = []
    instance_names = [instance.name for instance in instances]

    for instance in instances:
        # Measure time using dispatcher method
        dispatcher = Dispatcher(instance)
        solver = DispatchingRuleSolver(dispatching_rule=dispatching_rule)

        start_time = time.perf_counter()
        while not dispatcher.schedule.is_complete():
            solver.step(dispatcher)
            _ = dispatcher.unscheduled_operations()
        end_time = time.perf_counter()

        dispatcher_time = end_time - start_time
        dispatcher_times.append(dispatcher_time)

        # Measure time using observer method
        dispatcher = Dispatcher(instance)
        solver = DispatchingRuleSolver(dispatching_rule=dispatching_rule)
        observer = UnscheduledOperationsObserver(dispatcher)

        start_time = time.perf_counter()
        while not dispatcher.schedule.is_complete():
            solver.step(dispatcher)
            _ = observer.unscheduled_operations
        end_time = time.perf_counter()

        observer_time = end_time - start_time
        observer_times.append(observer_time)

        # Calculate speedup for this instance
        speedup = dispatcher_time / observer_time
        instance_speedups.append(speedup)

    return {
        "instance_names": instance_names,
        "dispatcher_times": dispatcher_times,
        "observer_times": observer_times,
        "instance_speedups": instance_speedups,
    }

from job_shop_lib.benchmarking import load_benchmark_instance
import pandas as pd

instances = [load_benchmark_instance(f"ta{i:02d}") for i in range(1, 81)]

results = benchmark_unscheduled_operations(instances)

df = pd.DataFrame(results)
df

	instance_names	dispatcher_times	observer_times	instance_speedups
0	ta01	0.001951	0.001197	1.630117
1	ta02	0.001707	0.001131	1.509800
2	ta03	0.001790	0.001097	1.631349
3	ta04	0.001682	0.001337	1.257420
4	ta05	0.002723	0.001243	2.191114
...	...	...	...	...
75	ta76	0.051289	0.024095	2.128598
76	ta77	0.055145	0.024647	2.237377
77	ta78	0.052566	0.025209	2.085196
78	ta79	0.052468	0.025190	2.082875
79	ta80	0.053840	0.024191	2.225636

80 rows × 4 columns

df.dispatcher_times.sum(), df.observer_times.sum(), df.instance_speedups.mean()

(1.0698642580073283, 0.5022928130001674, 2.1548888368714754)

Conclusion

The results show that the :class:UnscheduledOperationObserver is significantly faster. This is because the observer updates a list of unscheduled operations at each dispatching step, while the dispatcher method creates a new list of unscheduled operations each time it is called. The difference between the first, in which the dispatcher method is faster, and the second, in which the observer method is faster, is due to the use of the :meth:~job_shop_lib.dispatching.Dispatcher.create_or_get_observer method, which retrieves the observer if it already exists or creates a new one if it doesn’t. This retrieval process takes time, which is why the first method is faster in this case.