Game:

Deadline (1982)

Duration: 0:00

8 views

1

Write High-level description of job sequencing algorithm. Let number of jobs (n)=5; Profit vector P={20, 15, 10, 5, 1); Deadline vector D={2, 2, 1, 3, 3) Find the feasible solutions. What is the optimal solution and maximum profit?

#job #jobsearching #algorithm #cs #cse #engineering

What is Job Sequencing with Deadlines?

The prime objective of the Job Sequencing with Deadlines algorithm is to complete the given order of jobs within respective deadlines, resulting in the highest possible profit. To achieve this, we are given a number of jobs, each associated with a specific deadline, and completing a job before its deadline earns us a profit. The challenge is to arrange these jobs in a way that maximizes our total profit.

It is not always possible to complete all of the assigned jobs within the deadlines. For each job, denoted as Ji, we have a deadline di and a profit pi associated with completing it on time. Our objective is to find the best solution that maximizes profit while still ensuring that the jobs are completed within their deadlines.

Here’s how Job Sequencing with Deadlines algorithm works:

Problem Setup

You’re given a list of jobs, where each job has a unique identifier (job_id), a deadline (by which the job should be completed), and a profit value (the benefit you gain by completing the job).

Sort the Jobs by Profit

To ensure we consider jobs with higher profits first, sort the jobs in non-increasing order based on their profit values.

Initialize the Schedule and Available Time Slots

Set up an array to represent the schedule. Initialize all elements to -1, indicating that no job has been assigned to any time slot. Also, create a boolean array to represent the availability of time slots, with all elements set to true initially.

Assign Jobs to Time Slots

Go through the sorted jobs one by one. For each job, find the latest available time slot just before its deadline. If such a time slot is available, assign the job to that slot. If not, skip the job.

Calculate Total Profit and Scheduled Jobs

Sum up the profits of all the scheduled jobs to get the total profit. Additionally, keep track of which job is assigned to each time slot.

Output the Results

Finally, display the total profit achieved and the list of jobs that have been scheduled.






Job Sequencing Problem


Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. Maximize the total profit if only one job can be scheduled at a time.

Examples: 

Input: Four Jobs with following deadlines and profits

JobID  Deadline  Profit

  a           4          20   
  b           1          10
  c           1          40  
  d          1          30

Output: Following is maximum profit sequence of jobs: c, a   

Input:  Five Jobs with following deadlines and profits

JobID   Deadline  Profit

  a            2          100
  b            1          19
  c            2          27
 d            1          25
 e            3          15

Output: Following is maximum profit sequence of jobs: d, a, e

Using Greedy Approach with Extra Space

Follow the given steps to solve the problem:

Sort the jobs by profit: The first step is to sort the jobs in descending order of their profit because we want to maximize the profit by performing the highest-paying jobs first.

Create time slots: We create an array slot[] to keep track of which time slots are available (free) and an array result[] to store the job sequence.

Job scheduling: For each job, try to find a free time slot before or on its deadline (starting from the last possible time slot). If such a time slot is available, assign the job to it.

Output the job sequence: Finally, print the job sequence that yields the maximum profit. Only jobs that are scheduled in valid time slots are printed.