3.1 Scheduling Tasks

3.2 Critical-Path Schedules

1. You and your two housemates are planning to have a party this Friday night at your apartment. Eight guests are expected, and you plan to serve a small homemade dinner. List the tasks involved in carrying out such a party and the types of processors to be used to carry out the tasks. Can any of the tasks be done simultaneously?

2. Compare and contrast the scheduling problems that arise at a

3. List as many scheduling situations as you can for these environments:

4. Jane is planning a getaway weekend at a ski resort. She plans to leave work in Manhattan at 1 P.M. and must make her way to a local airport for a 5 P.M. shuttle plane to Boston. She then hopes to get a bus to the nearby resort. Discuss the tasks that Jane must complete to be at the resort by 10 P.M. What are the different types of processors involved in getting these tasks done? Can any of these tasks be done simultaneously?

5. Schedule the six tasks of the job indicated in the accompanying order-requirement digraph on one processor, using the list-processing algorithm and the list T₁, T₂, T₃, T₄, T₅, T₆.

6. Use the list-processing algorithm to solve the scheduling problem in Exercise 5 on two processors.

7. Use the list-processing algorithm to schedule the tasks in the accompanying order-requirement digraph on

8. Consider the order-requirement digraph below:

9.

10. For the accompanying order-requirement digraph, answer the following questions.

11. An order-requirement digraph has exactly two vertices that have no edges coming into them. Explain why, if there are three processors available, one or more of these processors must be idle some of the time.

12.

13.

14.

15.

16.

17. Can you give examples of scheduling problems for which it seems reasonable to assume that all the task times are the same?

18. Use the list-processing algorithm to schedule the tasks in the accompanying order-requirement digraph on

19. For the accompanying order-requirement digraph, apply the list-processing algorithm, using three processors for lists (a) through (c). How do the completion times obtained compare with the length of the critical path?

20.

21. Can you find a list that gives rise to the optimal schedule shown in Figure 3.14 (on page 93) for the order-requirement digraph in Figure 3.12 (on page 92)?

22. Consider the accompanying order-requirement digraph.

23. Given the order-requirement digraph below, answer the following questions.

24.

25.

26. To prepare a meal quickly involves carrying out the tasks shown (time lengths in minutes) in the accompanying order-requirement digraph:

113

27.

28.

29. Consider the following order-requirement digraph. Suppose one plans to schedule these tasks on two identical processors.

30.

31. Can you find an order-requirement digraph with four tasks for which every possible list yields exactly the same schedule?

32. Can you find an order-requirement digraph involving three tasks such that the schedule corresponding to every list is different?

33. At a large toy store, scooters arrive unassembled in boxes. To assemble a scooter, the following tasks must be performed:

34. If two schedules for the same number of processors have the same completion time, can one schedule have more idle time than the other?

35. Could the schedule below be obtained by applying the list-scheduling algorithm to some order-requirement digraph?

3.3 Independent Tasks

36. Could the following schedule be obtained by applying the list-scheduling algorithm to some order-requirement digraph?

37. For the accompanying schedules, can you produce a list so that the list-processing algorithm produces the schedule shown when the tasks are independent? What are the times for each task?

38. Once an optimal schedule has been found for independent tasks (see the diagrams in Exercise 37), usually the scheduling of the tasks can be rearranged and the same optimal time achieved.

We can, among other things, reorder the tasks done by a particular processor. Discuss criteria that might be used to implement the rearrangement process.

39. The task times of eight independent tasks T₁ to T₈ are 1, 2, 3, 4, 5, 6, 7, 8.

40. Repeat Exercise 39, but schedule the tasks (with the same lists) on three processors. If the schedules you get are not optimal, find a list that gives an optimal schedule.

41. Discuss different criteria that might be used to construct a priority list for a scheduling problem.

42. Some scheduling projects have due dates for tasks (times by which a given task should be completed) and release dates (times before which a task cannot have work begun on it). Give examples of circumstances where these situations might arise.

43. Using the lists you found in Exercise 37 and the task times you computed for those independent tasks, schedule the tasks for part (a) on four processors and the tasks for part (b) on five processors. Can you see why for any schedule you may produce for part (a) on four processors and part (b) on five processors, there must be some idle time for one or more processors?

44. Use the order-requirement digraph below to answer the following questions.

45. Repeat the questions in Exercise 44 using the order-requirement digraph obtained by erasing all the (directed) edges shown there. How do the schedules you obtain compare with the ones you originally got?

46.

47. Repeat parts (a)–(c) of Exercise 46 for independent tasks of lengths 19, 19, 20, 20, 1, 1, 2, 2, 3, 3, 5, 5, 11, 11, 17, 17, 18, 18, 17, 2, 16, 16, 2.

48. Suppose that independent tasks require a total of 36 minutes, but only one of the tasks takes as long as 12 minutes. If these tasks are scheduled on two machines, show by an example that the earliest completion time may be as long as 22 minutes.

49. A photocopy shop must schedule independent batches of documents to be copied. The times for the different sets of documents are (in minutes) 12, 23, 32, 13, 24, 45, 23, 23, 14, 21, 34, 53, 18, 63, 47, 25, 74, 23, 43, 43, 16, 16, 76.

50. Find a list that produces the following optimal schedule when the list-processing algorithm is applied to this list. (Assume that the tasks are independent.)

What completion time and schedule are obtained when the decreasing-time-list algorithm is applied to this list?

51. Can you think of situations other than those mentioned in the text where scheduling independent tasks on processors occurs?

52. Can you think of real-world scheduling situations in which all the tasks have the same time and are independent? Find an algorithm for solving this problem optimally. (If there are independent tasks of time length , when will all the tasks be finished?)

53. Show that when tasks to be scheduled are independent, the critical-path method and the decreasing-time-list method are identical.

3.4 Bin Packing

54. Two wooden wall systems are to be made of pieces of wood with lengths shown in the accompanying diagram. If wood is sold in 10-foot planks and can be cut with no waste, what number of boards would be purchased if one uses the FFD, NFD, and WFD heuristics, respectively?

In solving this problem, does it make a difference if the 10-foot horizontal shelves and 6-foot vertical boards employ single-length pieces, compared with using pieces of boards that add up to 10- and 6-foot lengths?

55. It takes 4 seconds to photocopy one page. Manuscripts of 10, 8, 15, 24, 22, 24, 20, 14, 19, 12, 16, 30, 15, and 16 pages are to be photocopied. How many photocopy machines would be required, using the FFD algorithm, to guarantee that all manuscripts are photocopied in 2 minutes or less? Would the solution differ if WFD were used?

56. A radio station’s policy allows advertising breaks of no longer than 2 minutes, 15 seconds. Using FF and FFD algorithms, determine the minimum number of breaks into which the following ads will fit (lengths given in seconds): 80, 90, 130, 50, 60, 20, 90, 30, 30, 40. Can you find the optimal solution? Do the same for these ad lengths: 60, 50, 40, 40, 60, 90, 90, 50, 20, 30, 30, 50.

57. Fiberglass insulation comes in 36-inch pre-cut sections. A plumber must install insulation in a basement on piping that is interrupted often by joints. The distances between the joints on the stretches of pipe that must be insulated are 12, 15, 16, 12, 9, 11, 15, 17, 12, 14, 17, 18, 19, 21, 31, 7, 21, 9, 23, 24, 15, 16, 12, 9, 8, 27, 22, 18 inches. How many pre-cut sections would he have to use to provide the insulation if he bases his decision on

58. The files that a company has for its employees dealing with utilities occupy 100, 120, 60, 90, 110, 45, 30, 70, 60, 50, 40, 25, 65, 25, 55, 35, 45, 60, 75, 30, 120, 100, 60, 90, 85 sectors. If, after operating systems are installed, a disk can store up to 480 sectors, determine the number of disks needed to store the utilities if each of these heuristics is used to pack the disk with files.

59. Advertisements for the TV show are permitted to last up to a total of 8 minutes, and each group of ads can last up to 2 minutes. If the ads slated for last 63, 32, 11, 19, 24, 87, 64, 36, 27, 42, 63 seconds, determine whether FF and FFD yield acceptable configurations for the ads.

60. Consider the heuristic for packing bins known as best fit described as follows: Keep track of how much room remains in each unfilled bin and put the next item to be packed into that bin that would leave the least room left over after the item is put into the bin. (For example, suppose that bin 4 had 6 units left, bin 7 had 5 units left, and bin 9 had 8 units left. If the next item in the list had size 5, then first fit would place this item in bin 4, worst fit would place the item in bin 9, while best fit would place the item in bin 7.) If there is a tie, place the item in the bin with the lowest number. Apply this heuristic to the list 8, 7, 1, 9, 2, 5, 7, 3, 6, 4, where the bins have capacity 10.

61. We have described two algorithms for bin packing called worst fit and best fit (see page 97 and Exercise 60). The words best and worst have connotations in English. However, the performance of algorithms depends on their merits as algorithms, not on the names we give them.

62. The best-fit heuristic (see Exercise 60) also has a “decreasing” version, where the list is first sorted in decreasing order. Using bins of capacity 10, apply the best-fit heuristic and its decreasing version to the following list: 6, 9, 5, 8, 3, 2, 1, 9, 2, 7, 2, 5, 4, 3, 7, 6, 2, 8, 3, 7, 1, 6, 4, 2, 5, 3, 7, 2, 5, 2, 3, 6, 2, 7, 1, 3, 5, 4, 2, 6.

63. One pianist’s recording of the complete Mozart piano sonatas takes the following times (given in minutes and seconds): 13:46, 6:15, 3:29, 5:37, 7:52, 2:55, 5:00, 4:28, 4:21, 7:39, 7:55, 6:42, 4:23, 3:52, 4:21, 4:20, 5:46, 6:29, 5:34, 6:23, 6:39, 7:19, 5:54, 6:54, 2:58, 5:22, 1:42, 5:00, 1:29, 5:47, 7:30, 8:19, 4:44, 4:57, 4:09, 14:31, 3:55, 4:04, 4:01, 6:06, 6:50, 5:27, 4:28, 5:40, 2:52, 5:16, 5:34, 3:10, 7:22, 4:40, 3:08, 6:32, 4:47, 6:59, 5:38, 7:57, 3:38. If the maximum time that can be recorded on a compact disc is 70:30, can all the music be performed on four compact discs? Can all the music be performed on five compact discs?

64. In the wall-system example in the text, first fit and worst fit required equal numbers of bins (see Figure 3.20 on page 97). Can you find an example where first fit and worst fit yield different numbers of bins? Can you find an example where first fit, worst fit, and next fit yield answers with different numbers of bins?

65. A common suggestion for heuristics for the bin-packing problem with bins of capacity involves finding weights that sum to exactly . Discuss the pros and cons of a heuristic of this type.

66. A recording company wishes to record all the Beethoven string quartets (16 quartets, each consisting of several consecutive parts called movements) on reissued LPs. It wishes to complete the project on as few records as possible. Recording can be done on two sides as long as the movements are consecutive. Is this an example of a bin-packing problem? (Defend your answer.) If the project were to record the quartets on (standard) tape cassettes or compact discs, would your answer be different?

67. Give examples where it would be realistic to keep bins open as more items “arrive” to be packed, rather than to close a bin permanently based on some criterion.

68. Give examples where it would be unrealistic to keep bins open as more items “arrive” to be packed, rather than to close a bin permanently based on some criterion.

69. A data entry group must handle 30 (independent) tasks that will take the following amounts of time (in minutes) to type: 25, 18, 13, 19, 30, 32, 12, 36, 25, 17, 18, 26, 12, 15, 31, 18, 15, 18, 16, 19, 30, 12, 16, 15, 24, 16, 27, 18, 9, 14. Use these times as a priority list.

70. Find the minimum number of bins necessary to pack items of size 8, 5, 3, 4, 3, 7, 8, 8, 6, 5, 3, 2, 1, 2, 1, 2, 1, 3, 5, 2, 4, 2, 6, 5, 3, 4, 2, 6, 7, 7, 8, 6, 5, 4, 6, 1, 4, 7, 5, 1, 2, 4 in bins of capacity (a) through (d) using the FF and FFD algorithms. Can you determine whether any of the packings you get are optimal?

71. Two-dimensional bin packing refers to the problem of packing rectangles of various sizes into a minimum number of rectangles, with the sides of the packed rectangles parallel to those of the containing rectangle.

72. In what situations would packing bins of different capacities be the appropriate model for real-world situations? Suggest some possible algorithms for this type of problem.

73. Find an example of weights that, when packed into bins using first fit, use fewer bins than the number of bins used when the first-fit algorithm is applied with the first weight on the list removed.

74. Formulate “paradoxical” situations for bin packing that are analogous to those we found for scheduling processors.

3.5 Resolving Conflict via Coloring

75. Draw a connected graph with 12 vertices and 11 edges whose vertices can be colored with two colors.

76. Add a single edge to the graph you drew for Exercise 75 so that the vertices of the resulting graph cannot be colored with two colors but require three colors.

77. For each of the graphs below, answer the following questions.

78. For each of the accompanying graphs, answer the following questions.

79. The owner of a new pet store wishes to display tropical fish in display tanks. The accompanying table shows the incompatibilities between the species, in the sense that an X indicates that it is unwise to allow those species in the row and column that meet at the X to be in the same tank.

80. The managers of a zoo are planning to open a small satellite branch. The animals are to be in enclosures in which compatible animals are displayed together. The accompanying table indicates those pairs of animals that are compatible. (Thus, an X in a particular row and column means that the animals that label this row and column can share an enclosure.)

119

81. The nine standing committees of a state legislature are designing a schedule for when the committees can meet. The matrix shown in the following table has an X in a position where the committees corresponding to the row and column have a common member and, hence, should not be scheduled to meet at the same hour. The committees involved are Agriculture , Commerce , Consumer Affairs , Education , Forests , Health , Justice , Labor , and Rules .

82. Determine the minimum number of colors, and how often each color is used, in a vertex coloring of the graphs below.

83. The faculty-student governing council at All State College has nine standing committees (such as Curriculum, Academic Standards, Campus Life) that are designated for convenience. The following table shows which committees have no member in common:

84. When two towns are within 145 miles of each other, the frequency used by a certain type of emergency response system for the towns requires that they be on different frequencies to avoid possible interference with each other. The following table shows the mileage distances between six towns:

120

85. The legislature of a city has committees devoted to the following governmental areas:

; ; ; ; ; ; , . To schedule meetings for these committees in as few time slots as possible, consider the graph model below.

86. A small college has a mini-session in January (between its regular semesters) in which nine classes are offered: ; , ; ; , , , , . The accompanying table indicates those courses that have students in common.

87. Show that the vertices of any tree can be colored with two colors.

88. Can you find a family of graphs that require colors to color their vertices?

89. The edge-coloring number of a graph is the minimum number of colors needed to color the edges of so that edges sharing a common vertex get different colors. Determine the edge-coloring number for each of the graphs in Exercise 77. Can you make a conjecture about the value of the minimum number of colors needed to color the edges of any graph?

90. Can you think of any applications that require determining the minimum number of colors needed to color the edges of a graph?

91. When a graph has been drawn on a piece of paper so that edges meet only at vertices, the graph divides the paper up into regions called faces. The faces include one called the “infinite” face, which surrounds the whole graph. The face-coloring number of a graph (which can be drawn in this special way) is the minimum number of colors needed to color the faces of so that two faces sharing an edge receive different colors. (Note that if two faces meet only at a vertex, they can be colored the same color.)

92. For each of the graphs in Exercise 78 where the graph shown has edges that meet only at vertices, verify that the Four Color Theorem holds by showing that the regions (faces) of the graph can be colored with four or fewer colors so that regions sharing an edge get different colors. (Remember to assign a color to the unbounded, so-called infinite region.)

93. A company sells herbs, each of which requires a certain level of proper watering. The accompanying graph is constructed by having one vertex for each type of herb. The vertices representing two herbs are joined by an edge if they must have different levels of watering. What is the minimum number of terrariums that the herbs can be displayed in so that herbs in the same terrarium can be watered at the same level?

94. The company in Exercise 93 is disappointed by the minimum number of terrariums needed to display the herbs with the proper watering requirements. One company employee suggests that if the information about watering requirements is altered for a single pair of herbs (e.g., a single edge is erased from the diagram), then the number of terrariums needed will be reduced by 1. Is this true?

95. Each vertex in the graph below represents a child who attends a daycare center. An edge between two children indicates these children tend to cause problems when they are in the same play group. What is the minimum number of play groups that will ensure that no conflicts arise? Can conflict-free play groups with the same number of children in each group be formed?

Chapter Review

96. Determine the minimum number of time slots to schedule the seven committees represented by vertices in the accompanying graph, if edges show which committees cannot meet at the same time.

97. The regions of the accompanying map will appear in an atlas. If the surrounding region (infinite face) is to be colored blue, can the additional regions be colored so that all the regions can be colored with three or fewer colors? Regions sharing only a vertex can be colored with the same color.

98. Given the job (times shown in months) to publish a new edition of a book consisting of the tasks given in the order-requirement digraph below, answer the following questions.

99.