Explain Job sequencing with deadline for the given instance.

7views

written 8.4 years ago by

teamques10 ★ 68k

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.

ADD COMMENT EDIT

Why do we make subsets of two or three jobs ? Please explain in detail

8.0 years ago by teamques10 ★ 68k