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