# The Three-machine proportionate flow shop problem with unequal machine

As part of an Academic project I wrote the following code, according to the algorithm (verbal). When I checked the rest of the article I notice that the efficiency should be $O(n^2)$ and I wrote $O(n)$.

I know that I didn't finish and that there is much to do. I'm putting my code and article here and wishing to get some way with that or even an answer.

I've attached a link to the article on my college server (a PDF file only the third page relevant the rest is abstract and reducing): the article

I have a merge-sort object but it irrelevant here as it worked.

Job class:

public class Job{
private String name;// contain the name of the job(optional)
private int num;//contain the serial number of the job
private int duration;// contain the processing time of the job
private double start;//contain the starting time of the job
private double end;//contain the ending time of the job

public Job(){

this.num = 0;
this.duration = 0;
this.start = 0;
this.end = 0;

}//end of empty constructor

public Job(int num, int duration){

this.num = num;
this.duration = duration;

}//end of constructor

public void setNum(int num){
this.num = num;
}//end of setNum method

public int getNum(){
return this.num;
}//end of getNum method

public void setDuration(int duration){
this.duration = duration;
}//end of setDuration method

public int getDuration(){
return this.duration;
}//end of getDuration method

public void setName(String name){
this.name = name;
}//end of setName method

public String getName(){
return this.name;
}//end of getName method

public void setEnd(double end){
this.end = end;
}//end of setEnd method

public double getEnd(){
return this.end;
}//end of setEnd method

public void setStart(double start){
this.start = start;
}//end of setEnd method

public double getStart(){
return this.start;
}//end of setEnd method

public String toString(){
String str = "Job number is: " + getNum() + ", " +"and the duriation is: " + getDuration();
return str;
}//end of toString method

}//end of class


Main class:

import java.util.*;

import javax.swing.text.MaskFormatter;

public class assemblyLine{

public static void main(String[]args){
Scanner in = new Scanner(System.in);
double rateTime;
int numOfJobs;
Job []job_order;
MergeSort sorter = new MergeSort();

//getting input from the user
do{
System.out.println("please enter Rate-Time:");
rateTime = in.nextDouble();
}while(rateTime <=0 || rateTime >1);
do{
System.out.println("Enter how many Jobs do you have: ");
numOfJobs = in.nextInt();
}while(numOfJobs <=0);
System.out.println("Attention!!! Please enter the processing time of all jobs" + "\n" + "Note: please insert the same times unit! ");
System.out.println();
job_order = new Job[numOfJobs];//define an array
//Vector<Job>[][] p_Matrix = new Vector[numOfJobs];//define vector matrix
for(int i=0; i<job_order.length ;i++){
System.out.println("please enter the processing time of job " +(i+1) +":");
job_order[i] = new Job((i+1),in.nextInt());
}//end of input loop

sorter.sort(job_order);
job_order = sorter.sendBackSortedArr();
//don't need to sort anymore! need to release memory for the calculation!!!
sorter = null;
System.gc();

for(int i=0;i<job_order.length;i++){
System.out.println(job_order[i]);
}

if(numOfJobs == 1)
System.out.println("\n" +"Note: Only One Job!!!" +"\n" + "The Makespan is: " +((job_order.getDuration()*2) + (job_order.getDuration()/rateTime)) +"[time-units]");
else{

Vector<Job> solution =  new Vector<Job>();//this is the vector that will keep the optimum job order of the machines
solution.add(job_order);//adding the first job
//double t1end,t2,t2end, makeSpan;
double t1,t2, makeSpan;
//in this part we calculate the durations and the start and the end of each machine/job as a preparation for the calculate

makeSpan = 2*job_order.getDuration() + (job_order.getDuration()/rateTime);
t1 = job_order.getDuration();
t2 = t1;

int switcher=0;

for(int i=0; i <job_order.length;i++){
double rightGap, leftGap, helper =0;

if((t1 >= job_order[i].getDuration()) && (t2 >= job_order[i].getDuration())){
helper = Math.min(leftGap = makeSpan + job_order[i].getDuration(),rightGap = makeSpan + job_order[i].getDuration());
if(leftGap == helper)
switcher =1;
else if(rightGap == helper)
switcher =3;
}//end of if condition - first at the function

else if((t1 <job_order[i].getDuration()) && (t2 >= job_order[i].getDuration())){
helper = Math.min(leftGap = makeSpan + job_order[i].getDuration() + (job_order[i].getDuration()/rateTime) - t1,rightGap = makeSpan + job_order[i].getDuration());
if(leftGap == helper)
switcher =2;
else if(rightGap == helper)
switcher =3;
}//end of else-if condition - second at the function

else if((t1 >= job_order[i].getDuration()) && ((t2) < job_order[i].getDuration())){
helper = Math.min(leftGap = makeSpan + job_order[i].getDuration(),rightGap =  makeSpan + job_order[i].getDuration() + (job_order[i].getDuration()/rateTime) -(makeSpan -t2));
if(leftGap == helper)
switcher =1;
else if(rightGap == helper)
switcher =4;
}//end of else-if condition - third at the function

else if((t1 < job_order[i].getDuration()) && (t2 < job_order[i].getDuration())){
helper = Math.min(leftGap = makeSpan + job_order[i].getDuration() + (job_order[i].getDuration()/rateTime) - t1 ,rightGap = makeSpan + job_order[i].getDuration() + (job_order[i].getDuration()/rateTime) -t2);
if(leftGap == helper)
switcher =2;
else if(rightGap == helper)
switcher =4;
}//end of else-if condition - fourth at the function

if(switcher ==1){
solution.add(0, job_order[i]);
makeSpan +=job_order[i].getDuration();
t1 = t1 - (job_order[i].getDuration()/rateTime)+ job_order[i].getDuration();
}//end of "if" condition by first dot!

else if(switcher ==2){
solution.add(0, job_order[i]);
t1 = job_order[i].getDuration();
makeSpan+= (job_order[i].getDuration()/rateTime)+ job_order[i].getDuration() -t1;
}//end of "else-if" condition by second dot!

else if(switcher ==3){
solution.add(job_order[i]);
t2 =t2 -(job_order[i].getDuration()/rateTime)+job_order[i].getDuration();
makeSpan +=job_order[i].getDuration();
}//end of "else-if" condition by third dot!

else if(switcher ==4){
solution.add(job_order[i]);
t2+= job_order[i].getDuration();
makeSpan +=(job_order[i].getDuration()/rateTime)+job_order[i].getDuration()-t2;

}//end of "else-if" condition by fourth dot!

}//end of for loop
System.out.println();
System.out.print("The Makespan is: "+makeSpan +"[time-units]"+ "\n"+"flow: [");
for(int i=0; i<solution.size()-1;i++)
System.out.print(solution.elementAt(i).getDuration()+",");
System.out.print(solution.elementAt(solution.size()-1).getDuration()+"]");
System.out.println(t1);

}//end of else - more then one job

}//end of main

//this method should return a matrix with the job schedule and the processing time of every job at all machine
public static Job[][] createingP(Vector<Job> solution, int numOfJobs, double rateTime,double t1){
Job schedule[][] = new Job[numOfJobs];

return schedule;
}//end of creatingP method
/*
public string toString(){
String str = "\n" + "The Makespan is: "+makeSpan +"[time-units]"+ "\n"+"flow: ["
System.out.println();
System.out.print("The Makespan is: "+makeSpan +"[time-units]"+ "\n"+"flow: [");
for(int i=0; i<solution.size()-1;i++)
System.out.print(solution.elementAt(i).getDuration()+",");
System.out.print(solution.elementAt(solution.size()-1).getDuration()+"]");
}//end of toStringmethod
*/

}//end of class

/*
//calculates the new makespans options
boolean t1Biggest, t2Biggest;
double option1 = makeSpan + job_order[i].getDuration();
double option2 = makeSpan + job_order[i].getDuration() + (job_order[i].getDuration()/rateTime);
double option3 = makeSpan + job_order[i].getDuration();
double option4 = makeSpan + job_order[i].getDuration() + (job_order[i].getDuration()/rateTime) - t2;
*/

• That link is not working for me (server is taking too long to respond) – rolfl Jun 16 '14 at 18:39
• Iv'e checked again and it's work fine for me if you'll give me an address of any platform I can send it to you directly – user3446659 Jun 16 '14 at 20:49
• Well, I am not about to suggest you send anything to me, or anyone else, but, it is not just me that has a problem with it. – rolfl Jun 16 '14 at 21:58

## 2 Answers

• Don't ever call System.gc(). It probably won't even do anything, and if it does, it will most likely be less efficient than what Java does by default.

• Don't use Vector, but List instead. Vector has been somewhat deprecated for over a decade.

• Break things down in methods. A rule of thumb is that a method should not be more 10 lines long. It's not a rule that I always follow, but your method is much too long.

• Even better than breaking things down in methods, is to break them down by classes (object-oriented programming). You need to think about what goes on in your code and break things in semi-independent logically-consistent entities. It is actually not trivial to get this decomposition right, but it comes with experience. For example, you should define a main class which will take the input parameters as its constructor argument. Then you have a method that reads the user inputs and instantiate the main object.

• The for-loop with switcher is much too long. You could define one method that takes the parameters t1, t1, i and compute the value of switcher from those. Then you can have a method that reads in the switch value and modifies the member values of your object accordingly. (I'm not sure what exactly the object should be, but you can think about that.)

• Still working thank for the advises so far – user3446659 Jun 16 '14 at 21:40

There's some stuff to comment on in your code, so I'll just go ahead and take the comments , the empty constructor and your input reading:

### Comments:

private String name;// contain the name of the job(optional)
private int num;//contain the serial number of the job
private int duration;// contain the processing time of the job
private double start;//contain the starting time of the job
private double end;//contain the ending time of the job


About everything in these comments can be dumped. the only thing that is useful here is (optional). the rest is explicitly or implicitly given by code.

Instead something like this would have been enough:

private String name; //optional
private int serialNumber;
private int duration;
private double start;
private double end;


But let's stop here for a second and have an <interjection>:

start is a double, as well as end. Why in god's name is duration an int then?
And much more important, what unit are you working in? Days, Hours, Minutes, Weeks, Years, [...]?

</interjection>

Moving swiftly on:

} // end of empty constructor


I personally strongly dislike this comment style, as it is a . There should not be a need to explicitly write into comments, which brace closes which block. If you need to do this, your code is too complex and needs refactoring. For a nice help on reducing indentation levels you might want to read through Jeff's blogpost on "arrow code". To summarize in short: extract functions and guard clauses.

And on we go ;)

//don't need to sort anymore! need to release memory for the calculation!!!
sorter = null;


This is a quite big code-smell. While this may be true for low-level languages like / that is about useless in Instead you should move the sorting to a separate method and let the garbage collector do that for you.

The GC is a very nice feature that allows you to just end a function without having to fear you got a memory leak (as long as you don't use AutoClosable resources, but we leave that aside for now). It collects and frees unused variables in the JVM for you, so you don't have to be bothered with free variable or variable = null and the like.

### Empty Job Constructor:

What bothers me most about this piece of code is, that it's totally useless for the given assignment. Yea I know, from everywhere it shouts: "Implement the default constructor!" but IMO that's sometimes even counterproductive.

Instead you shouldn't allow instantiation of a job without values here. How? Just remove the constructor, and you're good to go ;)

Why? What sense does a job make, that has no serial number and no duration?

### Reading Input From The User or: How To Write A Main-Method:

To make it short: Your main method is doing everything, and that in probably the most possible way :(

Here is another answer of mine, that should show the general problem in your main method, as well as one on parsing user input

I will sum these up here shortly either way:

Your main method is cramped with everything your program does. That's why it is so long and complicated and difficult to read. You should extract functionality out of your main-method into smaller parts. In the end your main method could read like this:

public static void main(String[] args) {
Job[] allJobs = readUserInput();
Solution bestSolution = calculateSolution(allJobs);
System.out.println(bestSolution.toString());
}


In one of the other answers I mentioned I have created a IMO very nice prompting method, which I slightly modified for here:

private String promptUserForInput(String prompt, Scanner in){
System.out.println(prompt);
return in.nextLine();
}


This is about the simplest way to extract the prompting into a method, if you want to keep it reusable.

Now to check for validity you'd need to do something like:

private int promptForNumberOfJobs () {
String PROMPT = "Enter how many Jobs you have:";
String userInput;
int result;
while (true) {
userInput = promptUserForInput(PROMPT, new Scanner(System.In));
try {
result = Integer.parseInt(userInput);
if(result >= 0){
break;
}
else {
System.out.println("The number of jobs must be 0 or larger");
}
} catch (NumberFormatException ex) {
System.out.println("Input is not a valid number.");
}
}
return result;
}


I am confident you can get your code much more readable when following this advice, and I hope to see you again here on CodeReview, possibly with a follow up, as I haven't touched some aspects of your code that still need it :(