Planning, scheduling, and control are three of the most critical activities in an organization. The success of any project, public or private, depends on how effectively these activities are carried out and the kinds of operational tools one uses to undertake them. One such operational tool that is frequently used in this context is network analysis. For large and complex projects where time could be a major factor, network analysis plays a vital role by identifying the most efficient schedule for completing a project. Network analysis also provides an excellent tool for establishing the work sequence well in advance of the actual undertaking of a project, thereby allowing the decision makers the opportunity to monitor progress and correct potential problem areas. In addition to this, it helps in the allocation of resources by redefining the work relationship that can expedite the achievement of project goals and objectives.
A number of network problems have been developed to date. This chapter presents four such problems that are among the most frequently used in network analysis: the shortest-route problem, the minimal spanning-tree problem, the maximal flow problem, and CPM/PERT for planning and control. But before discussing these specific problems, the chapter briefly introduces several terminologies that serve as a precursor to network analysis and can be used as a guide to solving practical problems.
Network analysis has its origins in the more general theory of graphs. A graph is an interconnected network of elements consisting of nodes, called vertices, and branches, called edges or lines. A node is a point that is usually denoted by a circle and connected by one or several branches. Nodes generally represent locations, such as communities, service stations, bus terminals, and so on, while branches represent flow of goods, services, messages, distance, time, etc. Branches in a graph may or may not have directions. If every branch in a graph has a direction, it is called a directed graph; if it does not, it is called an undirected graph. If, on the other hand, some of the