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.

The recordclass module

Please note i'm using the third-party module 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!

 1 from recordclass import recordclass
 2 
 3 Job = recordclass('Job', 'name profit deadline')
 4 Slot = recordclass('Slot', 'start end job')
 5 
 6 jobs = [Job('j1', 20, 2), Job('j2', 15, 2), Job('j3', 10, 1), Job('j4', 5, 3), Job('j5', 1, 3)]
 7 slots = [Slot(0, 1, 0), Slot(1, 2, 0), Slot(2, 3, 0)]
 8 
 9 def compute_max_profit_schedule():
10     for max_profit_job in jobs:
11         slots_before_deadline = [s for s in slots if (s.start+1) <= max_profit_job.deadline and s.job == 0]
12         if slots_before_deadline:
13             slot = slots_before_deadline[-1]
14             slot.job = max_profit_job
15 
16     print("Schedule:")
17 
18     for s in slots:
19         print(s)
20 
21     print("Profit:")
22 
23     print(sum(slot.job.profit for slot in slots))
24 
25 if __name__ == '__main__':
26     compute_max_profit_schedule()

Output:

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