Write a program that allows the user to enter the total number of jobs and then
ID: 3758890 • Letter: W
Question
Write a program that allows the user to enter the total number of jobs and then an ID number and a processing time for each job (at the command line).
The goal is to produce a schedule that tells what order the jobs should be done in to minimize the average completion time of all the jobs.
Ex. Input
Job ID
Processing Time
123
5
256
3
The correct order should be job 256 then job 123
completion time job 256 will be 3
completion time of job 123 will be 8
average completion time (3+8)/2 = 5.5
[If you did the longer job first the average completion time would be (5 + 8)/2 = 6.5]
In order to receive full credit, your algorithm must take O(nlogn) time.
Job ID
Processing Time
123
5
256
3
Explanation / Answer
Given an array of jobs where every job has a job id and associated processing time. How to maximize average completion time if only one job can be scheduled at a time.
Examples:
Input: Four Jobs with following deadlines and profits
JobID Processing time
123 5
256 3
Output: Following is maximum profit sequence of jobs
256
A Simple Solution is to generate all subsets of given set of jobs and check individual subset for feasibility of jobs in that subset. Keep track of maximum processing time among all feasible subsets. The time complexity of this solution is exponential.
This is a standard Greedy Algorithm problem. Following is algorithm.
1) Sort all jobs in decreasing order of processing time.
2) Initialize the result sequence as first job in sorted jobs.
3) Do following for remaining n-1 jobs
.......a) If the current job can fit in the current result sequence
without missing the processing time, add current job to the result.
Else ignore the current job.
The Following is C++ implementation of above algorithm.
// Program to find the maximum profit job sequence from a given array
// of jobs with deadlines and profits
#include<iostream>
#include<algorithm>
using namespace std;
// A structure to represent a job
struct Job
{
char id; // Job Id
int processingtime; // processing time if job is over before
};
// This function is used for sorting all jobs according to processing time
bool comparison(Job a, Job b)
{
return (a. processing time > b. processing time);
}
// Returns minimum number of platforms reqquired
void printJobScheduling(Job arr[], int n)
{
// Sort all jobs according to decreasing order of processing time
sort(arr, arr+n, comparison);
int result[n]; // To store result (Sequence of jobs)
bool slot[n]; // To keep track of free time slots
// Initialize all slots to be free
for (int i=0; i<n; i++)
slot[i] = false;
// Iterate through all given jobs
for (int i=0; i<n; i++)
{
// Find a free slot for this job (Note that we start
// from the last possible slot)
for (int j=min(n, arr[i].dead)-1; j>=0; j--)
{
// Free slot found
if (slot[j]==false)
{
result[j] = i; // Add this job to result
slot[j] = true; // Make this slot occupied
break;
}
}
}
// Print the result
for (int i=0; i<n; i++)
if (slot[i])
cout << arr[result[i]].id << " ";
}
// Driver program to test methods
int main()
{
Job arr[5] = { {123, 5}, {256, 3}};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Following is maximum processing time of jobs ";
printJobScheduling(arr, n);
return 0;
}
Time Complexity of the above solution is O(n2). It can be optimized to almost O(n) by using union-find data structure.
// Program to find the maximum profit job sequence from a given array
// of jobs with deadlines and profits
#include<iostream>
#include<algorithm>
using namespace std;
// A structure to represent a job
struct Job
{
char id; // Job Id
int processingtime; // processing time if job is over before
};
// This function is used for sorting all jobs according to processing time
bool comparison(Job a, Job b)
{
return (a. processing time > b. processing time);
}
// Returns minimum number of platforms reqquired
void printJobScheduling(Job arr[], int n)
{
// Sort all jobs according to decreasing order of processing time
sort(arr, arr+n, comparison);
int result[n]; // To store result (Sequence of jobs)
bool slot[n]; // To keep track of free time slots
// Initialize all slots to be free
for (int i=0; i<n; i++)
slot[i] = false;
// Iterate through all given jobs
for (int i=0; i<n; i++)
{
// Find a free slot for this job (Note that we start
// from the last possible slot)
for (int j=min(n, arr[i].dead)-1; j>=0; j--)
{
// Free slot found
if (slot[j]==false)
{
result[j] = i; // Add this job to result
slot[j] = true; // Make this slot occupied
break;
}
}
}
// Print the result
for (int i=0; i<n; i++)
if (slot[i])
cout << arr[result[i]].id << " ";
}
// Driver program to test methods
int main()
{
Job arr[5] = { {123, 5}, {256, 3}};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Following is maximum processing time of jobs ";
printJobScheduling(arr, n);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.