Job Sequencing Problem

Scheduling can be tough sometimes, and the Job Sequencing Problem is an example. You have a list of jobs with some deadlines and profit that you’ll receive if you finish the job before the deadline. Your goal is to reach the maximum total profit.

Each job lasts 1-time point, and you can do no more than one job at the moment.

This problem is similar to the Schedule Problem, but there is no maximizing the total number of tasks, only total profit.

The data is jobs – a list of dicts:

jobs[i] = {'name': “A”, 'profit':12, 'dl': 3}

Let’s be greedy and sort all jobs in decreasing order by the profit. We want to reach the maximum, so let’s pick jobs one by one and find someplace among empty slots. You can pick some empty slot between 0 and jobs[i][dl] (deadline) for jobs[i]. How to do that greedy, too?

The approach is similar to the Schedule Problem: you have to choose the rightmost empty slot, because in case if (i+1)th job has less deadline, you’ll probably find an empty slot for it.

Algorithm:

Sort jobs decreasing by profit.
Traverse the jobs, pick the jobs[i].
If there is an empty slot[j] (j starts from jobs[i][dl] down to 0), fill it with jobs[j][name]. Else skip this job – there is no slot to schedule it.

Task

Swipe to start coding

Complete the algorithm.

Solution

def JSP(jobs):

jobs.sort(key=lambda x: x['profit'], reverse=True)

max_dl = max(job['dl'] for job in jobs)

slot = [None for _ in range(max_dl+1)]

profit = 0

for job in jobs:

for j in range(job['dl'], 0, -1):

if slot[j] == None:

slot[j] = job['name']

profit += job['profit']

break

return slot[1:], profit

d = dict()

jobs = [{'name':'A', 'profit':12, 'dl': 2},

{'name':'B', 'profit':4, 'dl': 1},

{'name':'C', 'profit':10, 'dl': 2},

{'name':'D','profit':9, 'dl': 2},

{'name':'E', 'profit':2, 'dl': 4}]

print(JSP(jobs))

Everything was clear?

Thanks for your feedback!

Section 1. Chapter 6

single

def JSP(jobs):

# sort jobs by profit

jobs.sort(key=lambda x: x['profit'], reverse=True)

max_dl = ___________ # find the maximum deadline

# init slots that are empty for now