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