Flowshop¶

/********** Flowshop.java **********/

import java.util.*;
import java.io.*;
import localsolver.*;

public class Flowshop {
    /* Number of jobs */
	int nbJobs;

    /* Number of machines */
	int nbMachines;

    /* Initial seed used to generate the instance */
	long initialSeed;

    /* Upper bound */
	int upperBound;

    /* Lower bound*/
	int lowerBound;

    /* Processing time */
    long[][] processingTime;

    /* LocalSolver */
    LocalSolver localsolver;

    /* Decision variable */
    LSExpression jobs;

    /* Objective */
    LSExpression makespan;

    /* Reads instance data. */
    void readInstance(String fileName) {
        try {
            Scanner input = new Scanner(new File(fileName));

            nbJobs = input.nextInt();
            nbMachines = input.nextInt();
            initialSeed = input.nextInt();
            upperBound = input.nextInt();
            lowerBound = input.nextInt();

            processingTime = new long[nbMachines][nbJobs];
            for (int m = 0; m < nbMachines; m++) {
                for(int j = 0; j < nbJobs; j++) {
                    processingTime[m][j] = input.nextInt();
                }
            }
            input.close();
            
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    void solve(int limit) {
        try {
            localsolver = new LocalSolver();

            /* Declares the optimization model. */
            LSModel model = localsolver.getModel();


	        // Permutation of jobs
            jobs = model.listVar(nbJobs);

	        // All jobs have to be assigned
	        model.constraint(model.eq(model.count(jobs), nbJobs));

            // For each machine create proccessingTime[m] as an array to be able to access it 
            // with an 'at' operator
            LSExpression[] processingTimeArray = new LSExpression[nbMachines];
            for (int m = 0; m < nbMachines; m++) {
                processingTimeArray[m] = model.array(processingTime[m]);
            }
   
			// As the operator [] is not overloaded, create the explicit list of jobs for easy access
            LSExpression[] explicitJobs = new LSExpression[nbJobs];
            for (int j = 0; j < nbJobs; j++) {
                explicitJobs[j] = model.at(jobs, j);
            }

            // end[m][j] is the end of the jth job on machine m
            LSExpression[][] end = new LSExpression[nbMachines][nbJobs];

            // On machine 0, the first job ends after it has been processed.
            end[0][0] = model.at(processingTimeArray[0], explicitJobs[0]);
            // On machine 0, the jth job ends on the time it took to be processed after 
            // the end of the previous job
            for (int j = 1; j < nbJobs; j++) {
                end[0][j] = model.sum(end[0][j-1], model.at(processingTimeArray[0], explicitJobs[j]));
            }
            // On machine m, the first job ends on the time it took to be processed after 
            // the end on the previous machine
            for (int m = 1; m < nbMachines; m++) {
            	end[m][0] = model.sum(end[m-1][0], model.at(processingTimeArray[m], explicitJobs[0]));
            }

            // The jth job on machine m starts when it has been processed by machine n-1 AND when 
            // job j-1 has been processed on machine m. It ends after it has been processed.
            for (int m = 1; m < nbMachines; m++) {
                for (int j = 1; j < nbJobs; j++) {
                    LSExpression start = model.max(end[m][j-1], end[m-1][j]);
                    end[m][j] = model.sum(start, model.at(processingTimeArray[m], explicitJobs[j]));
                }
            }

            // Minimize the makespan: end of the last job on the last machine
            makespan = end[nbMachines-1][nbJobs-1];
            model.minimize(makespan);

            model.close();

            /* Parameterizes the solver. */
            LSPhase phase = localsolver.createPhase();
            phase.setTimeLimit(limit);

            localsolver.solve();

        } catch (LSException e) {
            System.out.println("LSException:" + e.getMessage());
            System.exit(1);
        }
    }

    /* Writes the solution in a file */
    void writeSolution(String fileName) {
        try {
            BufferedWriter output = new BufferedWriter(new FileWriter(fileName));
            output.write(makespan.getValue() + "\n");
            LSCollection jobsCollection = jobs.getCollectionValue();
            for (int j = 0; j < nbJobs; j++) {
                output.write(jobsCollection.get(j) + " ");
            }
            output.write("\n");
            output.close();
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }
    
     public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("Usage: java Flowshop inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "20";

        Flowshop model = new Flowshop();
        model.readInstance(instanceFile);
        model.solve(Integer.parseInt(strTimeLimit));
        if(outputFile != null) {
            model.writeSolution(outputFile);
        }
    }
}