Let n = 4, (p1 , p2, p3, p4) = (100, 10, 15, 27) and (dl, d2, d3, d4) = (2, 1, 2, 1). Find feasible solutions, using job sequencing with deadlines.

• 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.

Job sequencing with deadlines algorithm:

1. Initially all slots are free
   • We have b+1 sets corresponding ponding to b+1 time slots i, 0 ≤ i ≤ b
   • Slot 0 is a sentinel
   • Initially F (i) = i for all i
2. We will use parent p[i] to link slot i into its set
   • Initially p[i] = -1 for all i
   • Parent of root is negative of number of nodes in set
3. To schedule job i with deadline di :
   • “Find” root of tree containing slot min (n, di)
     • Usually this is just slot di
   • If root of i’s set is j, then F (j) is latest free slot, provided F (j) ≠ 0
4. After using slot F(j), we combine (“set union”) set having root j with set having slot F(j) -1

Problem:

Feasible solution and there values are:

• Solution 6 is optimal. In this solution, job 1, 3, 4 are processed and the value is 142.
• These jobs can be processed in order 1, 3 and then 4 or 3, 1 and then 4.
• The processing of job 1 or 3 begins at time zero and is completed at time 3 and that of job 4 is completed at time 3.