**Introduction**

A traditional CPU can only execute one job at a time, which makes the system operate more but with poor output. Therefore, various Job Scheduling algorithms come into the picture to maximize CPU utilization and increase the systemâ€™s efficiency.

Parallel Execution of multiple jobs is one of them, which is accomplished by scheduling the CPU based on the profit or priority given to jobs.

This article will discuss the variations of the job scheduling problem in data structures and algorithms, followed by a comprehensive discussion of various approaches from brute force to the most optimal.

At first, it might seem not very comforting, but we urge you to read it till the end and believe me, then, there is no turning back; you will be able to solve this problem even in your sleepy head.

Also see: __Multiprogramming vs Multitasking____ __and __Open Source Operating System____.__

**Problem Statement**

In weighted job scheduling, Youâ€™re given a list of jobs to complete, each with a Start time, Finish time, and a profit. A jobâ€™s profit is only awarded if performed within its deadline. One more catch here is that only one machine is available for processing.

So here, find the maximum profit you can achieve so that no jobs overlap. In this problem, we must focus on maximizing profit rather than increasing the number of jobs executed. Now that weâ€™ve got the problem statement letâ€™s figure out how to approach its solution.

**Solution Approach**

A clear vision of our goals is the driving force behind our efforts to achieve them. Similarly, before we further search for the best solution to this problem, letâ€™s explore what the answer might be.

- A viable solution to this problem will include a set of jobs, each of which can be completed by the specified deadline without overlapping.
- The value of a possible solution will be the sum of the profits associated with the jobs in the above set.

Letâ€™s look at an example to help us understand in a better way:

```
Let the number of jobs = 4
profits (p1 , p2 , p3 , p4)=(100 , 10 , 15 , 27)
start time(s1 , s2 , s3 , s4) =(1 , 0 , 1 , 0) and finish time (f1 , f2 , f3 , f4)=(2 , 1 , 2 , 1)
```

**Solution:** The total time available for the execution of jobs is 2 units(equal to the maximum deadline). Refer to the Gantt chart below for a pictorial interpretation.

Now we have to schedule the jobs assigned to us to maximize profit. All of these schedules are listed in the table below.

**Answer:** Solution 2 is optimal. In this case, only jobs 1 and 4 are processed, and the value is 127. Therefore, the processing order of the jobs is that job 4 is followed by job 1.

Letâ€™s see the immediate implementation of the brute-force solution.

```
Algorithm JobScheduling( d, J, n)
{
// J is the set of jobs that can be completed by their deadline
// n is the total number of jobs
J := { 1 } ;
For i:= 2 to n do
{
if( all jobs in J U i can be completed by their deadlines )
Then J := J U { i } ;
}
}
```

**Variations of Job Scheduling Problem**

**Basic Version**

You are given a list of n jobs, each with a start and end time. Choose the maximum number of jobs a single processor can do, given that each can only work on one job at a time.

Note: The profit associated with each job is the same in this case.

Example: Given four jobs with their start and finish times.

```
Job1 = { 1, 3 }
Job2 = { 2, 4 }
Job3 = { 3, 5 }
Job4 = { 5, 7 }
```

Letâ€™s consider, You as a boss and attending meetings is a part of your daily routine; now you want to attend a maximum number of meetings with the above-given start and end times.