{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Comparing Performance: Dispatcher Method vs. Observer Method for Unscheduled Operations\n", "\n", "In this tutorial, we'll compare the performance of two methods for accessing unscheduled operations in a job shop scheduling problem:\n", "1. Using the `dispatcher.unscheduled_operations()` method\n", "2. Using the `UnscheduledOperationsObserver` class\n", "\n", "We'll solve multiple instances and measure the time taken to access unscheduled operations after each dispatching step.\n", "\n", "## Setup\n", "\n", "First, let's import the necessary modules and define our helper functions.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import time\n", "from collections.abc import Callable\n", "from job_shop_lib import JobShopInstance\n", "from job_shop_lib.dispatching import Dispatcher, UnscheduledOperationsObserver\n", "from job_shop_lib.dispatching.rules import DispatchingRuleSolver\n", "from job_shop_lib.benchmarking import load_benchmark_instance\n", "\n", "\n", "def solve_instances_and_measure_time(\n", " instances: list[JobShopInstance],\n", " access_unscheduled: Callable[[Dispatcher], None],\n", ") -> float:\n", " total_time = 0\n", " for instance in instances:\n", " dispatcher = Dispatcher(instance)\n", " solver = DispatchingRuleSolver(dispatching_rule=\"random\")\n", "\n", " start_time = time.perf_counter()\n", " while not dispatcher.schedule.is_complete():\n", " solver.step(dispatcher)\n", " access_unscheduled(dispatcher)\n", " end_time = time.perf_counter()\n", "\n", " total_time += end_time - start_time\n", "\n", " return total_time\n", "\n", "\n", "# Load benchmark instances\n", "instances = [load_benchmark_instance(f\"ta{i:02d}\") for i in range(1, 11)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Method 1: Using dispatcher.unscheduled_operations()\n", "\n", "Let's first measure the time taken when using the dispatcher's method directly." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Time taken using dispatcher method: 0.0174 seconds\n" ] } ], "source": [ "def access_with_method(dispatcher: Dispatcher):\n", " _ = dispatcher.unscheduled_operations()\n", "\n", "\n", "method_time = solve_instances_and_measure_time(instances, access_with_method)\n", "print(f\"Time taken using dispatcher method: {method_time:.4f} seconds\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Method 2: Using UnscheduledOperationsObserver\n", "\n", "Now, let's measure the time taken when using the UnscheduledOperationsObserver." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Time taken using observer: 0.0134 seconds\n" ] } ], "source": [ "def access_with_observer(dispatcher: Dispatcher):\n", " observer = dispatcher.create_or_get_observer(UnscheduledOperationsObserver)\n", " _ = observer.unscheduled_operations\n", "\n", "\n", "observer_time = solve_instances_and_measure_time(\n", " instances, access_with_observer\n", ")\n", "print(f\"Time taken using observer: {observer_time:.4f} seconds\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Results Analysis\n", "\n", "Let's compare the results and calculate the speedup factor." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Speedup factor: 1.30x\n", "The observer method is 1.30 times faster than the dispatcher method.\n" ] } ], "source": [ "speedup = method_time / observer_time\n", "print(f\"Speedup factor: {speedup:.2f}x\")\n", "\n", "if speedup > 1:\n", " print(\n", " f\"The observer method is {speedup:.2f} times faster than the dispatcher method.\"\n", " )\n", "else:\n", " print(\n", " f\"The dispatcher method is {1/speedup:.2f} times faster than the observer method.\"\n", " )" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "from typing import Any\n", "\n", "\n", "def benchmark_unscheduled_operations(\n", " instances: list[JobShopInstance],\n", " dispatching_rule: str = \"random\",\n", ") -> dict[str, Any]:\n", " \"\"\"\n", " Benchmark the performance of dispatcher method vs observer method for\n", " accessing unscheduled operations.\n", "\n", " This function solves each instance twice, once using the dispatcher's\n", " unscheduled_operations method and once using the UnscheduledOperationsObserver.\n", " It measures the time taken to access unscheduled operations after each\n", " dispatching step.\n", "\n", " Args:\n", " instances: A list of JobShopInstance objects to benchmark.\n", " dispatching_rule: The dispatching rule to use for solving instances.\n", "\n", " Returns:\n", " A dictionary containing:\n", " - 'dispatcher_times': List of times for dispatcher method per instance.\n", " - 'observer_times': List of times for observer method per instance.\n", " - 'total_dispatcher_time': Total time for all instances using dispatcher method.\n", " - 'total_observer_time': Total time for all instances using observer method.\n", " - 'speedup': Overall speedup factor (dispatcher_time / observer_time).\n", " - 'instance_speedups': List of speedup factors per instance.\n", " \"\"\"\n", " dispatcher_times = []\n", " observer_times = []\n", " instance_speedups = []\n", " instance_names = [instance.name for instance in instances]\n", "\n", " for instance in instances:\n", " # Measure time using dispatcher method\n", " dispatcher = Dispatcher(instance)\n", " solver = DispatchingRuleSolver(dispatching_rule=dispatching_rule)\n", "\n", " start_time = time.perf_counter()\n", " while not dispatcher.schedule.is_complete():\n", " solver.step(dispatcher)\n", " _ = dispatcher.unscheduled_operations()\n", " end_time = time.perf_counter()\n", "\n", " dispatcher_time = end_time - start_time\n", " dispatcher_times.append(dispatcher_time)\n", "\n", " # Measure time using observer method\n", " dispatcher = Dispatcher(instance)\n", " solver = DispatchingRuleSolver(dispatching_rule=dispatching_rule)\n", " observer = UnscheduledOperationsObserver(dispatcher)\n", "\n", " start_time = time.perf_counter()\n", " while not dispatcher.schedule.is_complete():\n", " solver.step(dispatcher)\n", " _ = observer.unscheduled_operations\n", " end_time = time.perf_counter()\n", "\n", " observer_time = end_time - start_time\n", " observer_times.append(observer_time)\n", "\n", " # Calculate speedup for this instance\n", " speedup = dispatcher_time / observer_time\n", " instance_speedups.append(speedup)\n", "\n", " return {\n", " \"instance_names\": instance_names,\n", " \"dispatcher_times\": dispatcher_times,\n", " \"observer_times\": observer_times,\n", " \"instance_speedups\": instance_speedups,\n", " }" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", " | instance_names | \n", "dispatcher_times | \n", "observer_times | \n", "instance_speedups | \n", "
---|---|---|---|---|
0 | \n", "ta01 | \n", "0.001951 | \n", "0.001197 | \n", "1.630117 | \n", "
1 | \n", "ta02 | \n", "0.001707 | \n", "0.001131 | \n", "1.509800 | \n", "
2 | \n", "ta03 | \n", "0.001790 | \n", "0.001097 | \n", "1.631349 | \n", "
3 | \n", "ta04 | \n", "0.001682 | \n", "0.001337 | \n", "1.257420 | \n", "
4 | \n", "ta05 | \n", "0.002723 | \n", "0.001243 | \n", "2.191114 | \n", "
... | \n", "... | \n", "... | \n", "... | \n", "... | \n", "
75 | \n", "ta76 | \n", "0.051289 | \n", "0.024095 | \n", "2.128598 | \n", "
76 | \n", "ta77 | \n", "0.055145 | \n", "0.024647 | \n", "2.237377 | \n", "
77 | \n", "ta78 | \n", "0.052566 | \n", "0.025209 | \n", "2.085196 | \n", "
78 | \n", "ta79 | \n", "0.052468 | \n", "0.025190 | \n", "2.082875 | \n", "
79 | \n", "ta80 | \n", "0.053840 | \n", "0.024191 | \n", "2.225636 | \n", "
80 rows × 4 columns
\n", "