Class Activity Ch$.8$

A kitchen remodel business with two workers would like to optimize the amount of time required for a

remodel. A list of tasks for a typical remodel is given below. Answer questions $1-4$ regarding this scenario.

$1.$ Create a precedence digraph to describe the tasks based on their prerequisites.

$2.$ Write out a decreasing$-$time priority list.

$3.$ Schedule the tasks for the business using the priority list from above. $($Each block represents $1$ hour$)$

$4.$ How long will it take the workers to finish the schedule obtained in question $3?$ Was it possible to

complete this project with no idle time?

Tasks Prerequisites Time

Unload None $2$ hr

Remove appliances None $1$ hr

Remove flooring Remove appliances $3$ hr

Remove cabinetry Remove appliances $1$ hr

Install flooring Unload, remove flooring $5$ hr

Install cabinetry Unload, remove cabinetry $4$ hr

Install backsplash Install flooring $2$ hr

Paint Install flooring $2$ hr

Install countertop Install flooring $3$ hr

Install sink Install countertop $3$ hr

Install appliances Install countertop $1$ hr

Abernathy and Bethany are planning to host Christmas dinner for their family and would like to build a

schedule to figure out how to best optimize their time. The tasks they need to complete to finish preparing as

well as their time to complete are listed:

$($A$)$ Go to the grocery store $(2$ hours$)$

$($B$)$ Cook the ham $(3$ hours$)$

$($C$)$ Prepare the mashed potatoes $(1$ hour$)$

$($D$)$ Prepare the other sides $(2$ hours$)$

$($E$)$ Prepare the drinks $(1$ hour$)$

$($F$)$ Prepare desserts $(2$ hours$)$

$($G$)$ Bake the desserts $(2$ hours$)$

$($I$)$ Decorate the tree and table $(3$ hours$)$

$($J$)$ Put up Christmas lights $(4$ hours$)$

They have agreed to work on tasks separately so that they do not get in each other$$s way. The only

requirement is that one of them must go to the grocery store before they do any food related tasks $($Tasks B$-$

G$).$ They also need to cook the ham and prepare the desserts before they bake the desserts since the desserts

will need the oven. Tasks I and J are independent tasks. Answer questions $5-14$ regarding this scenario.

$5.$ Create a precedence digraph that properly represents this situation.

$6.$ Write out a decreasing$-$time priority list.

$7.$ Schedule the tasks for Abernathy and Bethany using the decreasing$-$time algorithm. What is Fin?

$8.$ What is the finishing time $($Fin$)?$ How much idle time was in the schedule?

$9.$ Use the backflow algorithm to find the critical time for each vertex, writing your critical times in brackets.

$10.$ What is the critical path and critical time for the project?

$11.$ Write out a critical time priority list.

$12.$ Schedule the tasks for Abernathy and Bethany using the critical path algorithm. What is Fin?

$13.$ Explain why your answer from #$8$ is optimal and #$3$ is not optimal.

$14.$ The critical time is always the fastest possible time for completing a task$-$processor problem. Explain why

Abernathy and Bethany were unable to complete their tasks within the critical time. If they had the help

of Cathy as a third processor, would they be able to complete the tasks within the critical time?

J $(4)$

$15.$ You are the manager of an advertising firm and the process for designing a specific ad requires eight tasks to be

completed before the ad is ready. The lengths of each task is given in the table below.

Your goal as manager is to assign the tasks to your two employees in the most efficient possible manner. Use the critical

path algorithm to schedule the tasks. How much time will it take them to finish?

Task # Time to Complete

$13$ hours

$22$ hours

$31$ hour

$43$ hours

$56$ hours

$62$ hours

$72$ hours

$85$ hours