Review Vocabulary

105

Average-case analysis The study of the list-processing algorithm (more generally, any algorithm) from the point of view of how well it performs in all the types of problems it may be used for and seeing on average how well it does. See also worst-case analysis. (p. 94)

Bin-packing problem The problem of determining the minimum number of containers of capacity , … , () can be packed. (p. 96)

Chromatic number The chromatic number of a graph is the minimum number of colors (labels) needed in any vertex coloring of . (p. 101)

Critical-path scheduling A heuristic algorithm for solving scheduling problems where the list-processing algorithm is applied to the priority list obtained by listing next in the priority list a task that heads a longest path in the order-requirement digraph. This task is then deleted from the order-requirement digraph, and the next task placed in the priority list is obtained by repeating the process. (pp. p. 91 p. 92)

Decreasing-time-list algorithm The heuristic algorithm that applies the list-processing algorithm to the priority list obtained by listing the tasks in decreasing order of their time length. (p. 94)

First fit (FF) A heuristic algorithm for bin packing in which the next weight to be packed is placed in the lowest-numbered bin already opened into which it will fit. If it fits in no open bin, a new bin is opened. (p. 97)

First-fit decreasing (FFD) A heuristic algorithm for bin packing where the first-fit algorithm is applied to the list of weights sorted so that they appear in decreasing order. (p. 98)

Heuristic algorithm An algorithm that is fast to carry out but that doesn’t necessarily give an optimal solution to an optimization problem. (p. 96)

Independent tasks Tasks are independent when there are no edges in the order-requirement digraph. These are tasks that can be performed in any order. (p. 93)

List-processing algorithm A heuristic algorithm for assigning tasks to processors: Assign the first ready task on the priority list that has not already been assigned to the lowest-numbered processor that is not working on a task. (p. 84)

Machine-scheduling problem The problem of assigning tasks to processors so as to complete the tasks by the earliest time possible. (p. 82)

Next fit (NF) A heuristic algorithm for bin packing in which a new bin is opened if the weight to be packed next will not fit in the bin that is currently being filled; the current bin is then closed. (p. 97)

Next-fit decreasing (NFD) A heuristic algorithm for bin packing where the next-fit algorithm is applied to the list of weights sorted so that they appear in decreasing order. (p. 98)

Priority list An ordering of the collection of tasks to be scheduled for the purpose of attaining a particular scheduling goal. One such goal is minimizing completion time when the list-processing algorithm is applied. (p. 83)

Processor A person, machine, robot, operating room, or runway with time that must be scheduled. (p. 82)

Ready task A task is called ready at a particular time if its predecessors, as given by the order-requirement digraph, have been completed by that time. (p. 84)

Vertex coloring A vertex coloring of a graph is an assignment of labels, which can be thought of as “colors,” to the vertices of G so that vertices joined by an edge get different labels (colors). (p. 101)

Worst-case analysis The study of the list-processing algorithm (more generally, any algorithm) from the point of view of how well it performs on the hardest problems it may be used on. See also average-case analysis. (p. 94)

Worst fit (WF) A heuristic algorithm for bin packing in which the next weight to be packed is placed into the open bin with the largest amount of room remaining. If the weight fits in no open bin, a new bin is opened. (p. 97)

Worst-fit decreasing (WFD) A heuristic algorithm for bin packing where the worst-fit algorithm is applied to the list of weights sorted so that they appear in decreasing order. (p. 98)