Assume you have a scheduling problem with 10 customers. Customer i has value Vi,

Question

Assume you have a scheduling problem with 10 customers. Customer i has value Vi, and requires processing time Ti.

The values of Vi and Ti are listed below as arrays:

V = { 6, 25, 4, 1, 7, 3, 12, 1, 1, 8 }

T = { 2, 5, 1, 4, 4, 9, 1, 5, 3, 16 }

Assume that jobs can be scheduled partially, so that a job of value Vi which requires time Ti will receive value, x Vi , if processed only for time, t = x Ti, for a fraction, 0 ? x ?1.

(a) Find the maximum value which can be scheduled with total processing time T = 30 units.

(b) Let T take on value T = 1,

Explanation / Answer

(a)

Algorithm :

1. We totally consume Jobs with higher values (in sorted order) before moving on to lower value Jobs

2. If we don't have time to complete a Job, we partially complete it and then stop.

--------------------------------------------------------------------------------------------------------------------------------------

Code :

#include <cstdio>
#include <algorithm>
using namespace std;

struct Job {
   int V;
   int T;
};

struct JobComparator {
   bool operator() (const Job & i, const Job & j) {
       return ( i.V >= j.V );
   }
} JobComparatorObject;

double maxValue(struct Job sortedJobs[], int T) {
   int T_remain = T;
   double total_value = 0.0;
   for(int i=0; i < 10; ++i) {
       if(T_remain < sortedJobs[i].T) {
           total_value += (sortedJobs[i].V * ((double)T_remain) / sortedJobs[i].T);
           break;
       }
       else {
           total_value += sortedJobs[i].V;
           T_remain -= sortedJobs[i].T;
       }
   }
   return total_value;
}

int main() {
   int V[] = { 6, 25, 4, 1, 7, 3, 12, 1, 1, 8 };
   int T[] = { 2, 5, 1, 4, 4, 9, 1, 5, 3, 16 };
  
   struct Job Jobs[10];
  
   for(int i=0; i<10; ++i) {
       Jobs[i].V = V[i];
       Jobs[i].T = T[i];
   }
  
   // sort Jobs by value (highest Value is first)
   sort(Jobs, Jobs + 10, JobComparatorObject);
  
   // now we totally consume Jobs with higher values before moving on to lower value Jobs
  
   for(int t = 1; t <= 50; ++t) {
       printf("Time = %d Value = %lf ", t, maxValue(Jobs, t));
   }
   return 0;
}

--------------------------------------------------------------------------------------------------------------------------------------

Above code prints Max Values for all T = 1, ... 50

For part (a)

Maximum value = 62.3333

--------------------------------------------------------------------------------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.