    001    package ifs.example.jobshop;
    002
    003    import ifs.model.*;
    004    import ifs.util.*;
    005    import java.io.*;
    006    import java.util.*;
    007
    008    /**
    009     * Job Shop model.
    010     * <br><br>
    011     * It contains the number of available time slots and all machines and jobs.
    012     * <br><br>
    013     * It can also load the model from a file and save the solution.
    014     * <br><br>
    015     * <b>Input file format:</b><ul>
    016     * First line: <ul><code>&lt;number of jobs&gt; &lt;number of machines&gt;</code></ul>
    017     * Following lines: <ul>space separated list (a line for each job) of operations, each operation consist of machine number and operation processing time</ul>
    018     * Example of 10 jobs, 10 machines:<ul><code>
    019     * 10 10<br>
    020     * 4 88 8 68 6 94 5 99 1 67 2 89 9 77 7 99 0 86 3 92<br>
    021     * 5 72 3 50 6 69 4 75 2 94 8 66 0 92 1 82 7 94 9 63<br>
    022     * 9 83 8 61 0 83 1 65 6 64 5 85 7 78 4 85 2 55 3 77<br>
    023     * 7 94 2 68 1 61 4 99 3 54 6 75 5 66 0 76 9 63 8 67<br>
    024     * 3 69 4 88 9 82 8 95 0 99 2 67 6 95 5 68 7 67 1 86<br>
    025     * 1 99 4 81 5 64 6 66 8 80 2 80 7 69 9 62 3 79 0 88<br>
    026     * 7 50 1 86 4 97 3 96 0 95 8 97 2 66 5 99 6 52 9 71<br>
    027     * 4 98 6 73 3 82 2 51 1 71 5 94 7 85 0 62 8 95 9 79<br>
    028     * 0 94 6 71 3 81 7 85 1 66 2 90 4 76 5 58 8 93 9 97<br>
    029     * 3 50 0 59 1 82 8 67 7 56 9 96 6 58 4 81 5 59 2 96<br>
    030     * </code></ul>
    031     * For instance, the first job is described as follows: <ul>
    032     * 88 time units on machine 4, then 68 time units on machine 8, then 94 time units on machine 6 ...
    033     * </ul>
    034     * </ul><br>
    035     * <b>Output file firmat:</b><ul>
    036     * 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.
    037     * </ul>
    038     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    039     * @version 1.0
    040     */
    041    public class JobShopModel extends Model {
    042        private int iTotalNumberOfSlots = 1250;
    043        private Machine[] iMachines;
    044        private Job[] iJobs;
    045
    046        /**
    047         * Constructor
    048         * @param nrMachines number of machines
    049         * @param nrJobs number of jobs
    050         */
    051        public JobShopModel(int nrMachines,int nrJobs) {
    052            super();
    053            iMachines = new Machine[nrMachines];
    054            iJobs = new Job[nrJobs];
    055        }
    056
    057        /** Get total number of slots */
    058        public int getTotalNumberOfSlots() { return iTotalNumberOfSlots; }
    059        /** Get machine of the given numbner */
    060        public Machine getMachine(int machineNumber) { return iMachines[machineNumber]; }
    061        /** Count number of machines in the model */
    062        public int countMachines() { return iMachines.length; }
    063        /** Get job of the given number */
    064        public Job getJob(int jobNumber) { return iJobs[jobNumber]; }
    065        /** Count number of jobs in the model */
    066        public int countJobs() { return iJobs.length; }
    067
    068        private void setJob(int jobNumber, Job job) { iJobs[jobNumber]=job; }
    069        private void setMachine(int machineNumber, Machine machine) { iMachines[machineNumber]=machine; }
    070
    071        /** Loads the model from the given file */
    072        public static JobShopModel loadModel(String file) throws IOException {
    073            BufferedReader reader = new BufferedReader(new FileReader(file));
    074            String line = reader.readLine();
    075            while (line.startsWith("#")) line = reader.readLine();
    076            StringTokenizer stk = new StringTokenizer(line," ");
    077            int nrJobs = Integer.parseInt(stk.nextToken());
    078            int nrMachines = Integer.parseInt(stk.nextToken());
    079            JobShopModel model = new JobShopModel(nrMachines,nrJobs);
    080            Machine[] machine = new Machine[nrMachines];
    081            for (int i=0;i<nrMachines;i++) {
    082                machine[i]=new Machine(i);
    083                model.addConstraint(machine[i]);
    084                model.setMachine(i, machine[i]);
    085            }
    086            for (int i=0;i<nrJobs;i++) {
    087                Job job = new Job(i);
    088                model.addConstraint(job);
    089                model.setJob(i, job);
    090                line = reader.readLine();
    091                stk = new StringTokenizer(line," ");
    092                for (int j=0;j<nrMachines;j++) {
    093                    int machineNumber = Integer.parseInt(stk.nextToken());
    094                    int processingTime = Integer.parseInt(stk.nextToken());
    095                    Operation operation = new Operation(job,machine[machineNumber],j,processingTime);
    096                    model.addVariable(operation);
    097                    job.addVariable(operation);
    098                    machine[machineNumber].addVariable(operation);
    099                }
    100                if (stk.hasMoreTokens()) {
    101                    job.setDueTime(Integer.parseInt(stk.nextToken()));
    102                }
    103            }
    104            reader.close();
    105            for (Enumeration e=model.variables().elements();e.hasMoreElements();)
    106                ((Operation)e.nextElement()).init();
    107            return model;
    108        }
    109
    110        /** Get finishing time of the current (partial) solution */
    111        public int getFinishingTime() {
    112            int ret = 0;
    113            for (Enumeration e=assignedVariables().elements();e.hasMoreElements();) {
    114                ret = Math.max(ret,((Location)((Operation)e.nextElement()).getAssignment()).getFinishingTime());
    115            }
    116            return ret;
    117        }
    118
    119        /** Get information table */
    120        public Hashtable getInfo() {
    121            Hashtable ret = super.getInfo();
    122            ret.put("Finishing time", String.valueOf(getFinishingTime()));
    123            return ret;
    124        }
    125
    126        /** Save the solution into the given file */
    127        public void save(String file) throws java.io.IOException {
    128            PrintWriter writer = new PrintWriter(new FileWriter(file));
    129            for (int i=0;i<countMachines();i++) {
    130                Machine m = getMachine(i);
    131                Vector ops = (Vector)m.variables().clone();
    132                Collections.sort(ops, new OperationComparator());
    133                for (Enumeration e=ops.elements();e.hasMoreElements();) {
    134                    Operation op = (Operation)e.nextElement();
    135                    if (op.getAssignment()!=null)
    136                        writer.print((op.getJobNumber()<10?" ":"")+op.getJobNumber()+" ");
    137                }
    138                writer.println();
    139            }
    140            writer.println(";");
    141            Hashtable info = getInfo();
    142            for (Enumeration e=info.keys();e.hasMoreElements(); ) {
    143                Object key = e.nextElement();
    144                Object value = info.get(key);
    145                writer.println("; "+key+": "+value);
    146            }
    147            writer.println(";");
    148            for (int i=0;i<countJobs();i++) {
    149                Job job = getJob(i);
    150                writer.print("; ");
    151                for (Enumeration e=job.variables().elements();e.hasMoreElements();) {
    152                    Operation op = (Operation)e.nextElement();
    153                    Location loc = (Location)op.getAssignment();
    154                    writer.print((loc==null?"----":ToolBox.trim(String.valueOf(loc.getStartTime()), 4))+" ");
    155                }
    156                writer.println();
    157            }
    158            writer.flush();writer.close();
    159        }
    160
    161        private static class OperationComparator implements Comparator {
    162            public int compare(Object o1, Object o2) {
    163                Operation op1 = (Operation)o1;
    164                Operation op2 = (Operation)o2;
    165                Location loc1 = (Location)op1.getAssignment();
    166                Location loc2 = (Location)op2.getAssignment();
    167                if (loc1==null) {
    168                    if (loc2==null) return 0;
    169                    else return -1;
    170                }
    171                if (loc2==null) return 1;
    172                return (loc1.getStartTime()<loc2.getStartTime()?-1:loc1.getStartTime()==loc2.getStartTime()?0:1);
    173            }
    174        }
    175    }