{ "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.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": [], "source": [ "NUMBER_OF_RUNS = 100" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Time taken using dispatcher method: 0.0134 seconds\n" ] } ], "source": [ "def access_with_method(dispatcher: Dispatcher):\n", " _ = dispatcher.unscheduled_operations()\n", "\n", "\n", "method_time = (\n", " sum(\n", " solve_instances_and_measure_time(instances, access_with_method)\n", " for _ in range(NUMBER_OF_RUNS)\n", " )\n", " / NUMBER_OF_RUNS\n", ")\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": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Time taken using observer: 0.0096 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 = (\n", " sum(\n", " solve_instances_and_measure_time(instances, access_with_observer)\n", " for _ in range(NUMBER_OF_RUNS)\n", " )\n", " / NUMBER_OF_RUNS\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": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Speedup factor: 1.39x\n", "The observer method is 1.39 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": 6, "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": 7, "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.0012410.0007781.595974
1ta020.0011940.0006961.716365
2ta030.0011760.0008231.428035
3ta040.0022440.0012881.742647
4ta050.0015540.0009711.599968
...............
75ta760.0405940.0212011.914774
76ta770.0406370.0186112.183487
77ta780.0396470.0191342.072027
78ta790.0396330.0180282.198378
79ta800.0403460.0235551.712866
\n", "

80 rows × 4 columns

\n", "
" ], "text/plain": [ " instance_names dispatcher_times observer_times instance_speedups\n", "0 ta01 0.001241 0.000778 1.595974\n", "1 ta02 0.001194 0.000696 1.716365\n", "2 ta03 0.001176 0.000823 1.428035\n", "3 ta04 0.002244 0.001288 1.742647\n", "4 ta05 0.001554 0.000971 1.599968\n", ".. ... ... ... ...\n", "75 ta76 0.040594 0.021201 1.914774\n", "76 ta77 0.040637 0.018611 2.183487\n", "77 ta78 0.039647 0.019134 2.072027\n", "78 ta79 0.039633 0.018028 2.198378\n", "79 ta80 0.040346 0.023555 1.712866\n", "\n", "[80 rows x 4 columns]" ] }, "execution_count": 7, "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": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0.8449087279923333, 0.3913600640034929, 2.2413732582217087)" ] }, "execution_count": 8, "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 `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 experiment and the second is due to the use of the `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 speedup difference is not as significant as in the second experiment." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] } ], "metadata": { "kernelspec": { "display_name": "job-shop-lib-gOF0HMZJ-py3.12", "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.12.3" } }, "nbformat": 4, "nbformat_minor": 2 }