Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lära Job Sequencing Problem | Greedy Algorithms: Overview and Examples
Greedy Algorithms using Python

book
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:

  1. Sort jobs decreasing by profit.

  2. Traverse the jobs, pick the jobs[i].

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

Uppgift

Swipe to start coding

Complete the algorithm.

Lösning

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))

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 6
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
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:
# add job's name to the empty slot
slot[j] = __________
# increase the total profit with job's profit
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))

Fråga AI

expand
ChatGPT

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

some-alt