Assembly line balancing¶

/********** AssemblyLineBalancing.java **********/

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

public class AssemblyLineBalancing {

    private static class ALBInstance {
        int nbTasks;
        int nbMaxStations;
        int cycleTime;
        int[] processingTime;
        ArrayList<ArrayList<Integer>> successors;

        // Constructor
        private ALBInstance(String fileName) throws IOException {
            readInput(fileName);
        }

        // Read instance data
        private void readInput(String fileName) throws IOException {
            try (Scanner input = new Scanner(new File(fileName))) {

                input.nextLine();
                // Read number of tasks
                nbTasks = input.nextInt();
                nbMaxStations = nbTasks;
                processingTime = new int[nbTasks];
                successors = new ArrayList<ArrayList<Integer>>(nbTasks);
                for (int i = 0; i < nbTasks; i ++)
                    successors.add(i, new ArrayList<Integer>());
                for (int i = 0; i < 3; i++)
                    input.nextLine();

                // Read the cycle time limit
                cycleTime = input.nextInt();
                for (int i = 0; i < 7; ++i)
                    input.nextLine();

                // Read the processing times
                for (int i = 0; i < nbTasks; i++)
                    processingTime[input.nextInt()-1] = input.nextInt();
                for (int i = 0; i < 3; ++i)
                    input.nextLine();

                // Read the successors' relations
                String line = input.nextLine();
                while (!line.isEmpty()) {
                    String lineSplit[] = line.split(",");
                    int predecessor = Integer.parseInt(lineSplit[0]) -1;
                    int successor = Integer.parseInt(lineSplit[1]) -1;
                    successors.get(predecessor).add(successor);
                    line = input.nextLine();
                }
            }
        }
    }

    private static class ALBProblem {

        // LocalSolver
        private final LocalSolver localsolver;

        // Instance data
        private final ALBInstance instance;

        // Decision variable
        private LSExpression[] assignedStation;

        // Intermediate expressions
        private LSExpression[] stationUsed;
        private LSExpression[] timeStations;

        // Objective
        private LSExpression nbUsedStations;

        // Constructor
        private ALBProblem(LocalSolver localsolver, ALBInstance instance) {
            this.localsolver = localsolver;
            this.instance = instance;
        }

        private void solve(int limit) {
            // Declare the optimization model
            LSModel model = localsolver.getModel();

            // assignedStation[i] is the number of the station to which task i belongs
            assignedStation = new LSExpression[instance.nbTasks];
            for (int i = 0; i < instance.nbTasks; i++)
                assignedStation[i] = model.intVar(0, instance.nbMaxStations-1);

            // nbUsedStations is the total number of used stations
            stationUsed = new LSExpression[instance.nbMaxStations];
            nbUsedStations = model.sum();
            for (int s = 0; s < instance.nbMaxStations; s++) {
                stationUsed[s] = model.or();
                for (int i = 0; i < instance.nbTasks; i++) {
                    LSExpression isTaskInStation = model.eq(assignedStation[i], s);
                    stationUsed[s].addOperand(isTaskInStation);
                }
                nbUsedStations.addOperand(stationUsed[s]);
            }

            // All stations must respect the cycleTime constraint
            timeStations = new LSExpression[instance.nbMaxStations];
            for (int s = 0; s < instance.nbMaxStations; s++) {
                timeStations[s] = model.sum();
                for (int i = 0; i < instance.nbTasks; i++) {
                    LSExpression isTaskInStation = model.eq(assignedStation[i],s);
                    LSExpression timeForOneTask = model.prod(isTaskInStation, instance.processingTime[i]);
                    timeStations[s].addOperand(timeForOneTask);
                }
                LSExpression cycleTimeConstraint = model.leq(timeStations[s], instance.cycleTime);
                model.constraint(cycleTimeConstraint);
            }

            // The stations must respect the succession's order of the tasks
            for (int i = 0; i < instance.nbTasks; i++) {
                ArrayList<Integer> successors_i = instance.successors.get(i);
                for (int j : successors_i) {
                    LSExpression order = model.leq(assignedStation[i], assignedStation[j]);
                    model.constraint(order);
                }
            }

            // Minimization of the number of stations
            model.minimize(nbUsedStations);

            model.close();

            // Parametrize the solver
            localsolver.getParam().setTimeLimit(limit);
            // Initialize with a naive solution : each task belongs to one separate station
            for (int i = 0; i < instance.nbTasks; i++)
                assignedStation[i].setIntValue(i);

            localsolver.solve();
        }

        /* Write the solution in a file following the format:
        * - 1st line: value of the objective
        * - 2nd line: number of tasks
        * - following lines: task's number, station's number */
        void writeSolution(String fileName) throws IOException {
            try(PrintWriter output = new PrintWriter(new FileWriter(fileName))) {
                output.println(nbUsedStations.getIntValue());
                output.println(instance.nbTasks);
                for (int i = 0; i < instance.nbTasks; i++) {
                    output.print(i + 1);
                    output.print(",");
                    output.println(assignedStation[i].getIntValue() + 1);
                }
            }
        }
    }
    public static void main(String [] args) {
        if (args.length < 1) {
            System.err.println("Usage: AssemblyLineBalancing 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";
        try (LocalSolver localsolver = new LocalSolver()) {
            ALBInstance instance = new ALBInstance(instanceFile);
            ALBProblem model = new ALBProblem(localsolver, instance);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null)
                model.writeSolution(outputFile);
        }
        catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}