Assembly line scheduling

Question

This is solution to the assembly line problem. Here is complete description, which is too big and verbose to re-describe. I apologize for the inconvenience of the hyperlink.

Note: I do understand merits of unit testing in separate files. But deliberately added it to main method for personal convenience, so I request that you not consider that in your feedback.

I'm looking for request code review, optimizations and best practices.

final class Station {

    private final int stationTime;
    private final int transtionToTime; // time to transition`to` this station
    private final int transitionFromTime; // time to transitition `from` this station.

    public Station(int stationTime, int transitionTime, int transitionFromTime) {
        this.stationTime = stationTime;
        this.transtionToTime = transitionTime;
        this.transitionFromTime = transitionFromTime;
    }

    public int getStationTime() {
        return stationTime;
    }

    public int getTransitionToTime() {
        return transtionToTime;
    }

    public int getTransitionFromTime() {
        return transitionFromTime;
    }
}

public final class AssemblyLine {

    private AssemblyLine() {}

    /**
     * Given an assembly line, outputs the shortest time needed to go through it.
     * The input data structures are not expected to be changed by client.
     * 
     * @param line1     the assembly line 1
     * @param line2     the assumbly line 2
     * @return          the minumum time needed to process the item.
     */
public static int assemblyLineShortestTime(List<Station> line1, List<Station> line2) {
    int prevLine1Min = line1.get(0).getStationTime() + line1.get(0).getTransitionToTime(); 
    int prevLine2Min = line2.get(0).getStationTime() + line2.get(0).getTransitionToTime(); 
    for (int i = 1; i < line1.size(); i++) {
        int currentLine1Min = line1.get(i).getStationTime() + Math.min(prevLine1Min, prevLine2Min + line1.get(i).getTransitionToTime());
        int currentLine2Min = line2.get(i).getStationTime() + Math.min(prevLine1Min + line2.get(i).getTransitionToTime(), prevLine2Min);

        prevLine1Min = currentLine1Min;
        prevLine2Min = currentLine2Min;
    }
    return Math.min(prevLine1Min + line1.get(line1.size() - 1).getTransitionFromTime(), prevLine2Min + line2.get(line2.size() - 1).getTransitionFromTime()); 
}

    public static void main(String[] args) { 

        List<Station> line1 = new ArrayList<Station>(); 
        line1.add(new Station(4, 10, 7));
        line1.add(new Station(5,  9, 4));
        line1.add(new Station(3,  2, 5));
        line1.add(new Station(2,  8, 18));

        List<Station> line2 = new ArrayList<Station>(); 
        line2.add(new Station( 2, 12, 9));
        line2.add(new Station(10,  7, 2));
        line2.add(new Station( 1,  4, 8));
        line2.add(new Station( 4,  5, 7)); 

        assertEquals(35, assemblyLineShortestTime(line1, line2));
    }
}

Answer 1

The code implementing the core algorithm is very cumbersome. This is partly due to shoehorning the line entry/exit times into the first/last stations as evidenced by some internal stations in your tests having unusable exit times. But the code duplication doesn't help either.

Note: The diagram shows the transition time belonging to the station being transitioned from. Your code uses the transition time from the station on the other line. I'm going with the diagram as it seems cleaner to me.

Store the current stations into local variables to avoid having to read .get(0) and .get(i) many times. Also, when you name variables identically except for 1 and 2 (unavoidable in this method), don't hide the numbers in the middle of the names. Finally, since all these time-based local variables are for line X and track minimum times, drop Line and Min from their names.

public static int assemblyLineShortestTime(List<Station> line1, List<Station> line2) {
    return assemblyLineShortestTime(line1.iterator(), line2.iterator());
}

private static int assemblyLineShortestTime(Iterator<Station> line1, Iterator<Station> line2) {
    Station station1 = line1.next();
    Station station2 = line2.next();
    int prev1 = station1.getStationTime() + station1.getTransitionToTime(); 
    int prev2 = station2.getStationTime() + station2.getTransitionToTime(); 
    while (line1.hasNext()) {
        station1 = line1.next();
        station2 = line2.next();
        int curr1 = station1.getStationTime() + Math.min(prev1, prev2 + station2.getTransitionToTime());
        int curr2 = station2.getStationTime() + Math.min(prev2, prev1 + station1.getTransitionToTime());

        prev1 = curr1;
        prev2 = curr2;
    }
    return Math.min(prev1 + station1.getTransitionFromTime(), prev2 + station2.getTransitionFromTime()); 
}

While the code duplication seems much worse with those temporary variables, the logic is more apparent to me. The real problem is that there's no logic inside Station. If you add the line number to Station and added some helper methods, you could clean up that code a bit.

private static int assemblyLineShortestTime(Iterator<Station> line1, Iterator<Station> line2) {
    Station station1 = line1.next();
    Station station2 = line2.next();
    int prev1 = station1.start();
    int prev2 = station2.start();
    while (line1.hasNext()) {
        station1 = line1.next();
        station2 = line2.next();
        int curr1 = station1.proceed(prev1, prev2);
        int curr2 = station2.proceed(prev2, prev1);
        prev1 = curr1;
        prev2 = curr2;
    }
    return Math.min(prev1 + station1.exit(), prev2 + station2.exit()); 
}

class Station {
    public int start() {
        return stationTime + transitionToTime;
    }

    public int proceed(thisLineTime, otherLineTime) {
        // The transitionToTime here is not the correct one,
        // but this demonstrates the technique
        return stationTime + Math.min(thisLineTime, otherLineTime + transitionToTime);
    }

    public int exit() {
        return transitionFromTime;
    }
}

These small refactorings improve the readability only a little, but they don't alter it significantly. The real gains will require expanding the model and moving away from a single, static method.

Starting Over

If you're going to model the stations with classes to solve this, go all in and model the lines and entry/exit times properly to avoid confusion.

class Station
    int runTime - time to process this station
    int switchTime - time to switch lines

class Line
    List<Station> stations
    int entryTime - time to enter this line
    int exitTime - time to exit this line

Next model the location along the lines.

class Location
    Line line - which line are we on
    Station station - which station did we just go through
    int totalTime - elapsed time to reach this location

This design will allow moving the bulk of the algorithm into the model. You may not even need to model the lines themselves if you store the next stations in each station.

class Station
    int runTime - time to process this station
    Station next - next station on the same line
    Station otherNext - next station on the other line
    int switchTime - time to switch lines