Backtracking method to solve batch job scheduling problem

alas , This is the beginning of a failure . however , I'm not afraid of failure ！ Go to bed a little later today , Because I sleep more at noon ~ Recently, I was taught by teacher Wang Xiaodong 《 Computer algorithm design and analysis 》（ The first 4 edition ） It's a hell of a torture . Won't say something elegant , It's true . Based on differential , Not only will I forget what I learned , And I thought I could never do something , Now you can understand it with a little look . How arrogant people are ！ I don't say much nonsense . Put the original question first .

One 、 problem

Given n A collection of jobs J={J1,J2,...,Jn}. Every assignment Ji There are two tasks, respectively 2 Complete... On this machine . Each operation must be carried out by the machine first 1 Handle , Then the machine 2 Handle . Homework Ji We need machines j Of The processing time is tji,i=1,2,...,n;j=1,2. For a certain job scheduling , set up Fji It's homework i In the machine j Last time the processing is completed . Then all operations are on the machine 2 Time and f=F2i The sum of call Schedule the completion and .

Batch job scheduling problem requires for a given n Homework , Make the best job scheduling plan , Make it complete in the shortest time .

no way , I can't fix this form . Don't do it first . I'll put the code first .

Two 、 Code

</pre><pre name="code" class="html"> Batch job scheduling class FlowShop<pre name="code" class="java">

/** * Problem description ： * Given n A collection of jobs J={J1,J2,...,Jn}. Every assignment Ji There are two tasks, respectively 2 Complete... On this machine . Each operation must be carried out by the machine first 1 Handle , Then the machine 2 Handle . Homework Ji We need machines j Of * The processing time is tji,i=1,2,...,n;j=1,2. For a certain job scheduling , set up Fji It's homework i In the machine j Last time the processing is completed . Then all operations are on the machine 2 Time and f=F2i Sum of * Schedule the completion and . * Batch job scheduling problem requires for a given n Homework , Make the best job scheduling plan , Make it complete in the shortest time . * @author noonTree * */public class FlowShop {static int Max = 200;static int M[][];// Processing time required for each operation static int[] x;// Current job schedule static int[] bestx;// Current optimal job scheduling static int[] f2;// machine 2 Processing time completed static int f1;// machine 1 Time to complete processing static int f;// Completion time and static int bestf;// The current optimal value static int n;// Number of assignments void BackTrack(int i){if(i > n){//n Secondary cycle , Let the current optimal scheduling be bestx[] For the current optimal scheduling x[]for(int j = 1;j <= n;j++)bestx[j] = x[j];// The current optimal values are completion time and bestf = f;}else{/*i To n The cycle of time *j Used to indicate which task is selected （ That is, the order of execution ） tb(0) Came in , No matter how recursive , There is j=1,2,3 These three processes , So it must be able to traverse completely （ I copied this sentence from someone else ） */for(int j = i;j <= n;j++){//f1 Equal to the i The time of the first job on the first machine is added f1 += M[x[j]][1];/*f2 There are two situations ： * (1) If the last job spent more time on the second machine than the next job on machine one , Then the current job time is equal to the last job on the machine 2 Time spent plus current job * In the machine 2 Time spent ; * (2) If it's less than , Then the current job is equal to the machine 1 The completion processing time plus the current job on the machine 2 Time spent . */f2[i] = ((f2[i - 1] > f1)? f2[i - 1]:f1) + M[x[j]][2];// The total time is equal to working on the machine 2 Action time on f += f2[i];// If the total time is less than the optimal value, there is ：if(f < bestf){// Exchange job scheduling at this time Swap(x,i,j);// Go back to i+1BackTrack(i + 1);// Backtracking doesn't understand ！！！// Exchange job scheduling at this time Swap(x,i,j);}// When backtracking is complete , Current machine 1 The processing time is equal to the last machine 1 The completion processing time minus the current xf1 -= M[x[j]][1];f -= f2[i];}}}void Swap(int[] x, int i, int j) {int temp = x[j];x[j] = x[i];x[i] = temp;}int Flow(int[][] MM,int nn,int bbestx[]){int ub = Max;// What is it? ? Determine a maximum n = nn;M = MM;x = new int[n + 1];f2 = new int[n + 1];bestx = bbestx;bestf = ub;f1 = 0;f = 0;for(int i = 0;i <= n;i++){f2[i] = 0;x[i] = i;}BackTrack(1);return bestf;}}

Test class TestFlowShop

import java.util.Scanner;

public class TestFlowShop {

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		System.out.printf("\t Batch job scheduling \n");
		System.out.print(" Enter the number of jobs ：");
		int n = input.nextInt();
		System.out.println(" Enter the processing time required for each job ：");
		// Let array subscript from 1 Start entering data , Line zero no 
		int M[][] = new int[n + 1][3];
		for(int i = 1;i <= n;i++){
			for(int j = 1;j < 3;j++){
				M[i][j] = input.nextInt();
			}
		}
		// Current optimal scheduling 
		int bestx[] = new int[n + 1];
		FlowShop Fls = new FlowShop();
		// The current optimal value 
		int bestf = Fls.Flow(M,n,bestx);
		System.out.print(" Output the current optimal scheduling ：");
		for(int i = 1;i <= n;i++){
			if(i != n){
				System.out.print(bestx[i] + " ");
			}else{
				System.out.print(bestx[i]);
			}
		}
		System.out.println();
		System.out.print(" Output the current optimal value ：" + bestf);
		
		
	}

}
/* What happened ：
 * （1） Use when variables are not initialized 
 * （2） It's killing me , Position of subscript , I'm sick of it . I just can't see . I think that's it . It's uncomfortable to be laughed at when you say it , Maybe this is where I don't know how to adapt . however , I won't admit defeat . In self-control ,
 *  I   There are advantages .
 * （3） I also found a problem , Why does it show up （1） What about the situation ？ Because in C++ The methods of , In the method outside the class, use the method of the class to declare this class , Then default two variables with the same name , Of course, it is called by default 
 *  It is the variable of the current method, not the variable in the class , The variable to call the class is “ Class name . Method ”. I don't understand this , So I took a detour . It's just , This is also a big lesson ！！
 * */