Exam 3: Planning and Scheduling

Choose the packing that results from the use of the next-fit decreasing (NFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs. 5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs, 3 lbs

Choose the packing that results from the use of the worst-fit (WF) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs. 5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs

What is the minimum time required to complete 12 independent tasks on four processors when the sum of all the times of the 12 tasks is 120 minutes?

Questions refer to this bin-packing task. Pack the following weights into bins holding no more than 5 lbs: 2 lbs, 1 lb, 4 lbs, 3 lbs, 4 lbs, 1 lb, 2 lbs, 3 lbs -Find the number of bins required using the worst-fit (WF) algorithm.

What is the minimum number of machines required to perform eight independent tasks in 12 minutes with a total task time of 48 minutes?

When scheduling tasks using the list-processing algorithm, decreasing the time of each task always decreases the completion time.

Questions refer to this bin-packing task. Pack the following weights into bins holding no more than 5 lbs: 2 lbs, 1 lb, 4 lbs, 3 lbs, 4 lbs, 1 lb, 2 lbs, 3 lbs -Find the number of bins required using the next-fit (NF) algorithm.

Use the order requirement digraph below (with time given in minutes) and the priority list T₁, T₂, T₃, T₄, T₅, T₆, T₇, T₈ to answer the following Questions -Apply the critical-path scheduling algorithm to construct a schedule using two processors.

Give an example of an order-requirement digraph with six tasks T₁, T₂, T ₃, T₄, T₅, T₆ that requires 10 minutes when scheduled on two processors.

Give an example of an order-requirement digraph with six tasks T₁, T₂, T ₃, T₄, T₅, T₆ for which the critical-path is T₁, T₃, T₄.

Use the order-requirement digraph below (with time given in minutes) and the priority list T₁, T₂, T ₃, T₄, T₅, T₆ to answer Questions 13-16. -Apply the critical-path scheduling algorithm to construct a schedule using three processors.

-Use the next-fit (NF) bin-packing algorithm to pack the following weights into bins that can hold no more than 10 lbs. 1 lb, 2 lbs, 2 lbs, 7 lbs, 8 lbs, 5 lbs, 8 lbs, 4 lbs, 10 lbs, 6 lbs

Use the decreasing-time-list algorithm to schedule these tasks on two machines: How much time does the resulting schedule require? $9 \text { minutes, } 6 \text { minutes, } 3 \text { minutes, } 4 \text { minutes, } 8 \text { minutes }$

Use the following digraph to answer Questions Suppose that a crew can currently complete a job (order-requirement digraph is shown below) in a minimum amount of time. -If Task T₂ is shortened from 9 minutes to 6 minutes, then what is the maximum amount of time by which the completion time of the entire job can be shortened?

The worst-fit decreasing (WFD) algorithm for bin-packing is guaranteed to always produce an optimal solution.

The first-fit (FF) algorithm never uses more boxes than the next-fit (NF) algorithm.

Give an example in which six independent tasks require 12 minutes when scheduled on three processors.

Choose the packing that results from the use of the next-fit decreasing (NFD) bin-packing algorithm to pack data files with the following sizes onto compact discs that can hold no more than 700 MB. 100 MB, 500 MB, 250 MB, 350 MB, 400 MB, 250 MB, 450 MB, 200 MB, 50 MB

Why are there several different algorithms for the bin-packing problem?

Which of the algorithms-first fit (FF), next fit (NF), or worst fit (WF)-would be most preferable when packing cloth dolls? Why?