- We are given n jobs. Associated with each job i there is an integer deadline di and a profit pi where di>0 & pi>0.
- For any job i, the corresponding profit is earned if the job is completely by its deadline. To complete the job one has to process a job on a machine and only one machine is available for processing jobs.
- Each jobs requires only one unit of time for its processing.
- A feasible solution for this problem is a subset j of jobs such that each job in this subset can be completed by its deadline. The value of this feasible solution j is the sum of profits of jobs in j or ⅀pi. An optimal solution is a feasible solution with maximum value. Hence again, since the problem involves the identification of a subset, it fits the subset paradigm.
Problem:
Feasible solution and there values are:
| Sr. No |
Feasible solution |
Frequenting,sequence |
Values |
| 1 |
(1,2) |
1,2 or 2,1 |
35 |
| 2 |
(1,3) |
1,3 |
30 |
| 3 |
(1,4) |
1,4 |
25 |
| 4 |
(1,5) |
1,5 |
23 |
| 5 |
(1,2,4) |
1,2,4 or 2,1,4 |
40 |
| 6 |
(1,3,4) |
3,1,4 |
35 |
| 7 |
(2,3,4) |
3,2,4 |
30 |
| 8 |
(1,2,5) |
1,2,5 or 2,1,5 |
38 |
| 9 |
(1,3,5) |
3,1,5 |
33 |
| 10 |
(2,3,5) |
3,2,5 |
28 |
| 11 |
(2,3) |
3,2 |
25 |
| 12 |
(2,4) |
2,4 |
20 |
| 13 |
(2,5) |
2,5 |
18 |
| 14 |
(4,5) |
4,5 or 5,4 |
8 |
- Solution 5 is optimal. In this solution, job 1, 2, 4 are processed and the value is 40.
- These jobs can be processed in order 1, 2 and then 4 or 2, 1 and then 4.
- The processing of job 1 or 2 begins at time zero and is completed at time 2 and that of job 4 is completed at time 3.
teamques10
★ 64k
and 4 others joined a min ago.