Solve the following Job sequencing with deadlines problem n=7, Profits(p1, p2, p7)={3, 5, 20, 18, 1, 6, 30}Deadlines(d1, d2, d7)={1, 3, 4, 3, 2, 1, 2}

5.3kviews

written 7.1 years ago by

Let n=7, Profits(p1, p2. ….p7)={3, 5, 20, 18, 1, 6, 30} Deadlines(d1, d2,….d7)={1, 3, 4, 3, 2, 1, 2} The feasible solution and their values are given below.

Sr. No	Feasible Solution	Frequenting Sequence	Value
1	(1,2)	1,2 or 2,1	8
2	(1,3)	3,1	23
3	(1,4)	4,1	21
4	(1,5)	5,1	4
5	(1,6)	6,1	9
6	(1,7)	7,1	33
7	(2,3)	3,2	25
8	(3,4)	4,3	38
9	(4,5)	5,4	19
10	(5,6)	6,5	7
11	(6,7)	7,6	36
12	(1)	1	3
13	(2)	2	5
14	(3)	3	20
15	(4)	4	18
16	(5)	5	1
17	(6)	6	6
18	(7)	7	30

Consider the jobs in the non-increasing order of profits subject to the constraint that the resulting job sequence J is a feasible solution.

In the example considered before, the non-increasing profit vector is

30	20	18	6	5	3	1		2	4	3	1	3	1	2
p1	p2	p3	p4	p5	p6	p7		d1	d2	d3	d4	d5	d6	d7

i. Now we start adding the job with J = 0 and Σ i ej Pi= 0.

ii. Job 7 is added to J as it has the largest profit and thusJ = {7} is a feasible one.

iii. Now job 3 is considered. The solution J = {3, 7} is a feasible one with processing sequence (7, 3).

iv. The next job, Job 4 is considered. The solution J = {3, 4, 7} is a feasible one with processing sequence (3,4,7).

v. Finally, the next job, Job 6 is considered. The solution J = {3, 4, 6, 7} is a feasible one with processing sequence (3,4, 6,7).

vi. Thus we have J = {3,4, 6, 7} is optimal solution with value 74.’

ADD COMMENT EDIT