examples/notebook/flexible_job_shop_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",
    "from __future__ import print_function\n",
    "\n",
    "from collections import defaultdict\n",
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "class SolutionPrinter(cp_model.CpSolverSolutionCallback):\n",
    "  \"\"\"Print intermediate solutions.\"\"\"\n",
    "\n",
    "  def __init__(self):\n",
    "    cp_model.CpSolverSolutionCallback.__init__(self)\n",
    "    self.__solution_count = 0\n",
    "\n",
    "  def OnSolutionCallback(self):\n",
    "    print('Solution %i, time = %f s, objective = %i' %\n",
    "          (self.__solution_count, self.WallTime(), self.ObjectiveValue()))\n",
    "    self.__solution_count += 1\n",
    "\n",
    "\n",
    "# Data part.\n",
    "jobs = [[[(3, 0), (1, 1), (5, 2)], [(2, 0), (4, 1), (6, 2)], [(2, 0), (3, 1),\n",
    "                                                              (1, 2)]],\n",
    "        [[(2, 0), (3, 1), (4, 2)], [(1, 0), (5, 1), (4, 2)],\n",
    "         [(2, 0), (1, 1), (4, 2)]], [[(2, 0), (1, 1), (4, 2)],\n",
    "                                     [(2, 0), (3, 1), (4, 2)], [(3, 0), (1, 1),\n",
    "                                                                (5, 2)]]]\n",
    "\n",
    "num_jobs = len(jobs)\n",
    "all_jobs = range(num_jobs)\n",
    "\n",
    "num_machines = 3\n",
    "all_machines = range(num_machines)\n",
    "\n",
    "# Model the flexible jobshop problem.\n",
    "model = cp_model.CpModel()\n",
    "\n",
    "horizon = 0\n",
    "for job in jobs:\n",
    "  for task in job:\n",
    "    max_task_duration = 0\n",
    "    for alternative in task:\n",
    "      max_task_duration = max(max_task_duration, alternative[0])\n",
    "    horizon += max_task_duration\n",
    "\n",
    "print('Horizon = %i' % horizon)\n",
    "\n",
    "# Global storage of variables.\n",
    "intervals_per_resources = defaultdict(list)\n",
    "starts = {}  # indexed by (job_id, task_id).\n",
    "presences = {}  # indexed by (job_id, task_id, alt_id).\n",
    "job_ends = []\n",
    "\n",
    "# Scan the jobs and create the relevant variables and intervals.\n",
    "for job_id in all_jobs:\n",
    "  job = jobs[job_id]\n",
    "  num_tasks = len(job)\n",
    "  previous_end = None\n",
    "  for task_id in range(num_tasks):\n",
    "    task = job[task_id]\n",
    "\n",
    "    min_duration = task[0][0]\n",
    "    max_duration = task[0][0]\n",
    "\n",
    "    num_alternatives = len(task)\n",
    "    all_alternatives = range(num_alternatives)\n",
    "\n",
    "    for alt_id in range(1, num_alternatives):\n",
    "      alt_duration = task[alt_id][0]\n",
    "      min_duration = min(min_duration, alt_duration)\n",
    "      max_duration = max(max_duration, alt_duration)\n",
    "\n",
    "    # Create main interval for the task.\n",
    "    suffix_name = '_j%i_t%i' % (job_id, task_id)\n",
    "    start = model.NewIntVar(0, horizon, 'start' + suffix_name)\n",
    "    duration = model.NewIntVar(min_duration, max_duration,\n",
    "                               'duration' + suffix_name)\n",
    "    end = model.NewIntVar(0, horizon, 'end' + suffix_name)\n",
    "    interval = model.NewIntervalVar(start, duration, end,\n",
    "                                    'interval' + suffix_name)\n",
    "\n",
    "    # Store the start for the solution.\n",
    "    starts[(job_id, task_id)] = start\n",
    "\n",
    "    # Add precedence with previous task in the same job.\n",
    "    if previous_end:\n",
    "      model.Add(start >= previous_end)\n",
    "    previous_end = end\n",
    "\n",
    "    # Create alternative intervals.\n",
    "    if num_alternatives > 1:\n",
    "      l_presences = []\n",
    "      for alt_id in all_alternatives:\n",
    "        alt_suffix = '_j%i_t%i_a%i' % (job_id, task_id, alt_id)\n",
    "        l_presence = model.NewBoolVar('presence' + alt_suffix)\n",
    "        l_start = model.NewIntVar(0, horizon, 'start' + alt_suffix)\n",
    "        l_duration = task[alt_id][0]\n",
    "        l_end = model.NewIntVar(0, horizon, 'end' + alt_suffix)\n",
    "        l_interval = model.NewOptionalIntervalVar(\n",
    "            l_start, l_duration, l_end, l_presence, 'interval' + alt_suffix)\n",
    "        l_presences.append(l_presence)\n",
    "\n",
    "        # Link the master variables with the local ones.\n",
    "        model.Add(start == l_start).OnlyEnforceIf(l_presence)\n",
    "        model.Add(duration == l_duration).OnlyEnforceIf(l_presence)\n",
    "        model.Add(end == l_end).OnlyEnforceIf(l_presence)\n",
    "\n",
    "        # Add the local interval to the right machine.\n",
    "        intervals_per_resources[task[alt_id][1]].append(l_interval)\n",
    "\n",
    "        # Store the presences for the solution.\n",
    "        presences[(job_id, task_id, alt_id)] = l_presence\n",
    "\n",
    "      # Select exactly one presence variable.\n",
    "      model.Add(sum(l_presences) == 1)\n",
    "    else:\n",
    "      intervals_per_resources[task[0][1]].append(interval)\n",
    "      presences[(job_id, task_id, 0)] = model.NewConstant(1)\n",
    "\n",
    "  job_ends.append(previous_end)\n",
    "\n",
    "# Create machines constraints.\n",
    "for machine_id in all_machines:\n",
    "  intervals = intervals_per_resources[machine_id]\n",
    "  if len(intervals) > 1:\n",
    "    model.AddNoOverlap(intervals)\n",
    "\n",
    "# Makespan objective\n",
    "makespan = model.NewIntVar(0, horizon, 'makespan')\n",
    "model.AddMaxEquality(makespan, job_ends)\n",
    "model.Minimize(makespan)\n",
    "\n",
    "# Solve model.\n",
    "solver = cp_model.CpSolver()\n",
    "solution_printer = SolutionPrinter()\n",
    "status = solver.SolveWithSolutionCallback(model, solution_printer)\n",
    "\n",
    "# Print final solution.\n",
    "for job_id in all_jobs:\n",
    "  print('Job %i:' % job_id)\n",
    "  for task_id in range(len(jobs[job_id])):\n",
    "    start_value = solver.Value(starts[(job_id, task_id)])\n",
    "    machine = -1\n",
    "    duration = -1\n",
    "    selected = -1\n",
    "    for alt_id in range(len(jobs[job_id][task_id])):\n",
    "      if solver.Value(presences[(job_id, task_id, alt_id)]):\n",
    "        duration = jobs[job_id][task_id][alt_id][0]\n",
    "        machine = jobs[job_id][task_id][alt_id][1]\n",
    "        selected = alt_id\n",
    "    print('  task_%i_%i starts at %i (alt %i, machine %i, duration %i)' %\n",
    "          (job_id, task_id, start_value, selected, machine, duration))\n",
    "\n",
    "print('Solve status: %s' % solver.StatusName(status))\n",
    "print('Optimal objective value: %i' % solver.ObjectiveValue())\n",
    "print('Statistics')\n",
    "print('  - conflicts : %i' % solver.NumConflicts())\n",
    "print('  - branches  : %i' % solver.NumBranches())\n",
    "print('  - wall time : %f s' % solver.WallTime())\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}