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