A Multi-Project Planning System
An Application to Shipbuilding
|W. Robert Terry||Ezey M. Dar-El|
|The University of Toledo||Technion — Israel Institute of Technology|
The problem of planning for an organization which is concurrently involved in the execution of several large scale projects is incredibly complex. However, U.S. shipyards which are prototypes of such organizations are not using any of the existing quantitative approaches for planning multiple projects in the face of resource constraints. This is surprising in view of the fact that completion delays and cost overruns indicate that better planning tools are badly needed.
An analysis of the factors which could be responsible for this paradox revealed that existing multi-resource/multi-project planning approaches fail to recognize the difference between the strategic and the tactical aspects of such planning problems. The failure to recognize this difference would overload both the strategic and tactical planners with irrelevant information — the strategic planner would be given too much detail while the planning horizon would be too long for the tactical planner. Therefore, an approach for decomposing the shipyard planning problem into strategic and tactical components was developed.
This paper, which is the first in a series of three papers, describes the approach for decomposing the problem into strategic and tactical components without detailing their solution procedures. The solution procedures for the strategic and tactical components of the problem are described in subsequent papers  and .
Organizations, such as large construction firms and shipyards, which become involved in the simultaneous execution of a number of large-scale one-of-a-kind projects, such as building an airport or a ship, face planning problems which are incredibly complex. Historically, the traditional approaches to planning used by the management of such firms have tended to result in completion delays and/or cost overruns. This situation has prompted a number of researchers to develop a variety of quantitative approaches for dealing with such problems. However, surveys by the authors have indicated that these quantitative approaches are not being utilized, suggesting that such approaches are not appropriate. This paper is aimed at identifying the potential problems and at developing approaches to their solution.
This paper uses a shipyard as a prototype of a firm which is typically involved in the simultaneous execution of a number of large-scale one-of-a-kind projects. Section II describes the complexity of the planning problem being faced in a typical U.S. shipyard. Section III analyzes the factors which could be responsible for the lack of use of quantitative approaches in shipyard planning. This section also shows the primary inhibiting factor to be the failure of existing approaches to distinguish between strategic and tactical aspects of the shipyard planning problem. This results in overloading the strategic planner with unneeded detail and requiring the tactical planner to deal with an excessive amount of uncertainty. Section IV describes an approach for decomposing the shipyard planning problem into strategic and tactical subproblems without describing in detail the procedures for solving these problems. Solutions to the strategic and tactical planning problem will be presented in subsequent papers  and , Section V contains a summary of this paper as well as an overview of the subsequent papers.
II. SHIPYARD PLANNING
II. A. A Complexity of the Shipyard
Building a ship is a large scale endeavor which requires the services of over forty construction trades , However, the rates at which the various trades are used in constructing a ship are not constant over time. During the early stages of construction, trades involved in constructing the hull, such as welders, shipfitters, riggers, loftsmen, hooker-on men, and flame cutters, will dominate the work force assigned to a given ship. During the later stages of construction, trades involved with outfitting, such as electricians, pipefitters, sheetmetal workers, and carpenters, will dominate the work force.
The number of workers in each trade that will be needed during each scheduling period is difficult to determine. This results from the fact that “in ship construction, the model is the product and everything which cannot be predetermined with paper studies must be tried out during production in the form of rework, change orders, or something else” [10, p. 19]. This ad hoc approach to ship construction makes it virtually impossible to determine a priori all of the activities which will be necessary to construct a ship. Consequently, shipbuilders are not able to establish standard methods to the extent that this is done for products that are produced continuously or in large lot sizes, making it difficult to develop accurate time standards which form the basis for estimating manpower requirements.
Not having the correct number of workers in each trade during each time period can be extremely costly. If too few workers are assigned to a bottleneck activity, then the ship will not be completed on time, incurring the following penalties: (1) late delivery payments, explicitly specified in the contract; and (2) opportunity cost. Typically, contracts for U.S. Navy ships do not explicitly contain late delivery penalty clauses. The opportunity cost for a 50 million dollar ship has been estimated to be at least $20,000 per day . A shipyard may take one or more the following actions when a planned delivery date is in jeopardy: (1) schedule overtime; (2) increase crew sizes; (3) postpone work until after launch; and (4) increase management involvement in day-to-day operation . On the other hand having too many workers could create idle time and increase labor cost unnecessarily.
Periodically, wage rates for the various trades and costs of the various raw materials increase as a result of inflation. However, these increases do not necessarily occur at the same time. The times at which increases in labor rates occur can be inferred from union contracts for the various trades and by examining the times in the past at which previous price increases have occurred for the various raw materials. Note that the rate of increase for each of the trades and for each of the raw materials will not necessarily be the same. Under a fixed cost contract, inflationary trends provide an incentive to the shipyard to complete a ship as early as possible. However, attempting to do this can result in intertrade and intratrade interferences.
It is obvious that constructing a ship is an enormously complicated process which involves a staggering number of diverse activities which, for each trade, are grouped in categories on the basis of spatial proximity. These categories are known as work packages. For example, the hull erection process and the outfitting process will be divided into approximately 2,500 work packages for each process. A typical work package requires approximately three months and 500 man-hours to complete .
These work packages cannot be scheduled independently of one another. In many instances there will be either a preferred sequence or a mandatory sequence in which certain of the work packages should be performed. When a preferred sequence is not followed unnecessary work will result. For example, suppose that the crane available at the erection site has the capacity to lift the main engine, whereas the one at the outfitting berth does not. Then, the main engine can be lifted aboard as an assembled unit prior to launching, whereas, after launching, it will be necessary to partially disassemble the main engine, lift the components separately and reassemble the engine on board where work space is limited . A mandatory sequence results when it is physically impossible to perform certain activities prior to others. For example, the electrical cable for a compartment cannot be installed before the compartment has been built. Another factor which precludes performing several work packages in parallel is limited work space. Interference results when too many workers from either the same or different trades are assigned to a confined workspace. Also certain trades are incompatible with one another. For example, none of the other trades can work in the area below welders. Another example, no trade can work in the same area as painters.
Cost will be incurred when the size of the work force is either increased or decreased. These costs have been classified into the following categories.
(1) cost of separation — exit interviewing, compensation, clerical processing;
(2) cost of unfilled position — lost output;
(3) cost of selection — advertising, screening, interviewing, clerical processing;
(4) cost of training — formal and informal instruction, operational damage;
(5) cost of output recovery — overtime, subcontracting, extra labor employed .
Hancock stated that the cost for “the leaving of one person and the hiring of a new one are from $600 to $2,000” [12, p. 7-113]. These costs do not account for the hyper inflation which has transpired since 1971. If an adjustment for this is made, then the current dollar equivalent of these costs would be approximately $1,500 to $5,000.
The typical shipyard has several ships in varying stages of completion at any given time. Each ship competes for a share of the shipyard’s manpower and facilities during each and every period in the planning horizon. Management’s task is to determine how the size of each trade’s workforce should be changed from period to period to minimize the sum of the following: (a) lateness penalty cost; (b) cost of changing the size of the workforce; (c) labor cost; and (d) materials cost. This type of problem is referred to as the multi-resource/multi-project (MRMP) planning problem.
II. B. Shipyard Planning Practices
The MRMP planning problem is a very real one in shipyards. This was evidenced by a study in which manufacturing executives and engineers in the major U.S. shipyards were asked to rank the causes of delays and cost overruns in shipbuilding . The most important finding of this survey was that 62.5 percent of the shipyards engaged in Naval construction ranked the unavailability of skilled labor as the most important cause of delays and cost overruns; 37.5 percent of the shipyards ranked improper sequence of assigned labor as the most important cause.
It is obvious from the discussion in the preceding subsection that the MRMP planning problems which shipyards must face are extremely complex and that the cost of making wrong decisions can be extremely high. This would suggest that shipyards should be keen on using MRMP planning models. In fact the first such model was described in a paper  entitled “Multi-Ship, Multi-Shop Workload Smoothing Program”. However a survey  revealed that not one out of a sample of 21 U.S. shipbuilders were using any of the existing MRMP planning models , ,  and . Furthermore, none were using any of the numerous multi-resource/single project models that had been developed. Davis  reviewed the state-of-the-art for such models up through mid-1972 covering 138 papers which he deemed relevant to the problem of project scheduling under resource constraints. Since this review other papers have appeared in the open literature , , , , , , and , The survey in 1979  also revealed that only half of the shipyards were using either PERT or CPM and that none were using either the probabilistic features of PERT or the time-cost features of CPM.
Why are shipyards not using the project planning tools which prima facie evidence suggests that they desperately need? The factors responsible for this are explored in the following section.
III. FACTORS RESPONSIBLE FOR LACK OF USE OF MULTI-RESOURCE/MULTI-PROJECT PLANNING MODELS
Several factors are identified which are suspected to be responsible for the failure of U.S. shipbuilders to use MRMP planning models. They are: (1) shipyard executives are not aware of the existence of such models; (2) the models are too complicated for shipyard personnel; (3) the models require data that could not be obtained at a reasonable cost; and (4) the models fail to recognize the fact that decisions concerning enterprise goals and the acquisition of resources are typically made at a higher management level than decisions concerned with the allocation of existing resources and (5) the models are insufficient, inappropriate or inadequate.
It is quite likely that many shipyard executives are not aware of the existence of MRMP planning models. These models are not usually covered in introductory operations research/management science courses. Most shipyard executives are not likely to be familiar with the journals in which these models have been described. Furthermore, most and perhaps all of the articles on MRMP planning, have not been written in a style which would appeal to and could be understood by most shipyard executives.
However, the biggest potential barrier to the use of such models arises from their data requirements. Current MRMP planning models require that the user specify the precedence relationships between the various activities involved in building a ship. The size and scope of a ship’s construction would result in a combinational problem too large and too expensive for any single heuristic MRMP planning model to handle.
Another barrier to implementing such models results from the fact that constructing a ship is partially an evolutionary process . Under such conditions it is not possible to identify a priori all of the important activities which will be involved in constructing a ship. In some situations during the planning stage, it is not always possible to specify which of several mutually exclusive approaches for accomplishing a given job will be optimal. These difficulties are compounded by the fact that “missing the date on one part of the construction cycle can cause several cascade effects on other parts” [3, p. D-9].
All of the models mentioned with the exception of some , , and , require that the total project scheduling problem be explicitly stated in order to determine the schedule for the next period. Consequently, they are not suitable for MRMP situations in which the definition of the project scheduling problem unfolds in an evolutionary manner as described in the paragraph above.
The survey of shipyard executives and engineers in 1979  revealed that most delays occurred in outfitting. The reason for this is that shipyards approach outfit planning on an informal basis in order to minimize overhead cost. However, this approach does not appear to be a sound one in view of the fact that the cumulative value added is very high at the outfit stage. Consequently, the lack of a relatively low cost outfit resource could create delays which cause large opportunity cost-losses.
The need for a more effective method for solving the MRMP planning problem is further emphasized by the fact that a sample of 296 Navy ships built since the early 1950’s, were finished on the average, 10.5 months late.’ This represents a great economic loss to both the shipbuilders and the nation.
The following section describes a theoretical framework which provides the basis for developing models for solving the MRMP planning problems of the size and difficulty faced by shipbuilders.
IV. THEORETICAL FRAMEWORK FOR DECOMPOSING MULTI-RESOURCE/ MULTI-PROJECT PROBLEMS INTO SOLVABLE PARTS
This section describes a two stage approach to decompose the MRMP planning problem into solvable parts: (1) decomposition of the total problem into strategic and tactical components; and (2) decomposition of activity network for the tactical component into sub-networks that can be handled separately.
IV. A. Decomposition into Strategic and Tactical Components
Anthony  provided a taxonomy which classifies planning decisions into two hierarchical levels: strategic planning and tactical planning. This taxonomy provides the basis for the first stage of decomposing the MRMP planning problem into manageable parts.
IV. A. 1. Strategic Planning
The purpose of strategic planning is to identify the goals of the enterprise, to evaluate the internal strengths and weaknesses of the enterprise, and to monitor the environment to identify problems/opportunities associated with accomplishing these goals. The information obtained from monitoring the environment and evaluating internal strengths and weaknesses typically gives rise to two types of questions: (1) How to solve the problems which the enterprise is likely to face in the future? (2) How to exploit the opportunities which are likely to occur? Answers to these questions enable the organization to identify the resources needed to achieve its objectives.
The resource needs of the organization are then translated into “broad brush” plans for acquiring the needed resources and disposing of those not required. This plan focuses attention on those resources that are costly and/or have long procurement lead times. This plan should specify what the levels of these major resources should be from period to period. In order to do this it will be necessary to determine how these resources should be deployed. However, detailed information on how the major resources should be deployed is not needed for the purposes of formulating this plan. The appropriate level of detail on the intended utilization of such resources should correspond to that needed to make an intelligent decision regarding whether or not the resources should be acquired.
The results of the strategic planning process create the environment in which tactical decisions must be made. The goal of strategic planning is to create an environment for tactical planning which is in some sense optimal. However, strategic decisions are made in the face of great uncertainty. As the future unfolds, uncertainty is reduced. Therefore, strategic plans need to be updated periodically to reflect the impact of intervening events.
IV. A. 2. Tactical Planning
Tactical planning is concerned with developing action plans for effectively utilizing available resources to accomplish short range objectives which have been derived from the strategic plan. Another function is to plan for the acquisition and disposal of resources as specified in the strategic plan. If the tactical planner is unable to meet the broad general objectives specified by the strategic plan, then the tactical planner should immediately advise the strategic planners of this situation. There are certain items of detailed information that are considered in the tactical planning process that are either ignored or dealt with in an aggregate form in the strategic planning process. Examples of this type of information are detailed precedence relationships and intercraft and intracraft interference.
IV. A. 3. Differences between Strategic and Tactical Planning
Any type of planning must be based on a forecast of what is likely to happen in the future. However, strategic planning and tactical planning differ in terms of the type of forecast required. Strategic planning requires a longer range forecast than tactical planning. On the other hand tactical planning requires a more detailed forecast than strategic planning. This suggests that the data base which supports tactical planning must be more detailed and updated more frequently than the one for strategic planning. The difference in data base requirements for strategic and tactical planning suggests that using a monolithic model which simultaneously solves both the strategic planning and the tactical planning problems will increase the size of the problem unnecessarily and largely explains why current MRMP algorithms are not being used. Furthermore, it overloads both the strategic and tactical planners with irrelevant information. The strategic planner is given too much detail while the planning horizon is too long for the tactical planner.
The strategic planner has two degrees of freedom which are not available to the tactical planner: (1) freedom to shift target completion dates; and (2) freedom to vary the levels of the various resources from period to period. Making such decisions at the tactical level is undesirable due to the enormous potential cost of a wrong decision and the limited purview of the tactical planner. However, information indicating a need to revise the strategic plan will not always surface at the strategic management level. When it surfaces at a lower level it should be immediately transmitted to the strategic level.
The inputs to the strategic planning process occur on a more random and less predictable basis than do inputs to the tactical planning process. This suggests that strategic planning should be done on an exception basis while tactical planning should be done on a periodic basis. The rational for this practice is that the time and cost associated with generating a strategic plan are too great to be squandered unnecessarily. What is needed is a more efficient and cost effective means of doing strategic planning, one which is more responsive to important changes in both “internal” and “external” environments. Less important changes should be handled informally if the cost of revising the strategic plan exceeds the benefits of doing so.
IV. B. Decompose Activity Network
IV. B. 1. Need to Simplify
The tactical shipyard planning problem is concerned with allocating each trade’s limited workforce to the various activities competing for their services. Shipyard management would obviously like to make this allocation in the most effective manner. However, formulating a mathematical model of this problem could result in a combinatorial problem of immense proportions. In addition, there can be major uncertainties associated with a number of activities required to construct the ships, and would therefore be well beyond the capabilities of existing models. However, it will be seen in Section IV. B. 4. that the very uncertainty associated with the activities provides an opportunity to simplify the tactical model.
IV. B. 2. Large Number of Activities
Approximately 5,000 work packages (roughly split 50-50 between hull erection and outfitting) are involved in constructing the typical ship  which utilizes about 40 trades for its completion , The average work package requires about three months to complete, and is scheduled in either a mandatory sequence or a preferred sequence.
An enormously large and complicated activity network would be necessary for describing the numerous precedence and incompatability relationships which exist between the 5,000 or so work packages involved in constructing a ship. In a typical shipyard there will be a number of ships under construction at the same time. Thus, at any point in time, the number of work packages at the planning stage in a given shipyard, could run into tens of thousands. Furthermore, these activities will be competing for the limited number of workers in each trade’s workforce.
IV. B. 3. Uncertainty in Construction Process
In addition to the large number of activities, the problem of determing how to allocate each trade’s workforce to the various activities is further complicated by the great amount of uncertainty in the construction process. This uncertainty manifests itself in two forms: (1) The activity duration times are influenced by a large number of factors which cannot be controlled due to the somewhat exploratory nature of shipbuilding . This makes it difficult to accurately estimate the durations for the various activities. (2) The set of activities necessary for constructing a ship cannot be accurately foreseen. Factors beyond the control of shipyard management can cause the set of activities to change. Frisch [10, p. 40] gives the following examples of such activities: “a subcontractor may not be able to deliver; new weapon developments must be accommodated; weather in open building areas influences worker efficiency.”Changes in the set of activities necessary to construct a ship can also be caused by decisions made by shipyard management.
Changes in the set of activities necessary to construct a ship caused by factors beyond the control of shipyard management can be modeled by simulation languages such as GERT  and TRANSIM  which permit one of several mutually exclusive arcs leading from a node to be determined probablistically. However, such a simulation model could not be used to specify how to allocate each crafts workforce to the various work packages. Changes in the set of activities necessary to construct a ship caused by shipyard management decisions can be modeled by the use of Decision CPM , This technique utilizes total project cost as the basis for selecting a job method from a set of mutually exclusive job methods. Unfortunately, this technique is not able to handle uncertainty which results from either random activity durations or from activities which cannot be foreseen.
IV. B. 4. Use of Uncertainly in Defining Planning Horizon
On the basis of the above, it would appear that the uncertainty in the ship construction process would make a problem which is already hopelessly difficult even more difficult. Fortunately, this need not be the case. This uncertainty can actually be used to decompose the activity networks for each ship into a number of subnetworks. The rational for doing this rests on the belief that detailed plans should be based on hard facts, indicating that detailed plans should be developed for only those parts of the activity network for which all necessary activities of a major nature can be clearly foreseen.
The horizon for tactical planning should not extend past the point in the activity network at which the first major uncertain activity occurs. For example, suppose there is a question as to whether or not the main engine can be built in time to be installed prior to launch. If the engine were ready prior to launch, it could be installed as a unit. If not ready prior to launch, then insufficient crane capacity at the outfit pier would dictate that it be partially disassembled, lifted aboard piece by piece and reassembled in situ which itself represents an additional activity. Furthermore, workspace will be more limited after launch. Thus, installing the main engine post-launch might necessitate using a vastly different work method than required for a pre-launch installation. In addition, freeing up the necessary space for assembling the main engine on board might necessitate drastic changes in the sequence in which certain outfitting activities could be performed. Thus, it should be obvious that the occurrence of uncertain events could drastically alter the nature of the remainder of the project. Thus it does not seem prudent to develop detailed plans beyond these points.
V. SUMMARY AND OVERVIEW OF SUBSEQUENT PAPERS
The problems of planning for an organization which is concurrently involved in the execution of several large scale projects are incredibly complex. However, U.S. shipyards which are prototypes of such organizations are not using any of the existing quantitative approaches for planning multiple projects in the face of resource constraints. This is surprising in view of the fact that completion delays and cost overruns indicate that better planning tools are badly needed.
An analysis of the factors which could be responsible for the paradox revealed that existing MRMP planning approaches fail to recognize the difference between the strategic and the tactical aspects of such planning problems. The failure to recognize this difference would require a prohibitively large database. It would also overload both the strategic and the tactical planners with irrelevant information — the strategic planner would be given too much detail while the planning horizon would be too long for the tactical planner. Therefore, an approach for decomposing the shipyard planning problem into strategic and tactical components was developed. The solutions of these problems are described in detail in two subsequent papers.
1 Anthony, R.N., Planning and Control Systems: A Framework for Analysis, Division of Research Harvard Business School, Boston, 1965.
2 Corlett, E.N. & J.B. Coates, “Cost and Benefits from Human Resource Studies,” International Journal of Production Research, 1976.
3 Corporate-Tech Planning, Inc., Production Oriented Planning: A Manual on Planning and Production Control for Shipyard Use Corporate-Tech Planning, Inc., 1978.
4 Crowston, W.O. & G.L. Thompson, “Decision CPM: A Method for Simultaneous Planning, Scheduling and Control of Projects,” Operations Research, 1967.
5 Dar-El, E.M., A Behmoaram & Y. Tur, “SCREAM-Scarce Resource Allocation to Multi-projects,” Project Management Quarterly, 1978.
6 Dar-El, E.M. & Y. Tur, “A Multi-resource Project Scheduling Algorithm,” AIIE Transactions, 1977.
7 Dar-El, E.M. and Y. Tur, “Resources Allocation of a Multi-Resource Project for Variable Resource Availabilities,” AIIE Transactions, 1978.
8 Davis, E.W. “Project Scheduling under Resource Constraints-Historical Review and Categorization of Procedures,” AIIE Transactions, 1973.
9 Davis, E.W. & J.H. Patterson, A Comparison of Heuristics and Optimum Solutions in Resource-constrained Project Scheduling, Management Science, 1975.
10 Frisch, F.A.P., Production and Construction: A Comparison of Concepts in Shipbuilding and Other Industries, Washington, D.C.: U.S. Department of the Navy.
11 Frisch, F.A.P., Personal communication, 1979.
12 Hancock, W.M., “The Learning Curve, in Industrial Engineering Handbook,” H.B. Maynard (Ed), McGraw-Hill, pp. 7-113., 1971.
13 Herroelen, W.S., “Resource Constrained Project Scheduling — The State of the Art,” Operational Research Quarterly, 1973.
14 Lambourne, S., “Resource Allocation and Multiproject Scheduling (RAMPS) — A New Tool in Planning and Control,” The Computer Journal, 1963.
15 Levy, F.K., G.L. Thompson, & J.J. Wiest, “Multi-Ship, Multi-Shop, Workload Smoothing Program, Naval Research Logistics Quarterly, 1962.
16 McMichael, D. & B.S. Orleans, TRANSIM — A General Purpose Problem Solving Tool, 1975.
17 Mark Battle Associates, Inc., Shipbuilding Manpower Study: Executive Summary, Mark Battle Associates, Inc., 1974.
18 Patterson, J.H. “Alternate Methods of Project Scheduling with Limited Resources,” Naval Research Logistics Quarterly, 1973.
19 Patterson, J.H. & W.D. Huber, “A Horizon-Varying, Zero-One Approach to Project Scheduling,” Management Science, 1974.
20 Pritsker, A.A.B., Q-GERT: GERT Networks with Queueing Capabilities, Purdue University, Research Memorandum, 1972.
21 Pritsker, A.A.B., L.J. Watters, & P.M. Wolfe, “Multi-Project Scheduling with Limited Resources: A Zero-One Programming Approach,” Management Science, 1969.
22 Terry, W.R. & E.M. Dar-El “Tactical Planning for Multi-Projects — An Application to Shipbuilding,” Technical Report UTEC ME 80-147, Department of Mechanical and Industrial Engineering, University of Utah, 1980 B
23 Terry, W.R. & E.M. Dar-El “Strategic Planning for Multi-Projects — An Application to Shipbuilding,” UTEC ME 80-148, Department of Mechanical and Industrial Engineering, University of Utah, 1980 B.
24 Terry, W.R., F. Green & A. Magnuson, Confidential Survey of U.S. Shipyards Conducted By the Industrial Engineering/Operations Research Department at Virginia Polytechnic Institute and State University, 1979.
25 Wiest, J.D., “A Heuristic Scheduling and Resource Allocation Model for Evaluating Alternative Weapon System Programs,” RAND Corp. Report No. RM-5769-RP., 1969.
1The basis for this sample was ship progress curves maintained by the Naval Sea Systems Command.