{ "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", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
instance_namesdispatcher_timesobserver_timesinstance_speedups
0ta010.0019510.0011971.630117
1ta020.0017070.0011311.509800
2ta030.0017900.0010971.631349
3ta040.0016820.0013371.257420
4ta050.0027230.0012432.191114
...............
75ta760.0512890.0240952.128598
76ta770.0551450.0246472.237377
77ta780.0525660.0252092.085196
78ta790.0524680.0251902.082875
79ta800.0538400.0241912.225636
\n", "

80 rows × 4 columns

\n", "
" ], "text/plain": [ " instance_names dispatcher_times observer_times instance_speedups\n", "0 ta01 0.001951 0.001197 1.630117\n", "1 ta02 0.001707 0.001131 1.509800\n", "2 ta03 0.001790 0.001097 1.631349\n", "3 ta04 0.001682 0.001337 1.257420\n", "4 ta05 0.002723 0.001243 2.191114\n", ".. ... ... ... ...\n", "75 ta76 0.051289 0.024095 2.128598\n", "76 ta77 0.055145 0.024647 2.237377\n", "77 ta78 0.052566 0.025209 2.085196\n", "78 ta79 0.052468 0.025190 2.082875\n", "79 ta80 0.053840 0.024191 2.225636\n", "\n", "[80 rows x 4 columns]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from job_shop_lib.benchmarking import load_benchmark_instance\n", "import pandas as pd\n", "\n", "instances = [load_benchmark_instance(f\"ta{i:02d}\") for i in range(1, 81)]\n", "\n", "results = benchmark_unscheduled_operations(instances)\n", "\n", "df = pd.DataFrame(results)\n", "df" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1.0698642580073283, 0.5022928130001674, 2.1548888368714754)" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df.dispatcher_times.sum(), df.observer_times.sum(), df.instance_speedups.mean()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Conclusion\n", "\n", "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." ] } ], "metadata": { "kernelspec": { "display_name": "job-shop-lib-gOF0HMZJ-py3.11", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.8" } }, "nbformat": 4, "nbformat_minor": 2 }