001 package net.sf.cpsolver.ifs.example.jobshop;
002
003 import java.io.BufferedReader;
004 import java.io.FileReader;
005 import java.io.FileWriter;
006 import java.io.IOException;
007 import java.io.PrintWriter;
008 import java.util.ArrayList;
009 import java.util.Collections;
010 import java.util.Comparator;
011 import java.util.List;
012 import java.util.Map;
013 import java.util.StringTokenizer;
014
015 import net.sf.cpsolver.ifs.model.Model;
016 import 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 Tomas Muller<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 */
083 public 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 }