jobsequencing.c

job sequencing algo used for sequencing

#include<stdio.h>
#include<string.h>
#include<conio.h>

int totalProfit = 0 , *name , count = 0;

void read(int *array , int n)
{
     int i;
     for(i = 0;i<n;i++)
           scanf("%d",&array[i]);
}

void display(int *array , int n)
{
     int i;
     printf("\narray is : ");
     for(i = 0;i<n;i++)
          printf("%d ",array[i]);
}

void sortProfit(int *profit , int *deadline , int n)
{
     int i,j,temp;
     if(n <= 1)
          return;
     for(i=0;i<n;i++)
          for(j=0;j<n-i-1;j++)
          {
               if(profit[j] < profit[j+1])
               {
                    temp = profit[j];
                    profit[j] = profit[j+1];
                    profit[j+1] = temp;
                    
                    temp = deadline[j];
                    deadline[j] = deadline[j+1];
                    deadline[j+1] = temp;
                    
                    temp = name[j];
                    name[j] = name[j+1];
                    name[j+1] = temp;
               }
          }
}

void sortDeadline(int *deadline ,  int n)
{
     int i,j,temp;
     if(n <= 1)
          return;
     for(i=0;i<n;i++)
          for(j=0;j<n-i-1;j++)
          {
               if(deadline[j] > deadline[j+1])
               {
                    temp = deadline[j];
                    deadline[j] = deadline[j+1];
                    deadline[j+1] = temp;
               }
          }
}


void sortfinal(int *deadline , int *sol , int n)
{
     int i,j,temp;
     if(n <= 1)
          return;
     
     for(i=0;i<n;i++)
          for(j=0;j<n-i-1;j++)
          {
               if(deadline[sol[j]] > deadline[sol[j+1]])
               {
                    
                    temp = sol[j];
                    sol[j] = sol[j+1];
                    sol[j+1] = temp;
                    
               }
          }
          
}



int feasible(int *deadline , int n)
{
     int i,j;
     int *temp ;
     temp = (int *)malloc(n*sizeof(int));
     memcpy(temp,deadline,n*sizeof(int));
     display(temp,n);
     sortDeadline(temp , n);              //sort with respect to increasing deadline
     
     for(i=0;i<n;i++)
     {
          if(temp[i] - i <= 0)
          {     
                printf("\t :: not feasible");
                return 0;
          }
     }
     printf("\t :: feasible\n");
     printf("\nFeasible combination : ");
     display(temp,n);
     return 1;
}

void algo(int *profit , int *deadline , int *solution , int n)
{
      int i , maxDeadline = deadline[0] ;
      
      for(i=1;i<n;i++)
           if(maxDeadline < deadline[i])
                maxDeadline = deadline[i];
      
      int *temp;
      temp = (int *)malloc(n*sizeof(int));
      //solution[count++] = 0;
      //temp[0] = deadline[0];
      //totalProfit += profit[0];
      for(i = 0;i<n;i++)
      {
                 if(count < maxDeadline)
                 {
                          temp[count] = deadline[i];
                          solution[count++] = i;
                 
                          if(feasible(temp , count))
                                    totalProfit += profit[i];
                          else
                                    count--;     
                 }
      }
}



int main()
{
    
     int *deadline , *profit , n , *solution , i;
          
     printf("\n\nEnter no. of jobs : ");
     scanf("%d",&n);
     
     deadline = (int *)malloc(n*sizeof(int));
     profit = (int *)malloc(n*sizeof(int));
     solution = (int *)malloc(n*sizeof(int));
     name = (int *)malloc(n*sizeof(int));
     
     for(i=0;i<n;i++)
          name[i] = i+1;
    
     
     printf("\nEnter the deadlines of %d jobs : ",n);
     read(deadline , n);
     printf("\nEnter the profits of %d jobs : ",n);
     read(profit , n);
     
     sortProfit(profit , deadline , n);
     printf("\n\nThe Jobs are : \n\n");
     for(i=0;i<n;i++)
          printf("\nJob : %d\t profit : %d\tDeadline : %d",i , profit[i],deadline[i]);
     algo(profit , deadline , solution , n);
     
     printf("\n\n\nThe optimal Solution is :  \n");
     sortfinal(deadline , solution , count);
     for(i=0;i<count;i++)
           printf("\nJob : %3d \tProfit : %3d\tdeadline = %3d",solution[i],profit[solution[i]],deadline[solution[i]]);
     
     printf("\n\nTotal Profit = %d",totalProfit);
     
     getch();
     return 0;
}