com.mhhe.clrs2e
Class AssemblyLine

java.lang.Object
  |
  +--com.mhhe.clrs2e.AssemblyLine

public class AssemblyLine

extends java.lang.Object

Implementation of assembly-line scheduling for two lines, as described in Section 15.1 of Introduction to Algorithms, Second edition. Because this is Java code, numbering starts from 0, so that the lines are 0 and 1 and station numbers are 0, 1, ..., n-1.

Field Summary

private double[][]	f The value of an optimal solution to a subproblem.
private double	fStar The fastest way to get all the way through the factory.
private int[][]	l The station used in an optimal solution to a subproblem.
private int	lStar The line whose station n is used in a fastest way through the factory.
private int	n The number of stations on each line.

Constructor Summary

AssemblyLine(double[][] a, double[][] t, double[] e, double[] x, int n)
Computes the fastest way through the factory, allocating the instance variables and storing the result in them.

Method Summary

private void	fastestWay(double[][] a, double[][] t, double[] e, double[] x, int n) Computes the fastest way through the factory, storing the result in the instance variables.
int[]	getFastestRoute() Returns the line numbers used in a fastest way through the factory.
double	getFastestTime() Returns the time taken by the fastest way to get all the way through the factory.
java.lang.String	toString() Returns the String representation of a fastest way through the factory.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

n

private int n

The number of stations on each line.

f

private double[][] f

The value of an optimal solution to a subproblem. f[i][j] is the fastest possible time to get from the starting point through station S_i,j, for i = 0, 1 and j = 0, 1, ..., n-1.

fStar

private double fStar

The fastest way to get all the way through the factory.

l

private int[][] l

The station used in an optimal solution to a subproblem. l[i][j] is the line number whose station precedes S_i,j on a fastest way from the starting point through station S_i,j, for i = 0, 1 and j = 0, 1, ..., n-1.

lStar

private int lStar

The line whose station n is used in a fastest way through the factory.

Constructor Detail

AssemblyLine

public AssemblyLine(double[][] a,
                    double[][] t,
                    double[] e,
                    double[] x,
                    int n)

Computes the fastest way through the factory, allocating the instance variables and storing the result in them.

Parameters:

a - a[i][j] is the assembly time at station S_i,j.

t - t[i][j] is the time to transfer from one assembly line to the other after going through station S_i,j.

e - e[i] is the entry time for line i, for i = 0, 1.

x - e[i] is the exit time for line i, for i = 0, 1.

n - The number of stations on each line.

Method Detail

fastestWay

private void fastestWay(double[][] a,
                        double[][] t,
                        double[] e,
                        double[] x,
                        int n)

Computes the fastest way through the factory, storing the result in the instance variables. The instance variables are assumed to be already allocated. Implements the Fastest-Way procedure on page 329.

Parameters:

a - a[i][j] is the assembly time at station S_i,j.

t - t[i][j] is the time to transfer from one assembly line to the other after going through station S_i,j.

e - e[i] is the entry time for line i, for i = 0, 1.

x - e[i] is the exit time for line i, for i = 0, 1.

n - The number of stations on each line.

getFastestTime

public double getFastestTime()

Returns the time taken by the fastest way to get all the way through the factory.

getFastestRoute

public int[] getFastestRoute()

Returns the line numbers used in a fastest way through the factory. Based on the Print-Stations procedure on page 330.

Returns:

An array, say r, such that station S_r[j],j is used in a fastest way through the factory.

toString

public java.lang.String toString()

Returns the String representation of a fastest way through the factory.

Overrides:

toString in class java.lang.Object