{ "cells": [ { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "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", "import collections\n", "\n", "from ortools.sat.python import cp_model\n", "\n", "\n", "def MinimalCpSat():\n", " # Creates the model.\n", " model = cp_model.CpModel()\n", "# Creates the variables.\n", " num_vals = 3\n", " x = model.NewIntVar(0, num_vals - 1, \"x\")\n", " y = model.NewIntVar(0, num_vals - 1, \"y\")\n", " z = model.NewIntVar(0, num_vals - 1, \"z\")\n", " # Create the constraints.\n", " model.Add(x != y)\n", "\n", " # Create a solver and solve.\n", " solver = cp_model.CpSolver()\n", " status = solver.Solve(model)\n", "\n", " if status == cp_model.MODEL_SAT:\n", " print(\"x = %i\" % solver.Value(x))\n", " print(\"y = %i\" % solver.Value(y))\n", " print(\"z = %i\" % solver.Value(z))\n", "\n", "\n", "class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):\n", " \"\"\"Print intermediate solutions.\"\"\"\n", "\n", " def __init__(self, variables):\n", " self.__variables = variables\n", " self.__solution_count = 0\n", "\n", " def NewSolution(self):\n", " self.__solution_count += 1\n", " for v in self.__variables:\n", " print('%s=%i' % (v, self.Value(v)), end = ' ')\n", " print()\n", "\n", " def SolutionCount(self):\n", " return self.__solution_count\n", "\n", "\n", "\n", "\n", "def MinimalCpSatAllSolutions():\n", " # Creates the model.\n", " model = cp_model.CpModel()\n", "# Creates the variables.\n", " num_vals = 3\n", " x = model.NewIntVar(0, num_vals - 1, \"x\")\n", " y = model.NewIntVar(0, num_vals - 1, \"y\")\n", " z = model.NewIntVar(0, num_vals - 1, \"z\")\n", " # Create the constraints.\n", " model.Add(x != y)\n", "\n", " # Create a solver and solve.\n", " solver = cp_model.CpSolver()\n", " solution_printer = VarArraySolutionPrinter([x, y, z])\n", " status = solver.SearchForAllSolutions(model, solution_printer)\n", "\n", " print('Number of solutions found: %i' % solution_printer.SolutionCount())\n", "\n", "\n", "def SolvingLinearProblem():\n", " # Create a model.\n", " model = cp_model.CpModel()\n", "\n", " # x and y are integer non-negative variables.\n", " x = model.NewIntVar(0, 17, 'x')\n", " y = model.NewIntVar(0, 17, 'y')\n", " model.Add(2*x + 14*y <= 35)\n", " model.Add(2*x <= 7)\n", " obj_var = model.NewIntVar(0, 1000, \"obj_var\")\n", " model.Add(obj_var == x + 10*y)\n", " objective = model.Maximize(obj_var)\n", "\n", " # Create a solver and solve.\n", " solver = cp_model.CpSolver()\n", " status = solver.Solve(model)\n", " if status == cp_model.OPTIMAL:\n", " print(\"Objective value: %i\" % solver.ObjectiveValue())\n", " print()\n", " print('x= %i' % solver.Value(x))\n", " print('y= %i' % solver.Value(y))\n", "\n", "\n", "def MinimalJobShop():\n", " # Create the model.\n", " model = cp_model.CpModel()\n", "\n", " machines_count = 3\n", " jobs_count = 3\n", " all_machines = range(0, machines_count)\n", " all_jobs = range(0, jobs_count)\n", " # Define data.\n", " machines = [[0, 1, 2],\n", " [0, 2, 1],\n", " [1, 2]]\n", "\n", " processing_times = [[3, 2, 2],\n", " [2, 1, 4],\n", " [4, 3]]\n", " # Computes horizon.\n", " horizon = 0\n", " for job in all_jobs:\n", " horizon += sum(processing_times[job])\n", "\n", " Task = collections.namedtuple('Task', 'start end interval')\n", " AssignedTask = collections.namedtuple('AssignedTask', 'start job index')\n", "\n", " # Creates jobs.\n", " all_tasks = {}\n", " for job in all_jobs:\n", " for index in range(0, len(machines[job])):\n", " start_var = model.NewIntVar(0, horizon, 'start_%i_%i' % (job, index))\n", " duration = processing_times[job][index]\n", " end_var = model.NewIntVar(0, horizon, 'end_%i_%i' % (job, index))\n", " interval_var = model.NewIntervalVar(start_var, duration, end_var,\n", " 'interval_%i_%i' % (job, index))\n", " all_tasks[(job, index)] = Task(start=start_var,\n", " end=end_var,\n", " interval=interval_var)\n", "\n", " # Creates sequence variables and add disjunctive constraints.\n", " for machine in all_machines:\n", " intervals = []\n", " for job in all_jobs:\n", " for index in range(0, len(machines[job])):\n", " if machines[job][index] == machine:\n", " intervals.append(all_tasks[(job, index)].interval)\n", " model.AddNoOverlap(intervals)\n", "\n", " # Add precedence contraints.\n", " for job in all_jobs:\n", " for index in range(0, len(machines[job]) - 1):\n", " model.Add(all_tasks[(job, index + 1)].start >=\n", " all_tasks[(job, index)].end)\n", "\n", " # Makespan objective.\n", " obj_var = model.NewIntVar(0, horizon, 'makespan')\n", " model.AddMaxEquality(\n", " obj_var, [all_tasks[(job, len(machines[job]) - 1)].end\n", " for job in all_jobs])\n", " model.Minimize(obj_var)\n", "\n", " # Solve model.\n", " solver = cp_model.CpSolver()\n", " status = solver.Solve(model)\n", "\n", " if status == cp_model.OPTIMAL:\n", " # Print out makespan.\n", " print('Optimal Schedule Length: %i' % solver.ObjectiveValue())\n", " print()\n", "\n", " # Create one list of assigned tasks per machine.\n", " assigned_jobs = [[] for _ in range(machines_count)]\n", " for job in all_jobs:\n", " for index in range(len(machines[job])):\n", " machine = machines[job][index]\n", " assigned_jobs[machine].append(\n", " AssignedTask(start = solver.Value(all_tasks[(job, index)].start),\n", " job = job, index = index))\n", "\n", " disp_col_width = 10\n", " sol_line = \"\"\n", " sol_line_tasks = \"\"\n", "\n", " print(\"Optimal Schedule\", \"\\n\")\n", "\n", " for machine in all_machines:\n", " # Sort by starting time.\n", " assigned_jobs[machine].sort()\n", " sol_line += \"Machine \" + str(machine) + \": \"\n", " sol_line_tasks += \"Machine \" + str(machine) + \": \"\n", "\n", " for assigned_task in assigned_jobs[machine]:\n", " name = 'job_%i_%i' % (assigned_task.job, assigned_task.index)\n", " # Add spaces to output to align columns.\n", " sol_line_tasks += name + \" \" * (disp_col_width - len(name))\n", " start = assigned_task.start\n", " duration = processing_times[assigned_task.job][assigned_task.index]\n", "\n", " sol_tmp = \"[%i,%i]\" % (start, start + duration)\n", " # Add spaces to output to align columns.\n", " sol_line += sol_tmp + \" \" * (disp_col_width - len(sol_tmp))\n", "\n", " sol_line += \"\\n\"\n", " sol_line_tasks += \"\\n\"\n", "\n", " print(sol_line_tasks)\n", " print(\"Time Intervals for Tasks\\n\")\n", " print(sol_line)\n", "\n", "\n", "\n", "def main():\n", " MinimalCpSat()\n", " MinimalCpSatAllSolutions()\n", " SolvingLinearProblem()\n", " MinimalJobShop()\n", "\n", "\n", "if __name__ == '__main__':\n", " main()" ] } ], "metadata": {}, "nbformat": 4, "nbformat_minor": 2 }