Minimizing maximum lateness : Greedy algorithm – Algorithms and Me

Minimizing maximum lateness : Greedy algorithm – Algorithms and Me

We have a processor which can process one process a time and as always given list of processes to be scheduled on that process, with intention that maximum late process should be minimized. Contrary to previous problems, this time, we are not provided with start time and end time, but we are given length of time (ti) process will run and deadline it has to meet (di), fi is actual finish time of process completion.

Lateness of a process is defined as

l(i) = max{0, fi − di}, i.e. the length of time past its deadline that it finishes.

Goal here schedule all jobs to minimize maximum lateness L = max  {l(i)}

1. Sort all job in ascending order of deadlines
2. Start with time t  = 0;
3. For each job in list
   3.1 Schedule the ob at time t
   3.2 Finish time = t + processing time of job
   3.3 t = finish time
4. Return (start time, finish time) for each job

1. from operator import itemgetter
2.  
3. jobs = [(1, 3, 6), (2, 2, 9), (3, 1, 8), (4, 4, 9), (5, 3, 14), (6, 2, 15)]
4.  
5. def get_minimum_lateness():
6. schedule =[];
7. max_lateness = 0
8. t = 0;
9.  
10. sorted_jobs = sorted(jobs,key=itemgetter(2))
11.  
12. for job in sorted_jobs:
13. job_start_time = t
14. job_finish_time = t + job[1] # add the processing time to currrent time
15. # and that will be finish time
16. t = job_finish_time
17. if(job_finish_time > job[2]):
18. max_lateness = max (max_lateness, (job_finish_time - job[2]))
19. schedule.append((job_start_time, job_finish_time))
20. return max_lateness, schedule
21.  
22. max_lateness, sc = get_minimum_lateness();
23. print "Maximum lateness will be :" + str(max_lateness)
24. for t in sc:
25. print t[0], t[1]

Read full article from Minimizing maximum lateness : Greedy algorithm – Algorithms and Me