Job Sequencing Problem | Set 1 (Greedy Algorithm) - GeeksforGeeks
Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.
http://www.geeksforgeeks.org/job-sequencing-using-disjoint-set-union/
Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.
1) Sort all jobs in decreasing order of profit.
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 deadline, add current job to the result.
Else ignore the current job.
structJob{charid;// Job Idintdead;// Deadline of jobintprofit;// Profit if job is over before or on deadline};// This function is used for sorting all jobs according to profitboolcomparison(Job a, Job b){return(a.profit > b.profit);}
// Returns minimum number of platforms reqquiredvoid printJobScheduling(Job arr[], int n){ // Sort all jobs according to decreasing order of prfit 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 << " ";}http://www.geeksforgeeks.org/job-sequencing-using-disjoint-set-union/
The costly operation in the Greedy solution is to assign a free slot for a job. We were traversing each and every slot for a job and assigning the greatest possible time slot(<deadline) which was available.
What does greatest time slot means?
Suppose that a job J1 has a deadline of time t = 5. We assign the greatest time slot which is free and less than the deadline i.e 4-5 for this job. Now another job J2 with deadline of 5 comes in, so the time slot allotted will be 3-4 since 4-5 has already been allotted to job J1.
Suppose that a job J1 has a deadline of time t = 5. We assign the greatest time slot which is free and less than the deadline i.e 4-5 for this job. Now another job J2 with deadline of 5 comes in, so the time slot allotted will be 3-4 since 4-5 has already been allotted to job J1.
Why to assign greatest time slot(free) to a job?
Now we assign the greatest possible time slot since if we assign a time slot even lesser than the available one than there might be some other job which will miss its deadline.
Now we assign the greatest possible time slot since if we assign a time slot even lesser than the available one than there might be some other job which will miss its deadline.
Using Disjoint Set for Job Sequencing
All time slots are individual sets initially. We first find the maximum deadline of all jobs. Let the max deadline be m. We create m+1 individual sets. If a job is assigned a time slot of t where t => 0, then the job is scheduled during [t-1, t]. So a set with value X represents the time slot [X-1, X].
We need to keep track of the greatest time slot available which can be allotted to a given job having deadline. We use the parent array of Disjoint Set Data structures for this purpose. The root of the tree is always the latest available slot. If for a deadline d, there is no slot available, then root would be 0. Below are detailed steps.
All time slots are individual sets initially. We first find the maximum deadline of all jobs. Let the max deadline be m. We create m+1 individual sets. If a job is assigned a time slot of t where t => 0, then the job is scheduled during [t-1, t]. So a set with value X represents the time slot [X-1, X].
We need to keep track of the greatest time slot available which can be allotted to a given job having deadline. We use the parent array of Disjoint Set Data structures for this purpose. The root of the tree is always the latest available slot. If for a deadline d, there is no slot available, then root would be 0. Below are detailed steps.
class DisjointSet{ int parent[]; // Constructor DisjointSet(int n) { parent = new int[n + 1]; // Every node is a parent of itself for (int i = 0; i <= n; i++) parent[i] = i; } // Path Compression int find(int s) { /* Make the parent of the nodes in the path from u--> parent[u] point to parent[u] */ if (s == parent[s]) return s; return parent[s] = find(parent[s]); } // Makes u as parent of v. void merge(int u, int v) { //update the greatest available //free slot to u parent[v] = u; }}class Job implements Comparator<Job>{ // Each job has a unique-id, profit and deadline char id; int deadline, profit; // Constructors public Job() { } public Job(char id,int deadline,int profit) { this.id = id; this.deadline = deadline; this.profit = profit; } // Returns the maximum deadline from the set of jobs public static int findMaxDeadline(ArrayList<Job> arr) { int ans = Integer.MIN_VALUE; for (Job temp : arr) ans = Math.max(temp.deadline, ans); return ans; } // Prints optimal job sequence public static void printJobScheduling(ArrayList<Job> arr) { // Sort Jobs in descending order on the basis // of their profit Collections.sort(arr, new Job()); // Find the maximum deadline among all jobs and // create a disjoint set data structure with // maxDeadline disjoint sets initially. int maxDeadline = findMaxDeadline(arr); DisjointSet dsu = new DisjointSet(maxDeadline); // Traverse through all the jobs for (Job temp : arr) { // Find the maximum available free slot for // this job (corresponding to its deadline) int availableSlot = dsu.find(temp.deadline); // If maximum available free slot is greater // than 0, then free slot available if (availableSlot > 0) { // This slot is taken by this job 'i' // so we need to update the greatest free // slot. Note that, in merge, we make // first parameter as parent of second // parameter. So future queries for // availableSlot will return maximum slot // from set of "availableSlot - 1" dsu.merge(dsu.find(availableSlot - 1), availableSlot); System.out.print(temp.id + " "); } } System.out.println(); } // Used to sort in descending order on the basis // of profit for each job public int compare(Job j1, Job j2) { return j1.profit > j2.profit? -1: 1; }}
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 profit among all feasible subsets. The time complexity of this solution is exponential.
Read full article from Job Sequencing Problem | Set 1 (Greedy Algorithm) - GeeksforGeeks