examples/notebook/gate_scheduling_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",
    "\"\"\"Gate Scheduling problem.\n",
    "\n",
    "We have a set of jobs to perform (duration, width).\n",
    "We have two parallel machines that can perform this job.\n",
    "One machine can only perform one job at a time.\n",
    "At any point in time, the sum of the width of the two active jobs does not\n",
    "exceed a max_length.\n",
    "\n",
    "The objective is to minimize the max end time of all jobs.\n",
    "\"\"\"\n",
    "\n",
    "from ortools.sat.python import cp_model\n",
    "from ortools.sat.python import visualization\n",
    "\n",
    "\n",
    "model = cp_model.CpModel()\n",
    "\n",
    "jobs = [[3, 3], [2, 5], [1, 3], [3, 7], [7, 3], [2, 2], [2, 2], [5, 5],\n",
    "        [10, 2], [4, 3], [2, 6], [1, 2], [6, 8], [4, 5], [3, 7]]\n",
    "\n",
    "max_length = 10\n",
    "\n",
    "horizon = sum(t[0] for t in jobs)\n",
    "num_jobs = len(jobs)\n",
    "all_jobs = range(num_jobs)\n",
    "\n",
    "intervals = []\n",
    "intervals0 = []\n",
    "intervals1 = []\n",
    "performed = []\n",
    "starts = []\n",
    "ends = []\n",
    "demands = []\n",
    "\n",
    "for i in all_jobs:\n",
    "  # Create main interval.\n",
    "  start = model.NewIntVar(0, horizon, 'start_%i' % i)\n",
    "  duration = jobs[i][0]\n",
    "  end = model.NewIntVar(0, horizon, 'end_%i' % i)\n",
    "  interval = model.NewIntervalVar(start, duration, end, 'interval_%i' % i)\n",
    "  starts.append(start)\n",
    "  intervals.append(interval)\n",
    "  ends.append(end)\n",
    "  demands.append(jobs[i][1])\n",
    "\n",
    "  performed_on_m0 = model.NewBoolVar('perform_%i_on_m0' % i)\n",
    "  performed.append(performed_on_m0)\n",
    "\n",
    "  # Create an optional copy of interval to be executed on machine 0.\n",
    "  start0 = model.NewIntVar(0, horizon, 'start_%i_on_m0' % i)\n",
    "  end0 = model.NewIntVar(0, horizon,  'end_%i_on_m0' % i)\n",
    "  interval0 = model.NewOptionalIntervalVar(\n",
    "      start0, duration, end0, performed_on_m0, 'interval_%i_on_m0' % i)\n",
    "  intervals0.append(interval0)\n",
    "\n",
    "  # Create an optional copy of interval to be executed on machine 1.\n",
    "  start1 = model.NewIntVar(0, horizon, 'start_%i_on_m1' % i)\n",
    "  end1 = model.NewIntVar(0, horizon, 'end_%i_on_m1' % i)\n",
    "  interval1 = model.NewOptionalIntervalVar(start1, duration, end1,\n",
    "                                           performed_on_m0.Not(),\n",
    "                                           'interval_%i_on_m1' % i)\n",
    "  intervals1.append(interval1)\n",
    "\n",
    "  # We only propagate the constraint if the tasks is performed on the machine.\n",
    "  model.Add(start0 == start).OnlyEnforceIf(performed_on_m0)\n",
    "  model.Add(start1 == start).OnlyEnforceIf(performed_on_m0.Not())\n",
    "\n",
    "# Max Length constraint (modeled as a cumulative)\n",
    "model.AddCumulative(intervals, demands, max_length)\n",
    "\n",
    "# Choose which machine to perform the jobs on.\n",
    "model.AddNoOverlap(intervals0)\n",
    "model.AddNoOverlap(intervals1)\n",
    "\n",
    "# Objective variable.\n",
    "makespan = model.NewIntVar(0, horizon, 'makespan')\n",
    "model.AddMaxEquality(makespan, ends)\n",
    "model.Minimize(makespan)\n",
    "\n",
    "# Symmetry breaking.\n",
    "model.Add(performed[0] == 0)\n",
    "\n",
    "# Solve model.\n",
    "solver = cp_model.CpSolver()\n",
    "solver.Solve(model)\n",
    "\n",
    "# Output solution.\n",
    "if visualization.RunFromIPython():\n",
    "  output = visualization.SvgWrapper(solver.ObjectiveValue(), max_length, 40.0)\n",
    "  output.AddTitle('Makespan = %i' % solver.ObjectiveValue())\n",
    "  color_manager = visualization.ColorManager()\n",
    "  color_manager.SeedRandomColor(0)\n",
    "\n",
    "  for i in all_jobs:\n",
    "    performed_machine = 1 - solver.Value(performed[i])\n",
    "    start = solver.Value(starts[i])\n",
    "    dx = jobs[i][0]\n",
    "    dy = jobs[i][1]\n",
    "    sy = performed_machine * (max_length - dy)\n",
    "    output.AddRectangle(start, sy, dx, dy, color_manager.RandomColor(),\n",
    "                        'black', 'j%i' % i)\n",
    "\n",
    "  output.AddXScale()\n",
    "  output.AddYScale()\n",
    "  output.Display()\n",
    "else:\n",
    "  print('Solution')\n",
    "  print('  - makespan = %i' % solver.ObjectiveValue())\n",
    "  for i in all_jobs:\n",
    "    performed_machine = 1 - solver.Value(performed[i])\n",
    "    start = solver.Value(starts[i])\n",
    "    print('  - Job %i starts at %i on machine %i' % (i, start,\n",
    "                                                     performed_machine))\n",
    "  print('Statistics')\n",
    "  print('  - conflicts : %i' % solver.NumConflicts())\n",
    "  print('  - branches  : %i' % solver.NumBranches())\n",
    "  print('  - wall time : %f ms' % solver.WallTime())\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}