{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d24e8248",
   "metadata": {},
   "source": [
    "# Single Machine Total Weighted Tardiness with Precedence\n",
    "\n",
    "In the single machine total weighted tardiness with precedence ($1|\\text{prec}|\\sum w_i T_i$), we are given a set of jobs $N = \\{ 0, ..., n-1 \\}$.\n",
    "Each job $i \\in N$ has the processing time $p_i$, the due date $d_i$, and the weight $w_i$.\n",
    "We schedule all jobs sequentially in a single machine.\n",
    "To schedule job $i$, all of its predecessors $P_i \\subseteq N$ must be scheduled before.\n",
    "When job $i$ completes at time $C_i$, its tardiness is $T_i = \\max\\{ C_i - d_i, 0 \\}$.\n",
    "We want to minimize the total weighted tardiness, $\\sum_{i \\in N} w_i T_i$.\n",
    "\n",
    "## DP Formulation\n",
    "\n",
    "Consider scheduling jobs one by one.\n",
    "Let $S$ be the set of already scheduled jobs.\n",
    "We can schedule job $i \\notin S$ if $P_i \\subseteq S$.\n",
    "If we schedule $i$ next, its completion time is $C_i = \\sum_{j \\in S} p_j + p_i$.\n",
    "Let $V(S)$ be the minimum total weighted tardiness to schedule all jobs in $N \\setminus S$.\n",
    "We have the following DP model:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "    \\text{compute } & V(\\emptyset) \\\\\n",
    "    & V(S) = \\begin{cases}\n",
    "        \\min\\limits_{i \\in N \\setminus S : P_i \\subseteq S} w_i \\max\\left\\{ \\sum\\limits_{j \\in S} p_j + p_i - d_i, 0 \\right\\} + V(S \\cup \\{ i \\}) & \\text{if } S \\neq N \\\\\n",
    "        0 & \\text{if } S = N\n",
    "    \\end{cases} \\\\\n",
    "    & V(S) \\geq 0.\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab530e9a",
   "metadata": {},
   "source": [
    "## Install DIDPPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ee3d8e3f",
   "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": "dc8347bb",
   "metadata": {},
   "source": [
    "## Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "fc65e222",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of jobs\n",
    "n = 5\n",
    "# Processing times\n",
    "p = [2, 3, 5, 1, 4]\n",
    "# Dead dates\n",
    "d = [1, 4, 7, 2, 5]\n",
    "# Weights\n",
    "w = [2, 1, 2, 3, 2]\n",
    "# Predecessors\n",
    "capital_p = [[2], [0, 3], [], [], [1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4da4efc9",
   "metadata": {},
   "source": [
    "## Modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "20e18fa3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import didppy as dp\n",
    "\n",
    "model = dp.Model()\n",
    "\n",
    "job = model.add_object_type(number=n)\n",
    "\n",
    "# S\n",
    "scheduled = model.add_set_var(object_type=job, target=[])\n",
    "\n",
    "# N\n",
    "all_jobs = model.create_set_const(object_type=job, value=list(range(n)))\n",
    "\n",
    "processing_time = model.add_int_table(p)\n",
    "predecessors = model.add_set_table(capital_p, object_type=job)\n",
    "\n",
    "for i in range(n):\n",
    "    tardiness = dp.max(0, processing_time[scheduled] + processing_time[i] - d[i])\n",
    "    schedule = dp.Transition(\n",
    "        name=\"schedule {}\".format(i),\n",
    "        cost=w[i] * tardiness + dp.IntExpr.state_cost(),\n",
    "        effects=[(scheduled, scheduled.add(i))],\n",
    "        preconditions=[~scheduled.contains(i), predecessors[i].issubset(scheduled)],\n",
    "    )\n",
    "    model.add_transition(schedule)\n",
    "    \n",
    "model.add_base_case([scheduled == all_jobs])\n",
    "\n",
    "model.add_dual_bound(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e55c446a",
   "metadata": {},
   "source": [
    "## Solving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "73dafcdd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transitions to apply:\n",
      "\n",
      "schedule 3\n",
      "schedule 2\n",
      "schedule 0\n",
      "schedule 1\n",
      "schedule 4\n",
      "\n",
      "Cost: 41\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
}