What Is a Batch Job?

n jobs {1, 2,, n} are to be processed on two machines. Each job must be processed by machine 1 and then machine 2. The time required for machine 1 to process job i is ai, machine 2 The time required to process job i is bi (1in). The batch-job scheduling problem requires the determination of the optimal processing order for these n jobs, so that the first job is on machine 1. Processing starts and the minimum time required for the last job to finish processing on machine 2. (Remarks: This definition should be the description of "pipeline scheduling problem". The general keyword of "batch scheduling problem" is "time sum", not "time", so this project should be more appropriate to change the entry name Changed to "pipeline scheduling problem.")

Batch job scheduling problem

Obviously, an optimal scheduling of batch jobs should make machine 1 have no idle time and machine 2 has the least idle time. It can be proved that there is an optimal job scheduling so that jobs on machine 1 and machine 2 are completed in the same order. For example, there are three jobs {1, 2, 3}. The processing time for these three jobs on machine 1 is (2, 5, 4), and the processing time for machine 2 is (3, 2, 3). 1), there are 6 possible scheduling schemes for these three jobs: {(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), ( 3, 1, 2), (3, 2, 1)}, and the corresponding completion time is {12, 13, 12, 14, 13, 14}, as shown in Figure 8.8. Obviously, the best scheduling schemes are (1, 2, 3) and (2, 1, 3), and the shortest completion time is 12.

Suppose the array a [n] stores the processing time of n jobs on machine 1, and b [n] stores the processing time of n jobs on machine 2. The algorithm for solving the batch scheduling problem using the backtracking method is described in pseudo code as follows:

For the batch job scheduling problem, since the job schedule with the earliest completion time is to be found from all permutations of the n jobs, the solution space of the batch job scheduling problem is an arrangement tree, and the entire solution space tree is searched Can determine the optimal solution, so its time performance is O (n!). Compared with the brute force method to solve the batch scheduling problem, the search process can use the shortest completion time that has been obtained to perform pruning, so the search speed can be improved.

Let the array a [n] store the processing time of n jobs on machine 1, and the array b [n] store the processing time of n jobs on machine 2. The array x [n] stores the specific job schedule. During the initial iteration, x [0] indicates that the job is not scheduled, and x [k] indicates the number of the kth job. The array sum1 [n] stores the completion time of machine 1, and sum2 [n] stores the completion time of machine 2. At the initial iteration, sum1 [0] and sum2 [0] are both 0, indicating that the completion time is 0, and sum1 [k] Represents the current completion time of machine 1 after scheduling the kth job, and sum2 [k] represents the current completion time of machine 2 after scheduling the kth job. The algorithm of backtracking to solve batch job scheduling problem is described in C ++ language as follows:

int BatchJob (int a [], int b [], int n)

{

int i, k;

int x [10], sum1 [10], sum2 [10]; // assuming a maximum of 9 jobs

int bestTime = 1000; // Assuming the final completion time does not exceed 1000

for (i = 1; i <= n; i ++) // Initialize scheduling

{

x [i] = -1;

sum1 [i] = 0; sum2 [i] = 0;

}

sum1 [0] = 0; sum2 [0] = 0; // Used when starting scheduling (initial iteration)

k = 1; // Schedule the first job

while (k> = 1)

{

x [k] = x [k] + 1; // Schedule the kth job, x [k] is the job number

while (x [k] <n)

{

for (i = 1; i <k; i ++) // Check if the job x [k] is repeated

if (x [i] == x [k]) break;

if (i == k) {// Job x [k] has not been processed

sum1 [k] = sum1 [k-1] + a [x [k]];

if (sum1 [k]> sum2 [k-1]) sum2 [k] = sum1 [k] + b [x [k]];

else sum2 [k] = sum2 [k-1] + b [x [k]];

if (sum2 [k] <bestTime) break; // The current minimum time has been exceeded, pruning

else x [k] = x [k] + 1;

}

else x [k] = x [k] + 1; // Job x [k] has been processed, try the next job

}

if (x [k] <n && k <n)

k = k + 1; // schedule the next job

else {

if (x [k] <n && k == n) // Get a job schedule

if (bestTime> sum2 [k]) {

bestTime = sum2 [k];

cout << "The shortest current job schedule is:";

for (int j = 1; j <= n; j ++)

cout << x [j] + 1 << ""; // The subscript starts from 0, and the print job number starts from 1.

cout << "The shortest time is:" << bestTime << endl;

}

x [k] = -1; k = k-1; // reset x [k], backtrack

}

}

return bestTime;

}