CSE 101 Summer 2019
Programming Assignment 3
Instructions: Solutions to this assignment must be submitted through Gradescope by
Friday, August 30th 2019 at 10:00 PM— no late submissions will be accepted.
For this programming assignment, it is recommended that you refer to your lecture notes, as
well as Some Basic Scheduling Algorithms, by Joseph Leung.
1. (1||∑Uj) Given n jobs with processing times p1, . . . , pn and due dates d1, . . . , dn, we will decide how
to schedule the jobs on a single processor with the objective of minimizing the number of late jobs,∑
Uj . Moore’s algorithm yields the optimal solution to this objective.
Implement Moore’s algorithm: Write a procedure Moore(P,D) that takes as input
• P: an array of n positive integers (processing times of jobs J1, . . . , Jn)
• D: an array of n positive integers (due dates of jobs J1, . . . , Jn),
and prints the schedule that results from Moore’s Algorithm, as well as the resulting late jobs.
For example, suppose that for a set of jobs J1, . . . , J4, the schedule resulting from Moore’s algorithm
is
P
0 1 2 3 4 5 6 7 8 9 10
J2 J3 J4 J1
where jobs J4 and J1 are late. Then calling Moore(P,D) should print the following (where jobs after
“|” are late):
P: J_2 (0,2), J_3 (2,3) | J_4 (3,6), J_1 (6,10)
2. (a) (P | pmtn | Cmax) Given n jobs with processing times p1, . . . , pn, we will decide how to preemp-
tively schedule the jobs on a m parallel processors with the objective of minimizing the makespan.
McNaughton’s algorithm yields the optimal solution to this objective.
Implement McNaughton’s algorithm: Write a procedure McNaughton(P,m) that takes as input
• P: an array of n positive integers (processing times of jobs J1, . . . , Jn)
• m: a positive integer (number of parallel and identical processors)
and prints the schedule that results from McNaughton’s Algorithm.
For example, suppose that for a set of jobs J1, . . . , J5, the schedule resulting from McNaughton’s
algorithm is
P1
0 1 2 3 4 5 6 7 8 9 10
J1
P2
0 1 2 3 4 5 6 7 8 9 10
J2 J3
P3
0 1 2 3 4 5 6 7 8 9 10
J3 J4
1
Then calling McNaughton(P,3) should print the following:
P_1: J_1 (0,6)
P_2: J_2 (0,4), J_3 (4,6)
P_3: J_3 (0,1), J_4 (1,6)
(b) (P || Cmax) Given n jobs with processing times p1, . . . , pn, we will decide how to schedule the jobs
on a m parallel processors (without preemption) with the objective of minimizing the makespan.
Implement List Scheduling, LPT, and SPT : Write three separate procedures
i. ListScheduling(P,m)
ii. LPT(P,m)
iii. SPT(P,m)
that take as input
• P: an array of n positive integers (processing times of jobs J1, . . . , Jn)
• m: a positive integer (number of parallel and identical processors)
and print the schedule that results from the corresponding algorithm.
For example, suppose that for a set of jobs J1, . . . , J5, the schedule resulting from LPT is
P1
0 1 2 3 4 5 6 7 8 9 10
J4
P2
0 1 2 3 4 5 6 7 8 9 10
J1 J3
P3
0 1 2 3 4 5 6 7 8 9 10
J2 J5
Then calling LPT(P,3) should print the following:
P_1: J_4 (0,8)
P_2: J_1 (0,5), J_3 (5,6)
P_3: J_2 (0,4), J_5 (5,7)
2