Scheduling: Theory, Algorithms and Systems

Chapter02 - Home
Exercises: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13 - 14 - 15 - 16 - 17 - 18 - 19 - 20 - 21 - 22 - 23

Exercise. This is the solution to exercise 2.1 in the book.

Solution. (a) We can implement the computation of the objective for each job permutation using the following C code:

 
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
 
int factorial(int n); 
void swap(int *x, int *y); 
void permute(int *a, int l, int r, int *k, int *perms); 
 
int job_weights[4]={6,11,9,5}; 
int job_times[4]={3,5,7,4}; 
 
int main(int argc, char **argv){ 
 
    int num_perm; 
    int num_jobs; 
    int *j; 
    int *p; 
    int *w; 
    int i,k=0; 
 
    int *perms; 
    int *objective_val; 
    int min_obj_val=RAND_MAX; 
    int cumul_time; 
 
    if (argc<2) 
        return 1; 
 
    num_jobs=atoi(argv[1]); 
 
    j=(int*)malloc(num_jobs*sizeof(int)); 
    p=(int*)malloc(num_jobs*sizeof(int)); 
    w=(int*)malloc(num_jobs*sizeof(int)); 
    for (i=0;i<num_jobs;i++){ 
        *(j+i)=i; 
        if (num_jobs==4) { 
            *(p+i)=job_times[i]; 
            *(w+i)=job_weights[i]; 
        } else { *(p+i)=rand()%10+1; 
            *(w+i)=rand()%20+1; 
        } 
 
    } 
 
    num_perm=factorial(num_jobs); 
 
    perms=(int*)malloc(num_perm*num_jobs*sizeof(int)); 
    objective_val=(int*)malloc(num_perm*sizeof(int)); 
 
    permute(j,0,num_jobs-1,&k,perms); 
 
    for (k=0; k<num_perm;k++) { 
        *(objective_val+k)=0; 
        cumul_time=0; 
        for (i=0;i<num_jobs;i++){ 
            cumul_time+=*(p+*(perms+num_jobs*k+i)); 
            *(objective_val+k)+=cumul_time*(*(w+*(perms+num_jobs*k+i))); 
        } 
        if (*(objective_val+k)<min_obj_val) 
            min_obj_val=*(objective_val+k); 
    } 
 
    for (k=0; k<num_perm; k++) { 
        printf("%3d:", k); 
        for (i=0;i<num_jobs;i++) { 
            printf("%d ", *(perms+k*num_jobs+i)); 
        } 
        printf("%d\n", *(objective_val+k)); 
    } 
    printf("MIN: %d\n", min_obj_val); 
 
    free(j); 
    free(p); 
    free(w); 
    free(perms); 
    free(objective_val); 
 
    return 0; 
} 
 
int factorial(int n) { 
    if (n<=1) 
        return 1; 
    else 
        return n*factorial(n-1); 
} 
 
void swap(int *x, int *y){ 
    int temp = *x; 
    *x=*y; 
    *y=temp; 
} 
 
void permute(int *a, int l, int r, int *k, int *perms) { 
   int i; 
   if (l == r) { 
     memcpy((perms+(r+1)*(*k)), a, (r+1)*sizeof(int)); 
     *k+=1; 
     /*printf("%2d:", *k); 
     for (i=0;i<(r+1);i++) { 
         printf("%d ", *(perms+(*k-1)*(r+1)+i)); 
     } 
     printf("\n");*/ 
   } else { 
       for (i = l; i <= r; i++) 
       { 
          swap((a+l), (a+i)); 
          permute(a, l+1, r, k, perms); 
          swap((a+l), (a+i)); //backtrack 
       } 
   } 
}

Running the code shows that the lowest objective job sequence is 2,1,3,4 with an objective function value of 333.

(b) In order to minimize the objective function the sum must contain the terms with larger weight at low values of cumulative completion time and terms with smaller weight at high values of cumulative completion time.

(c) In order to minimize the objective function which depends on the cumulative job completion time it is best to order jobs according to their processing time.

(d) In this case both metrics yield the correct result. Generic rule (ii) is in agreement with the arguments in (b) and (c) and is more suitable for various ranges of wi and pj.