examples/notebook/jobshop_ft06_sat.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Copyright 2010-2017 Google\n",
    "# Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "#     http://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License.\n",
    "\n",
    "import collections\n",
    "from ortools.sat.python import cp_model\n",
    "from ortools.sat.python import visualization\n",
    "\n",
    "\n",
    "# Creates the solver.\n",
    "model = cp_model.CpModel()\n",
    "\n",
    "machines_count = 6\n",
    "jobs_count = 6\n",
    "all_machines = range(0, machines_count)\n",
    "all_jobs = range(0, jobs_count)\n",
    "\n",
    "durations = [[1, 3, 6, 7, 3, 6], [8, 5, 10, 10, 10, 4], [5, 4, 8, 9, 1, 7],\n",
    "             [5, 5, 5, 3, 8, 9], [9, 3, 5, 4, 3, 1], [3, 3, 9, 10, 4, 1]]\n",
    "\n",
    "machines = [[2, 0, 1, 3, 5, 4], [1, 2, 4, 5, 0, 3], [2, 3, 5, 0, 1, 4],\n",
    "            [1, 0, 2, 3, 4, 5], [2, 1, 4, 5, 0, 3], [1, 3, 5, 0, 4, 2]]\n",
    "\n",
    "# Computes horizon dynamically.\n",
    "horizon = sum([sum(durations[i]) for i in all_jobs])\n",
    "\n",
    "Task = collections.namedtuple('Task', 'start end interval')\n",
    "\n",
    "# Creates jobs.\n",
    "all_tasks = {}\n",
    "for i in all_jobs:\n",
    "  for j in all_machines:\n",
    "    start_var = model.NewIntVar(0, horizon, 'start_%i_%i' % (i, j))\n",
    "    duration = durations[i][j]\n",
    "    end_var = model.NewIntVar(0, horizon, 'end_%i_%i' % (i, j))\n",
    "    interval_var = model.NewIntervalVar(start_var, duration, end_var,\n",
    "                                        'interval_%i_%i' % (i, j))\n",
    "    all_tasks[(i, j)] = Task(\n",
    "        start=start_var, end=end_var, interval=interval_var)\n",
    "\n",
    "# Create disjuctive constraints.\n",
    "machine_to_jobs = {}\n",
    "for i in all_machines:\n",
    "  machines_jobs = []\n",
    "  for j in all_jobs:\n",
    "    for k in all_machines:\n",
    "      if machines[j][k] == i:\n",
    "        machines_jobs.append(all_tasks[(j, k)].interval)\n",
    "  machine_to_jobs[i] = machines_jobs\n",
    "  model.AddNoOverlap(machines_jobs)\n",
    "\n",
    "# Precedences inside a job.\n",
    "for i in all_jobs:\n",
    "  for j in range(0, machines_count - 1):\n",
    "    model.Add(all_tasks[(i, j + 1)].start >= all_tasks[(i, j)].end)\n",
    "\n",
    "# Makespan objective.\n",
    "obj_var = model.NewIntVar(0, horizon, 'makespan')\n",
    "model.AddMaxEquality(\n",
    "    obj_var, [all_tasks[(i, machines_count - 1)].end for i in all_jobs])\n",
    "model.Minimize(obj_var)\n",
    "\n",
    "# Solve model.\n",
    "solver = cp_model.CpSolver()\n",
    "response = solver.Solve(model)\n",
    "\n",
    "# Output solution.\n",
    "if visualization.RunFromIPython():\n",
    "  starts = [[solver.Value(all_tasks[(i, j)][0])\n",
    "             for j in all_machines]\n",
    "            for i in all_jobs]\n",
    "  visualization.DisplayJobshop(starts, durations, machines, 'FT06')\n",
    "else:\n",
    "  print('Optimal makespan: %i' % solver.ObjectiveValue())\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}