{ "cells": [ { "cell_type": "markdown", "id": "30015725", "metadata": {}, "source": [ "# Simulated Annealing for the Job Shop Scheduling Problem\n", "\n", "Simulated annealing is a metaheuristic optimization technique inspired by the process of annealing in metallurgy. In the context of the JSSP, it's used to find a schedule that minimizes a certain objective, typically the makespan (the total time required to complete all jobs).\n", "\n", "The process can be summarized as follows:\n", "\n", "1. **Start with an initial solution:** We begin with a valid, but likely suboptimal, schedule. This initial solution can be generated using a simple heuristic, like a dispatching rule.\n", "2. **Define an \"energy\" function:** In our case, the energy of a schedule is its makespan, plus penalties for any violated constraints (like deadlines). A lower energy means a better solution.\n", "3. **Iteratively explore neighbors:** The algorithm then iteratively explores \"neighboring\" solutions. A neighbor is a new schedule created by making a small change to the current one, for example, by swapping the order of two operations on a single machine.\n", "4. **Accept or reject new solutions:**\n", " * If the neighbor solution has a lower energy (is better), it is always accepted as the new current solution.\n", " * If the neighbor solution has a higher energy (is worse), it might still be accepted with a certain probability. This probability is higher at the beginning (when the \"temperature\" is high) and decreases over time. This allows the algorithm to escape local optima and explore a wider range of solutions.\n", "5. **Cooling down:** The \"temperature\" gradually decreases, reducing the probability of accepting worse solutions. The process stops when the system has \"cooled down\" (the temperature is low) or after a certain number of iterations.\n", "\n", "## Core Components\n", "\n", "The implementation is structured into a few key components:\n", "\n", " * **`SimulatedAnnealingSolver`:** This is the main high-level solver class that you will interact with. It wraps the core annealing logic and provides a simple `solve` method.\n", " * **`JobShopAnnealer`:** This is a helper class that inherits from the `simanneal` library's `Annealer` class. It implements the core simulated annealing logic, including the `move` and `energy` functions.\n", " * **Neighbor Generators:** These are functions that define how to create a \"neighbor\" schedule from a current one.\n", " * **Objective Functions:** The `energy` function calculates the objective value of a schedule, which is typically the makespan plus any penalties for constraint violations.\n", "\n", "## The `SimulatedAnnealingSolver`\n", "\n", "This is the main entry point for using the solver. When you create an instance of this class, you can configure various parameters of the annealing process:\n", "\n", " * `initial_temperature` (`Tmax`): The starting temperature. A higher value increases the initial probability of accepting worse solutions.\n", " * `ending_temperature` (`Tmin`): The final temperature. The algorithm stops when it approaches this temperature.\n", " * `steps`: The total number of iterations to run.\n", " * `neighbor_generator`: The function used to generate neighboring solutions. The default is `swap_in_critical_path`.\n", " * `seed`: A random seed for reproducibility.\n", "\n", "## Neighbor Generation Strategies\n", "\n", "A key part of the simulated annealing process is how you explore the solution space by moving from one solution to a \"neighbor\". This implementation provides three different neighbor generation strategies in `_neighbor_generators.py`:\n", "\n", "1. **`swap_adjacent_operations`:** This function randomly selects a machine and swaps two adjacent operations in its sequence. This is a very localized search.\n", "\n", "2. **`swap_random_operations`:** This function randomly selects a machine and swaps two *random* operations in its sequence. This allows for larger jumps in the solution space compared to adjacent swaps.\n", "\n", "3. **`swap_in_critical_path` (Default):** This is the most sophisticated of the three. It identifies the critical path of the current schedule (the sequence of operations that determines the makespan) and looks for consecutive operations on that path that are on the same machine. It then swaps one of these pairs. The idea is that modifying the critical path is the most direct way to try to reduce the makespan. If no such pair exists, it falls back to a standard adjacent swap.\n", "\n", "## The Objective Function\n", "\n", "The objective function is what the simulated annealing algorithm tries to minimize. In the context of job shop scheduling, this is typically the makespan (the total time to complete all jobs) plus any penalties for violating constraints (like deadlines).\n", "\n", "## Examples\n", "\n", "Here are some examples of how to use the solver.\n", "\n", "### Basic Usage\n", "\n", "This example shows how to solve a benchmark instance (\"ft06\") with a specific seed to get a reproducible result." ] }, { "cell_type": "code", "execution_count": 1, "id": "221594d9", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ " Temperature Energy Accept Improve Elapsed Remaining\n", " 2.50000 60.00 70.00% 20.00% 0:00:00 0:00:00" ] }, { "name": "stdout", "output_type": "stream", "text": [ "The makespan found for ft06 is: 55\n" ] } ], "source": [ "from job_shop_lib.benchmarking import load_benchmark_instance\n", "from job_shop_lib.metaheuristics import SimulatedAnnealingSolver\n", "\n", "\n", "ft06_instance = load_benchmark_instance(\"ft06\")\n", "\n", "solver = SimulatedAnnealingSolver(\n", " seed=42, # Seed for reproducibility\n", " initial_temperature=10, # Low temperature --> more greedy search\n", " steps=1000, # The number of schedules to try before stopping\n", " updates=100, # How often the display table is updated\n", ")\n", "\n", "schedule = solver.solve(ft06_instance)\n", "makespan = schedule.makespan()\n", "print(f\"The makespan found for ft06 is: {makespan}\")" ] }, { "cell_type": "markdown", "id": "f7e6ca60", "metadata": {}, "source": [ "### Using a Different Neighbor Generator\n", "\n", "Although it's not recommended, you can easily plug in a different neighbor generation strategy by passing it to the `SimulatedAnnealingSolver`'s constructor. Here's how to use `swap_adjacent_operations`:\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "3ad372ab", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ " Temperature Energy Accept Improve Elapsed Remaining\n", " 2.50000 67.00 100.00% 20.00% 0:00:03 0:00:00" ] }, { "name": "stdout", "output_type": "stream", "text": [ "The makespan for ft06 with adjacent swaps is: 61\n" ] } ], "source": [ "from job_shop_lib.metaheuristics import swap_adjacent_operations\n", "\n", "# This time, we specify a different neighbor generator\n", "solver_adj_swap = SimulatedAnnealingSolver(\n", " seed=42,\n", " initial_temperature=10,\n", " steps=1000,\n", " updates=100,\n", " neighbor_generator=swap_adjacent_operations,\n", ")\n", "\n", "schedule_adj_swap = solver_adj_swap.solve(ft06_instance)\n", "makespan_adj_swap = schedule_adj_swap.makespan()\n", "print(f\"The makespan for ft06 with adjacent swaps is: {makespan_adj_swap}\")" ] }, { "cell_type": "markdown", "id": "304e13c0", "metadata": {}, "source": [ "Similarly, you can use `swap_random_operations`:" ] }, { "cell_type": "code", "execution_count": 3, "id": "5a120c76", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ " Temperature Energy Accept Improve Elapsed Remaining\n", " 2.50000 70.00 50.00% 0.00% 0:00:09 0:00:00" ] }, { "name": "stdout", "output_type": "stream", "text": [ "The makespan for ft06 with random swaps is: 61\n" ] } ], "source": [ "from job_shop_lib.metaheuristics import swap_random_operations\n", "\n", "solver_rand_swap = SimulatedAnnealingSolver(\n", " seed=42,\n", " initial_temperature=10,\n", " steps=1000,\n", " updates=100,\n", " neighbor_generator=swap_random_operations,\n", ")\n", "schedule_rand_swap = solver_rand_swap.solve(ft06_instance)\n", "makespan_rand_swap = schedule_rand_swap.makespan()\n", "print(f\"The makespan for ft06 with random swaps is: {makespan_rand_swap}\")" ] }, { "cell_type": "markdown", "id": "6b4bb5a8", "metadata": {}, "source": [ "In both cases, the algorithm doesn't find a better solution than the starting one (found with the Most Work Remaining dispatching rule). Additionally, while using these alternative neighbor generators, you may notice that each step takes longer to compute. This happens because swapping operations randomly often results in unfeasible schedules. If the schedule is invalid, the neighbor generator will try again until it finds a valid neighbor.\n", "\n", "We allow the possibility of customizing the neighbor generation strategy because for schedules with deadlines or due dates, the default `swap_in_critical_path` may not always yield the best results. In such cases, creating a custom neighbor generator that swaps operations that violate deadlines can be beneficial." ] }, { "cell_type": "markdown", "id": "792f8c94", "metadata": {}, "source": [ "### Handling Deadlines\n", "\n", "The solver can handle constraints like deadlines. The `energy` function will add a large penalty for any schedule where an operation finishes after its deadline. This guides the search towards solutions that respect the deadlines. You can specify how to penalize these violations with the `due_date_penalty_factor` and the `deadline_penalty_factor` parameters when creating the `SimulatedAnnealingSolver`." ] }, { "cell_type": "code", "execution_count": null, "id": "91375a47", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ " Temperature Energy Accept Improve Elapsed Remaining\n", " 2.50000 60.00 70.00% 20.00% 0:00:00 0:00:00" ] }, { "name": "stdout", "output_type": "stream", "text": [ "The makespan found for ft06 is: 55\n" ] } ], "source": [ "from job_shop_lib.metaheuristics import get_makespan_with_penalties_objective\n", "\n", "\n", "solver = SimulatedAnnealingSolver(\n", " seed=42,\n", " initial_temperature=10,\n", " steps=1000,\n", " updates=100,\n", " objective_function=get_makespan_with_penalties_objective(\n", " deadline_penalty_factor=10_000, # We can tune these factors here\n", " due_date_penalty_factor=100,\n", " ), # Since there are no extra constraints in ft06, this returns the makespan\n", ")\n", "\n", "# Solve the problem\n", "schedule = solver.solve(ft06_instance)\n", "\n", "makespan = schedule.makespan()\n", "print(f\"The makespan found for ft06 is: {makespan}\")" ] } ], "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": 5 }