    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>&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 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}