job scheduling with deadlines

This is a maximisation problem, solved using the greedy method, where we need to allocate jobs within specified deadlines to make a max profit. You can find [the lecture here](https://www.youtube.com/watch?v=zPtI8q9gvX8).

The recordclass module

Please note i’m using the third-party module [recordclass](https://pypi.org/project/recordclass/), as a mutable named tuple. recordclass is extremely handy, although a word of warning: on windows it adds Microsoft Visual Studio compiler as a dependency (for c file compilation).

Implementation

This implementation is not very efficient, due to the nested for loop. It could obviously be optimised, i just don’t have the will right now, as i have higher paying jobs waiting!

from recordclass import recordclass

Job = recordclass(‘Job’, ‘name profit deadline’)
Slot = recordclass(‘Slot’, ‘start end job’)

jobs = [Job(‘j1’, 20, 2), Job(‘j2’, 15, 2), Job(‘j3’, 10, 1), Job(‘j4’, 5, 3), Job(‘j5’, 1, 3)]
slots = [Slot(0, 1, 0), Slot(1, 2, 0), Slot(2, 3, 0)]

def compute_max_profit_schedule():
for max_profit_job in jobs:
slots_before_deadline = [s for s in slots if (s.start+1) <= max_profit_job.deadline and s.job == 0]
if slots_before_deadline:
slot = slots_before_deadline[-1]
slot.job = max_profit_job

print(“Schedule:”)

for s in slots:
print(s)

print(“Profit:”)

print(sum(slot.job.profit for slot in slots))

if __name__ == ‘__main__’:
compute_max_profit_schedule()

Output:

Slot(start=0, end=1, job=Job(name=’j2', profit=15, deadline=2))
Slot(start=1, end=2, job=Job(name=’j1', profit=20, deadline=2))
Slot(start=2, end=3, job=Job(name=’j4', profit=5, deadline=3))
Profit:
40

Related articles:

flatten a dictionary
design a web crawler
max array

Post by Shyal Beardsley . To see more— shyal.com — ioloop.io