Customer Support: email@example.com
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
- If you are a student, email to firstname.lastname@example.org to get special student discount.
Job Scheduling Problems are a very common category of problems often seen in both coding interviews as well as in academia (assignments, tests).
Job Scheduling Problems can be broadly categorized in three types:
- Sequential Jobs Scheduling with precedence
- Parallel Jobs Scheduling with Precedence
- Parallel Jobs Scheduling with Precedence and Relative Deadlines
Most of the job scheduling problems can be solved by any of these approaches:
We will discuss the Sequential Jobs Scheduling Problem with Precedence here.
So this kind of problems state is that there are certain jobs need to be done but there are some constraints that need to be fulfilled while getting those jobs done. The constraint is that there are certain jobs that are dependent on the completion on some other jobs, and cannot be started until those jobs are completed. This is what we refer to as Precedence. One more constraint for this kind of problems is that you can do only one job at a time. This is why it is sequential. Even if two or more jobs are eligible to be done at the same time, you cannot do them parallelly.
So what we need to do here is processing a job only after getting the jobs on which the job is dependent on first, and this must be true for all the given jobs. This is nothing but the concept of Topological Order or Topological Sorting.
One more thing to notice, each job may have its own duration to complete, but since it is a sequential job scheduling, the durations won't add any extra complexity. In fact, if we just have to do a feasibility test (i.e, determining if a given set of jobs are possible to be completed maintaining all the given constraints/precedence) we won't even have to consider the durations. In fact, the Topological Sorting does not even need any job durations. We would only need the durations if we have to determine how long it takes to process all the jobs from beginning till the end.
Now let's take a look at a real-world problem of this kind:
Course ScheduleThere are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? For example: 2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. 2, [[1,0],[0,1]] There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Solution:We can represent the input prerequisites as a graph. Let's represent the graph by a list of edges.
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Related Must-Read Topics:
- Course Scheduling
- Dijkstra's Algorithm
- Longest Paths Algorithm
- Topological Sort w/ Vertex Relaxation
- Bellman-Ford Algorithm & Negative Cycle Detection
- Optimized Bellman-Ford
- Parallel Job Scheduling
Parallel Job Scheduling
w/ Relative Deadlines
The above content is written by:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn