001package org.cpsolver.ifs.example.jobshop; 002 003import java.io.BufferedReader; 004import java.io.FileReader; 005import java.io.FileWriter; 006import java.io.IOException; 007import java.io.PrintWriter; 008import java.util.ArrayList; 009import java.util.Collections; 010import java.util.Comparator; 011import java.util.List; 012import java.util.Map; 013import java.util.StringTokenizer; 014 015import org.cpsolver.ifs.assignment.Assignment; 016import org.cpsolver.ifs.model.Model; 017import org.cpsolver.ifs.util.ToolBox; 018 019 020/** 021 * Job Shop model. <br> 022 * <br> 023 * It contains the number of available time slots and all machines and jobs. <br> 024 * <br> 025 * It can also load the model from a file and save the solution. <br> 026 * <br> 027 * <b>Input file format:</b> 028 * First line: 029 * <pre><code><number of jobs> <number of machines></code></pre> 030 * Following lines: 031 * <pre> 032 * space separated list (a line for each job) of operations, each operation 033 * consist of machine number and operation processing time 034 * </pre> 035 * Example of 10 jobs, 10 machines: 036 * <pre><code> 037 * 10 10 038 * 4 88 8 68 6 94 5 99 1 67 2 89 9 77 7 99 0 86 3 92 039 * 5 72 3 50 6 69 4 75 2 94 8 66 0 92 1 82 7 94 9 63 040 * 9 83 8 61 0 83 1 65 6 64 5 85 7 78 4 85 2 55 3 77 041 * 7 94 2 68 1 61 4 99 3 54 6 75 5 66 0 76 9 63 8 67 042 * 3 69 4 88 9 82 8 95 0 99 2 67 6 95 5 68 7 67 1 86 043 * 1 99 4 81 5 64 6 66 8 80 2 80 7 69 9 62 3 79 0 88 044 * 7 50 1 86 4 97 3 96 0 95 8 97 2 66 5 99 6 52 9 71 045 * 4 98 6 73 3 82 2 51 1 71 5 94 7 85 0 62 8 95 9 79 046 * 0 94 6 71 3 81 7 85 1 66 2 90 4 76 5 58 8 93 9 97 047 * 3 50 0 59 1 82 8 67 7 56 9 96 6 58 4 81 5 59 2 96 048 * </code></pre> 049 * For instance, the first job is described as follows: 050 * <pre> 051 * 88 time units on machine 4, then 68 time units on machine 8, then 94 time 052 * units on machine 6 ... 053 * </pre> 054 * <br> 055 * <b>Output file firmat:</b> 056 * <pre> 057 * A line for each machine, in each line there is a space separated list of jobs 058 * which the machine will process in the order they will be processed. 059 * </pre> 060 * 061 * @author Tomáš Müller 062 * @version IFS 1.3 (Iterative Forward Search)<br> 063 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 064 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 065 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 066 * <br> 067 * This library is free software; you can redistribute it and/or modify 068 * it under the terms of the GNU Lesser General Public License as 069 * published by the Free Software Foundation; either version 3 of the 070 * License, or (at your option) any later version. <br> 071 * <br> 072 * This library is distributed in the hope that it will be useful, but 073 * WITHOUT ANY WARRANTY; without even the implied warranty of 074 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 075 * Lesser General Public License for more details. <br> 076 * <br> 077 * You should have received a copy of the GNU Lesser General Public 078 * License along with this library; if not see 079 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 080 */ 081public class JobShopModel extends Model<Operation, Location> { 082 private int iTotalNumberOfSlots = 1250; 083 private Machine[] iMachines; 084 private Job[] iJobs; 085 086 /** 087 * Constructor � 088 * 089 * @param nrMachines 090 * number of machines 091 * @param nrJobs 092 * number of jobs 093 */ 094 public JobShopModel(int nrMachines, int nrJobs) { 095 super(); 096 iMachines = new Machine[nrMachines]; 097 iJobs = new Job[nrJobs]; 098 } 099 100 /** Get total number of slots 101 * @return total number of slots 102 **/ 103 public int getTotalNumberOfSlots() { 104 return iTotalNumberOfSlots; 105 } 106 107 /** Get machine of the given number 108 * @param machineNumber machine number 109 * @return machine of the given number 110 **/ 111 public Machine getMachine(int machineNumber) { 112 return iMachines[machineNumber]; 113 } 114 115 /** Count number of machines in the model 116 * @return number of machines in the model 117 **/ 118 public int countMachines() { 119 return iMachines.length; 120 } 121 122 /** Get job of the given number 123 * @param jobNumber job number 124 * @return job of the given number 125 **/ 126 public Job getJob(int jobNumber) { 127 return iJobs[jobNumber]; 128 } 129 130 /** Count number of jobs in the model 131 * @return number of jobs in the model 132 **/ 133 public int countJobs() { 134 return iJobs.length; 135 } 136 137 private void setJob(int jobNumber, Job job) { 138 iJobs[jobNumber] = job; 139 } 140 141 private void setMachine(int machineNumber, Machine machine) { 142 iMachines[machineNumber] = machine; 143 } 144 145 /** Loads the model from the given file 146 * @param file file to load 147 * @return loaded model 148 * @throws IOException thrown when there is a problem reading the input file */ 149 public static JobShopModel loadModel(String file) throws IOException { 150 BufferedReader reader = new BufferedReader(new FileReader(file)); 151 String line = reader.readLine(); 152 while (line.startsWith("#")) 153 line = reader.readLine(); 154 StringTokenizer stk = new StringTokenizer(line, " "); 155 int nrJobs = Integer.parseInt(stk.nextToken()); 156 int nrMachines = Integer.parseInt(stk.nextToken()); 157 JobShopModel model = new JobShopModel(nrMachines, nrJobs); 158 Machine[] machine = new Machine[nrMachines]; 159 for (int i = 0; i < nrMachines; i++) { 160 machine[i] = new Machine(i); 161 model.addConstraint(machine[i]); 162 model.setMachine(i, machine[i]); 163 } 164 for (int i = 0; i < nrJobs; i++) { 165 Job job = new Job(i); 166 model.addConstraint(job); 167 model.setJob(i, job); 168 line = reader.readLine(); 169 stk = new StringTokenizer(line, " "); 170 for (int j = 0; j < nrMachines; j++) { 171 int machineNumber = Integer.parseInt(stk.nextToken()); 172 int processingTime = Integer.parseInt(stk.nextToken()); 173 Operation operation = new Operation(job, machine[machineNumber], j, processingTime); 174 model.addVariable(operation); 175 job.addVariable(operation); 176 machine[machineNumber].addVariable(operation); 177 } 178 if (stk.hasMoreTokens()) { 179 job.setDueTime(Integer.parseInt(stk.nextToken())); 180 } 181 } 182 reader.close(); 183 for (Operation o : model.variables()) 184 o.init(); 185 return model; 186 } 187 188 /** Get finishing time of the current (partial) solution 189 * @param assignment current assignment 190 * @return finishing time of the current (partial) solution 191 **/ 192 public int getFinishingTime(Assignment<Operation, Location> assignment) { 193 int ret = 0; 194 for (Operation op : assignment.assignedVariables()) { 195 ret = Math.max(ret, assignment.getValue(op).getFinishingTime()); 196 } 197 return ret; 198 } 199 200 /** Get information table */ 201 @Override 202 public Map<String, String> getInfo(Assignment<Operation, Location> assignment) { 203 Map<String, String> ret = super.getInfo(assignment); 204 ret.put("Finishing time", String.valueOf(getFinishingTime(assignment))); 205 return ret; 206 } 207 208 /** Save the solution into the given file 209 * @param assignment current assignment 210 * @param file file to write 211 * @throws java.io.IOException throw when there is a problem writing the file 212 **/ 213 public void save(Assignment<Operation, Location> assignment, String file) throws java.io.IOException { 214 PrintWriter writer = new PrintWriter(new FileWriter(file)); 215 for (int i = 0; i < countMachines(); i++) { 216 Machine m = getMachine(i); 217 List<Operation> ops = new ArrayList<Operation>(m.variables()); 218 Collections.sort(ops, new OperationComparator(assignment)); 219 for (Operation var : ops) { 220 Operation op = var; 221 if (assignment.getValue(op) != null) 222 writer.print((op.getJobNumber() < 10 ? " " : "") + op.getJobNumber() + " "); 223 } 224 writer.println(); 225 } 226 writer.println(";"); 227 Map<String, String> info = getInfo(assignment); 228 for (String key : info.keySet()) { 229 String value = info.get(key); 230 writer.println("; " + key + ": " + value); 231 } 232 writer.println(";"); 233 for (int i = 0; i < countJobs(); i++) { 234 Job job = getJob(i); 235 writer.print("; "); 236 for (Operation op : job.variables()) { 237 Location loc = assignment.getValue(op); 238 writer.print((loc == null ? "----" : ToolBox.trim(String.valueOf(loc.getStartTime()), 4)) + " "); 239 } 240 writer.println(); 241 } 242 writer.flush(); 243 writer.close(); 244 } 245 246 private static class OperationComparator implements Comparator<Operation> { 247 Assignment<Operation, Location> iAssignment; 248 249 public OperationComparator(Assignment<Operation, Location> assignment) { 250 iAssignment = assignment; 251 } 252 253 @Override 254 public int compare(Operation op1, Operation op2) { 255 Location loc1 = iAssignment.getValue(op1); 256 Location loc2 = iAssignment.getValue(op2); 257 if (loc1 == null) { 258 if (loc2 == null) 259 return 0; 260 else 261 return -1; 262 } 263 if (loc2 == null) 264 return 1; 265 return (loc1.getStartTime() < loc2.getStartTime() ? -1 : loc1.getStartTime() == loc2.getStartTime() ? 0 : 1); 266 } 267 } 268}