辅导案例-CSE 101

  • May 15, 2020

CSE 101 Summer 2019Programming Assignment 3Instructions: Solutions to this assignment must be submitted through Gradescope byFriday, 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, aswell 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 howto 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 algorithmisP0 1 2 3 4 5 6 7 8 9 10J2 J3 J4 J1where 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’salgorithm isP10 1 2 3 4 5 6 7 8 9 10J1P20 1 2 3 4 5 6 7 8 9 10J2 J3P30 1 2 3 4 5 6 7 8 9 10J3 J41Then 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 jobson a m parallel processors (without preemption) with the objective of minimizing the makespan.Implement List Scheduling, LPT, and SPT : Write three separate proceduresi. 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 isP10 1 2 3 4 5 6 7 8 9 10J4P20 1 2 3 4 5 6 7 8 9 10J1 J3P30 1 2 3 4 5 6 7 8 9 10J2 J5Then 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

LATEST POSTS
MOST POPULAR

ezAce多年来为广大留学生提供定制写作、留学文书定制、语法润色以及网课代修等服务,超过200位指导老师为您提供24小时不间断地服务。