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>&lt;number of jobs&gt; &lt;number of machines&gt;</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    }