{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8e037610",
   "metadata": {},
   "source": [
    "# SALBP-1\n",
    "\n",
    "In a simple assembly line balancing problem to minimize the number of stations (SALBP-1), we are given the set of tasks $N = \\{ 0, ..., n - 1 \\}$.\n",
    "We want to schedule tasks in a totally ordered set of stations.\n",
    "Predecessors $P_i \\subseteq N$ of task $i$ must be scheduled in the same station as $i$ or earlier.\n",
    "Each task $i \\in N$ has processing time $t_i$, and the sum of processing times of tasks scheduled in the same station must be less than or equal to the cycle time $c$.\n",
    "The objective is to minimize the number of stations to schedule all tasks.\n",
    "\n",
    "## DP Formulation\n",
    "\n",
    "Consider using stations one by one and scheduling tasks one by one.\n",
    "Let $U$ be the set of unscheduled tasks, and $r$ be the idle time in the current station.\n",
    "To schedule task $i \\in U$ in the current station, $P_i \\cap U = \\emptyset$ and $t_i \\leq r$ must hold.\n",
    "After scheduling $i$, $U$ becomes $U \\setminus \\{ i \\}$ and $r$ becomes $r - t_i$.\n",
    "Therefore, we have the following DP model:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "    \\text{compute } & V(N, 0) \\\\\n",
    "    & V(U, r) = \\begin{cases}\n",
    "         \\min\\limits_{i \\in U : P_i \\cap U = \\emptyset \\land t_i \\leq r} V(U \\setminus \\{ i \\}, r - t_i) & \\text{if } \\exists i \\in U, P_i \\cap U = \\emptyset \\land t_i \\leq r \\\\\n",
    "         1 + V(U, c) & \\text{if } \\forall i \\in U, P_i \\cap U \\neq \\emptyset \\lor t_i > r \\\\\n",
    "         0 & \\text{if } U = \\emptyset.\n",
    "    \\end{cases}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "If two states $(U, r)$ and $(U, r')$ have the same set of unscheduled tasks and $r \\geq r'$, $(U, r)$ leads to a better solution. Therefore,\n",
    "\n",
    "$$\n",
    "    V(U, r) \\leq V(U, r') \\text{ if } r \\geq r'.\n",
    "$$\n",
    "\n",
    "If we ignore the predecessors and the fact that a task cannot be divided for multiple stations, we get the following lower bound:\n",
    "\n",
    "$$\n",
    "    V(U, r) \\geq \\left\\lceil \\frac{\\sum_{i \\in U} t_i - r}{c} \\right\\rceil.\n",
    "$$\n",
    "\n",
    "Consider only tasks $i$ with $t_i \\geq \\frac{c}{2}$ and ignore predecessors.\n",
    "Each station contains at most one of tasks $i$ with $t_i > \\frac{c}{2}$.\n",
    "Similarly, each station contains at most two tasks with $t_i = \\frac{c}{2}$, and such tasks are not scheduled in the same station having tasks with $t_i > \\frac{c}{2}$.\n",
    "If $r \\geq \\frac{c}{2}$, we can possibly use the current station to schedule the tasks.\n",
    "Therefore,\n",
    "\n",
    "$$\n",
    "    V(U, r) \\geq \\begin{cases}\n",
    "        \\sum\\limits_{ i \\in U : t_i > \\frac{c}{2} } 1 + \\left\\lceil \\sum\\limits_{i \\in U : t_i = \\frac{c}{2}} \\frac{1}{2} \\right\\rceil & \\text{if } r < \\frac{c}{2} \\\\\n",
    "        \\sum\\limits_{ i \\in U : t_i > \\frac{c}{2} } 1 + \\left\\lceil \\sum\\limits_{i \\in U : t_i = \\frac{c}{2}} \\frac{1}{2} \\right\\rceil - 1 & \\text{if } r \\geq \\frac{c}{2}.\n",
    "    \\end{cases}\n",
    "$$\n",
    "\n",
    "Similaly, if we consider only tasks $i$ with $t_i \\geq \\frac{c}{3}$, we get the following bound:\n",
    "\n",
    "$$\n",
    "    V(U, r) \\geq \\begin{cases}\n",
    "        \\left\\lceil \\sum\\limits_{ i \\in U : t_i > \\frac{2c}{3} } 1 + \\sum\\limits_{i \\in U : t_i = \\frac{2c}{3}} \\frac{2}{3} + \\sum\\limits_{i \\in U : t_i \\in (\\frac{c}{3}. \\frac{2c}{3})} \\frac{1}{2} + \\sum\\limits_{i \\in U : t_i = \\frac{c}{3}} \\frac{1}{3} \\right\\rceil & \\text{if } r < \\frac{c}{3} \\\\\n",
    "        \\left\\lceil \\sum\\limits_{ i \\in U : t_i > \\frac{2c}{3} } 1 + \\sum\\limits_{i \\in U : t_i = \\frac{2c}{3}} \\frac{2}{3} + \\sum\\limits_{i \\in U : t_i \\in (\\frac{c}{3}. \\frac{2c}{3})} \\frac{1}{2} + \\sum\\limits_{i \\in U : t_i = \\frac{c}{3}} \\frac{1}{3} \\right\\rceil - 1 & \\text{if } r \\geq \\frac{c}{3} \\\\\n",
    "    \\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80534624",
   "metadata": {},
   "source": [
    "## Install DIDPPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "07b4132e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: didppy in /home/kuro/tidel/code/didp-rs/didppy/.venv/lib/python3.10/site-packages (0.7.1)\r\n"
     ]
    }
   ],
   "source": [
    "!pip install didppy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "457d4597",
   "metadata": {},
   "source": [
    "## Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "2be75d7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of tasks\n",
    "n = 5\n",
    "# Cycle time\n",
    "c = 5\n",
    "# Processing times\n",
    "t = [2, 2, 1, 3, 2]\n",
    "# Predecessors\n",
    "p = [[], [], [], [0], [1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44dc9b66",
   "metadata": {},
   "source": [
    "## Preprocessing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4b1605e4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# The weight in the first term of the second bound.\n",
    "weight_2_1 = [1 if t[i] > c / 2 else 0 for i in range(n)]\n",
    "# The weight in the second term of the second bound.\n",
    "weight_2_2 = [1 / 2 if t[i] == c / 2 else 0 for i in range(n)]\n",
    "# The weight in the third bound (truncated to three decimal points).\n",
    "weight_3 = [\n",
    "    1.0\n",
    "    if t[i] > c * 2 / 3\n",
    "    else 2 / 3 // 0.001 * 1000\n",
    "    if t[i] == c * 2 / 3\n",
    "    else 0.5\n",
    "    if t[i] > c / 3\n",
    "    else 1 / 3 // 0.001 * 1000\n",
    "    if t[i] == c / 3\n",
    "    else 0.0\n",
    "    for i in range(n)\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c29a3733",
   "metadata": {},
   "source": [
    "## Modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "40abd606",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "import didppy as dp\n",
    "\n",
    "model = dp.Model()\n",
    "\n",
    "task = model.add_object_type(number=n)\n",
    "\n",
    "# U\n",
    "unscheduled = model.add_set_var(object_type=task, target=list(range(n)))\n",
    "# r\n",
    "idle_time = model.add_int_resource_var(target=0, less_is_better=False)\n",
    "\n",
    "processing_time = model.add_int_table(t)\n",
    "predecessors = model.add_set_table(p, object_type=task)\n",
    "\n",
    "for i in range(n):\n",
    "    schedule = dp.Transition(\n",
    "        name=\"schedule {}\".format(i),\n",
    "        cost=dp.IntExpr.state_cost(),\n",
    "        effects=[\n",
    "            (unscheduled, unscheduled.remove(i)),\n",
    "            (idle_time, idle_time - processing_time[i]),\n",
    "        ],\n",
    "        preconditions=[\n",
    "            unscheduled.contains(i),\n",
    "            unscheduled.isdisjoint(predecessors[i]),\n",
    "            processing_time[i] <= idle_time,\n",
    "        ],\n",
    "    )\n",
    "    model.add_transition(schedule)\n",
    "\n",
    "open_new = dp.Transition(\n",
    "    name=\"open a new station\",\n",
    "    cost=1 + dp.IntExpr.state_cost(),\n",
    "    effects=[(idle_time, c)],\n",
    "    preconditions=[\n",
    "        ~unscheduled.contains(i)\n",
    "        | ~unscheduled.isdisjoint(predecessors[i])\n",
    "        | (processing_time[i] > idle_time)\n",
    "        for i in range(n)\n",
    "    ],\n",
    ")\n",
    "model.add_transition(open_new, forced=True)\n",
    "\n",
    "model.add_base_case([unscheduled.is_empty()])\n",
    "\n",
    "model.add_dual_bound(\n",
    "    math.ceil((processing_time[unscheduled] - idle_time) / c)\n",
    ")\n",
    "\n",
    "weight_2_1_table = model.add_int_table(weight_2_1)\n",
    "weight_2_2_table = model.add_float_table(weight_2_2)\n",
    "model.add_dual_bound(\n",
    "    weight_2_1_table[unscheduled]\n",
    "    + math.ceil(weight_2_2_table[unscheduled])\n",
    "    - (idle_time >= c / 2).if_then_else(1, 0)\n",
    ")\n",
    "\n",
    "weight_3_table = model.add_float_table(weight_3)\n",
    "model.add_dual_bound(\n",
    "    math.ceil(weight_3_table[unscheduled])\n",
    "    - (idle_time >= c / 3).if_then_else(1, 0)\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e430270",
   "metadata": {},
   "source": [
    "## Solving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ea0484bf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transitions to apply:\n",
      "\n",
      "open a new station\n",
      "schedule 0\n",
      "schedule 1\n",
      "schedule 2\n",
      "open a new station\n",
      "schedule 3\n",
      "schedule 4\n",
      "\n",
      "Cost: 2\n"
     ]
    }
   ],
   "source": [
    "solver = dp.CABS(model, quiet=True)\n",
    "solution = solver.search()\n",
    "\n",
    "print(\"Transitions to apply:\")\n",
    "print(\"\")\n",
    "\n",
    "for t in solution.transitions:\n",
    "    print(t.name)\n",
    "\n",
    "print(\"\")\n",
    "print(\"Cost: {}\".format(solution.cost))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": ".venv"
  },
  "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}