1 // Copyright 2010-2021 Google LLC 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 14 // [START program] 15 package com.google.ortools.sat.samples; 16 // [START import] 17 import static java.lang.Math.max; 18 19 import com.google.ortools.Loader; 20 import com.google.ortools.sat.CpModel; 21 import com.google.ortools.sat.CpSolver; 22 import com.google.ortools.sat.CpSolverStatus; 23 import com.google.ortools.sat.IntVar; 24 import com.google.ortools.sat.IntervalVar; 25 import com.google.ortools.sat.LinearExpr; 26 import java.util.ArrayList; 27 import java.util.Arrays; 28 import java.util.Collections; 29 import java.util.Comparator; 30 import java.util.HashMap; 31 import java.util.List; 32 import java.util.Map; 33 import java.util.stream.IntStream; 34 // [END import] 35 36 /** Minimal Jobshop problem. */ 37 public class MinimalJobshopSat { main(String[] args)38 public static void main(String[] args) { 39 Loader.loadNativeLibraries(); 40 // [START data] 41 class Task { 42 int machine; 43 int duration; 44 Task(int machine, int duration) { 45 this.machine = machine; 46 this.duration = duration; 47 } 48 } 49 50 final List<List<Task>> allJobs = 51 Arrays.asList(Arrays.asList(new Task(0, 3), new Task(1, 2), new Task(2, 2)), // Job0 52 Arrays.asList(new Task(0, 2), new Task(2, 1), new Task(1, 4)), // Job1 53 Arrays.asList(new Task(1, 4), new Task(2, 3)) // Job2 54 ); 55 56 int numMachines = 1; 57 for (List<Task> job : allJobs) { 58 for (Task task : job) { 59 numMachines = max(numMachines, 1 + task.machine); 60 } 61 } 62 final int[] allMachines = IntStream.range(0, numMachines).toArray(); 63 64 // Computes horizon dynamically as the sum of all durations. 65 int horizon = 0; 66 for (List<Task> job : allJobs) { 67 for (Task task : job) { 68 horizon += task.duration; 69 } 70 } 71 // [END data] 72 73 // Creates the model. 74 // [START model] 75 CpModel model = new CpModel(); 76 // [END model] 77 78 // [START variables] 79 class TaskType { 80 IntVar start; 81 IntVar end; 82 IntervalVar interval; 83 } 84 Map<List<Integer>, TaskType> allTasks = new HashMap<>(); 85 Map<Integer, List<IntervalVar>> machineToIntervals = new HashMap<>(); 86 87 for (int jobID = 0; jobID < allJobs.size(); ++jobID) { 88 List<Task> job = allJobs.get(jobID); 89 for (int taskID = 0; taskID < job.size(); ++taskID) { 90 Task task = job.get(taskID); 91 String suffix = "_" + jobID + "_" + taskID; 92 93 TaskType taskType = new TaskType(); 94 taskType.start = model.newIntVar(0, horizon, "start" + suffix); 95 taskType.end = model.newIntVar(0, horizon, "end" + suffix); 96 taskType.interval = model.newIntervalVar( 97 taskType.start, LinearExpr.constant(task.duration), taskType.end, "interval" + suffix); 98 99 List<Integer> key = Arrays.asList(jobID, taskID); 100 allTasks.put(key, taskType); 101 machineToIntervals.computeIfAbsent(task.machine, (Integer k) -> new ArrayList<>()); 102 machineToIntervals.get(task.machine).add(taskType.interval); 103 } 104 } 105 // [END variables] 106 107 // [START constraints] 108 // Create and add disjunctive constraints. 109 for (int machine : allMachines) { 110 List<IntervalVar> list = machineToIntervals.get(machine); 111 model.addNoOverlap(list.toArray(new IntervalVar[0])); 112 } 113 114 // Precedences inside a job. 115 for (int jobID = 0; jobID < allJobs.size(); ++jobID) { 116 List<Task> job = allJobs.get(jobID); 117 for (int taskID = 0; taskID < job.size() - 1; ++taskID) { 118 List<Integer> prevKey = Arrays.asList(jobID, taskID); 119 List<Integer> nextKey = Arrays.asList(jobID, taskID + 1); 120 model.addGreaterOrEqual(allTasks.get(nextKey).start, allTasks.get(prevKey).end); 121 } 122 } 123 // [END constraints] 124 125 // [START objective] 126 // Makespan objective. 127 IntVar objVar = model.newIntVar(0, horizon, "makespan"); 128 List<IntVar> ends = new ArrayList<>(); 129 for (int jobID = 0; jobID < allJobs.size(); ++jobID) { 130 List<Task> job = allJobs.get(jobID); 131 List<Integer> key = Arrays.asList(jobID, job.size() - 1); 132 ends.add(allTasks.get(key).end); 133 } 134 model.addMaxEquality(objVar, ends.toArray(new IntVar[0])); 135 model.minimize(objVar); 136 // [END objective] 137 138 // Creates a solver and solves the model. 139 // [START solve] 140 CpSolver solver = new CpSolver(); 141 CpSolverStatus status = solver.solve(model); 142 // [END solve] 143 144 // [START print_solution] 145 if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) { 146 class AssignedTask { 147 int jobID; 148 int taskID; 149 int start; 150 int duration; 151 // Ctor 152 AssignedTask(int jobID, int taskID, int start, int duration) { 153 this.jobID = jobID; 154 this.taskID = taskID; 155 this.start = start; 156 this.duration = duration; 157 } 158 } 159 class SortTasks implements Comparator<AssignedTask> { 160 @Override 161 public int compare(AssignedTask a, AssignedTask b) { 162 if (a.start != b.start) { 163 return a.start - b.start; 164 } else { 165 return a.duration - b.duration; 166 } 167 } 168 } 169 System.out.println("Solution:"); 170 // Create one list of assigned tasks per machine. 171 Map<Integer, List<AssignedTask>> assignedJobs = new HashMap<>(); 172 for (int jobID = 0; jobID < allJobs.size(); ++jobID) { 173 List<Task> job = allJobs.get(jobID); 174 for (int taskID = 0; taskID < job.size(); ++taskID) { 175 Task task = job.get(taskID); 176 List<Integer> key = Arrays.asList(jobID, taskID); 177 AssignedTask assignedTask = new AssignedTask( 178 jobID, taskID, (int) solver.value(allTasks.get(key).start), task.duration); 179 assignedJobs.computeIfAbsent(task.machine, (Integer k) -> new ArrayList<>()); 180 assignedJobs.get(task.machine).add(assignedTask); 181 } 182 } 183 184 // Create per machine output lines. 185 String output = ""; 186 for (int machine : allMachines) { 187 // Sort by starting time. 188 Collections.sort(assignedJobs.get(machine), new SortTasks()); 189 String solLineTasks = "Machine " + machine + ": "; 190 String solLine = " "; 191 192 for (AssignedTask assignedTask : assignedJobs.get(machine)) { 193 String name = "job_" + assignedTask.jobID + "_task_" + assignedTask.taskID; 194 // Add spaces to output to align columns. 195 solLineTasks += String.format("%-15s", name); 196 197 String solTmp = 198 "[" + assignedTask.start + "," + (assignedTask.start + assignedTask.duration) + "]"; 199 // Add spaces to output to align columns. 200 solLine += String.format("%-15s", solTmp); 201 } 202 output += solLineTasks + "%n"; 203 output += solLine + "%n"; 204 } 205 System.out.printf("Optimal Schedule Length: %f%n", solver.objectiveValue()); 206 System.out.printf(output); 207 } else { 208 System.out.println("No solution found."); 209 } 210 // [END print_solution] 211 212 // Statistics. 213 // [START statistics] 214 System.out.println("Statistics"); 215 System.out.printf(" conflicts: %d%n", solver.numConflicts()); 216 System.out.printf(" branches : %d%n", solver.numBranches()); 217 System.out.printf(" wall time: %f s%n", solver.wallTime()); 218 // [END statistics] 219 } 220 MinimalJobshopSat()221 private MinimalJobshopSat() {} 222 } 223 // [END program] 224