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