Strategic Planning for MultiProjects
An Application to Shipbuilding
The University of Toledo
Ezey M. DarEl
TechnionIsrael Institute of Technology
Editor’s note – This article is the second in a three part series by Terry and DarEl concerning planning in the shipbuilding industry. Their first article, “A MultiProject Planning System—An Application to Shipbuilding,” appeared in the June 1982 Project Management Quarterly.
Precis
A previous article [12] has observed that: (1) shipyards face multiresource/multiproject (MRMP) planning problems that are incredibly complex, (2) the prevalence of completion delays and cost overruns indicate that better planning tools are badly needed and, (3) U.S. shipyards are not using any of the existing approaches to planning multiple projects in the face of resource constraints. To help alleviate this situation Patterson [12] proposed that the MRMP problem be decomposed into strategic and tactical components. However, details for solving the strategic and tactical problems were not given there. The purpose of this article is to describe the approach for solving the strategic problem.
The problem of strategic planning for multiprojects involves: (1) establishing target completion dates for each of the projects; and (2) specifying how the size of each trade’s workforce should be varied as a function of time. The objective is to determine the combination of target completion dates and workforce profiles which will minimize the sum of the cost of changing the size of the workforce and lateness penalty charges for late delivery. This problem was formulated as a mixed integer quadratic programming problem. The projection technique was used to develop an algorithm for solving this problem.
Introduction
The problems of planning for the execution of several largescale projects were discussed in an earlier article by the same authors [13] and were shown to be incredibly complex. It was also shown that 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 was most surprising since 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 multiresource/multiproject (MRMP) planning approaches fail to differentiate between the strategic and the tactical aspects of such planning problems. As a consequence, applying these models, for example, to shipyards, 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.
An approach was proposed in an earlier article [13] for decomposing the shipyard planning problem into strategic and tactical components in order to effectively solve the MRMP planning problem. This article describes the detailed approach for the strategic should be changed from period to period.
Strategic planning is also concerned with determining the most appropriate: (1) financial structure; (2) manufacturing technology; (3) portfolio of assets; and (4) organization structure. The results of these planning problem. The approach to the tactical planning problem is discussed in a later article [14].
Figure 1 Information Flows in the Planning Process
The relationship between strategic planning, tactical planning, and project execution is shown in Figure 1. This figure shows the flows of information which are involved in the process of converting strategic plans into the appropriate forms of action and for ensuring that these actions are executed on a timely basis.
Problem Definition
At the strategic level, shipyard management is concerned with: (1) determining target completion dates for the various ships under construction; and (2) specifying how the workforce levels for each trade decisions determine the environment in which the strategic shipyard plan must be formulated. As such they can be regarded as superstrategic decisions. For the purposes of the present discussion it will be assumed that the above types of superstrategic decisions have already been made.
Literature Review
None of the MRMP planning models reported in the open literature simultaneously considers both workforce levels and target completion dates as decision variables. Fendley [2] assumed that resource levels were fixed and considered target project completion dates as decision variables. A number of planning models [6], [8], [9], [10], [12], [15] have been developed based on the assumption that due dates for the various projects are fixed. DarEl and Tur [1] developed a model which determines resource levels for a single project so as to minimize the “weighted deviation squares between resource loads and currently assigned levels.” In this model they assumed that the resources required to perform each of the activities were fixed. Penalties for splitting activities and for not scheduling critical activities can be added to the weighted deviation squares. These penalty charges can be varied so as to generate a set of solutions corresponding to different project durations. Bit level storage was used to generate the set of feasible activity combinations for each day. In FORTRAN the unit of storage is a computer word consisting of 32 bits for an IBM 360. Thus, the use of bit level storage makes it possible to reduce storage requirements by a factor of 32 for an IBM 360. It will also result in a substantial reduction in computer effort since logic operations require less time at the bit level than the word level. Nevertheless, these computational refinements will not be sufficient to allow their algorithm to be generalized to handle MRMP problems in which both target completion dates and resource levels are decision variables.
Economic Impact of Completion Dates and Workforce Levels
Clearly, the stateoftheart as reported in the literature review section above suggests that a new model be developed for solving MRMP planning problems. A prerequisite for developing a model for the strategic shipyard planning problem is a clear understanding of how workforce levels and project completion dates impact cost.
Note that the total cost of the portfolio of ships under construction is not influenced by the completion date of a given ship up to the time at which the completion date exceeds the due date. After the due date, cost increases due to the lateness penalty charges for the ship which is late. However, being late on one project can create a series of events which can cause the cost of other projects to increase. For example, being late on one ship might delay the start of a number of other ships. This could increase costs in several ways. Lateness penalty charges could be incurred on subsequent ships which would not have been incurred otherwise. However, it might be possible to reduce these lateness penalty charges by temporarily increasing the size of the workforce, but this will cause certain additional costs to be incurred. When the workforce is expanded it will be necessary to: (1) recruit; (2) interview; (3) test; (4) examine; (5) place; and (6) train the new employees. Reducing the size of the workforce can involve: (1) exit interviews; (2) separation payments; (3) increased premiums for employment insurance; and (4) a bad image in the local labor market.
Wage rates for each of the trades and unit costs for the various materials will tend to increase abruptly at discrete points in time due to inflation. For a particular trade both the points in time at which such increases occur and their amounts can often be determined from the multiyear union contracts. A similar type step function will typically exist for each of the trades and each of the raw materials. For many raw materials price increases tend to be announced at specified times during the year. Forecasting the size of such increases will require an analysis of the factors which influence both the supply and demand for the material in question. Labys [5] provides a comprehensive account of econometric models of commodity markets. Such a model can be useful in predicting increases in material costs. Inflation in wage rates for the various trades and unit cost of raw materials cause total cost to increase as the duration of a particular ship construction project increases.
The time required to complete a given ship will depend on the number of workers for each trade assigned to work on it during each time period. This is illustrated by Figure 2 which shows two hypothetical percentage completion curves for constructing a given ship.
Figure 2 Impact of Start Date and Labor Application Rates on Completion Time.
The most obvious way in which completion dates influence cost is through late delivery penalty charges. The penalty cost for late delivery consists of: (1) penalty payments for late delivery explicitly specified in the contract; and (2) opportunity costs of the shipyard facilities tied up by the late delivery. In theory, bonuses for early delivery are possible. However, they are rarely encountered in practice and will not be considered as part of the model developed in the following section. Figure 3 illustrates how the total cost of a portfolio of projects behaves as the completion date of a single ship is varied given that all other variables which influence total costs are held constant.
Figure 3 Impact of Completion Date on Total Cost
Model Formulation
The strategic shipyard planning problem is to determine the target completion dates and workforce levels for each trade during each period in the planning horizon such that total relevant cost will be minimized. The following notation will be used in formulating a mathematical model of this problem:
In formulating this model it was assumed that:
(1) all hiring and laying off is done at the beginning of each time period;
(2) shipyard facilities are adequate and that lack of such facilities will not constitute a major source of delay;
(3) both intertrade and intratrade interference are negligible;
(4) overtime is not permitted (overtime is used as additional reserve capacity for tactical problems);
(5) strict precedence relationships, which specify that activity B cannot be started until activity A has been completed, are not necessary in view of the resulting long time periods used in strategic planning.
The last three assumptions are made to reduce the size and complexity of the problem so that it will be solvable. However, these factors will be explicitly considered in the tactical shipyard planning model.
Total relevant costs consists of the sum of: (1) cost of late deliveries; (2) labor costs; (3) materials costs; (4) hiring costs; and (5) layoff costs.
The cost of late delivery is given by
If ship j is not completed until period Dj + n then penalty costs will be incurred in periods Dj + 1 to Dj + n. This results from the fact that the binary decision variable zjt was defined to be equal to one for the case in which construction on ship j is permitted during period t.
Labor costs for the shipyard are given by the following expression:
Material costs are given by:
This equation is based on the assumption that trade i consumes materials at the rate of k_{ij} units of material per labor hour working on ship j.
The cost of hiring additional workers is given by:
while the cost of laying off workers is given by:
Thus the objective is to minimize the sum of the quantities in Equations 1 through 5 subject to a number of constraints which must be satisfied in order for a solution to the problem to be valid.
This constraint states that the total number of hours of trade i assigned ship j during the periods in the planning horizon must be equal to the total number of hours of trade i needed to construct ship j.
This constraint states that the total number of hours of trade i assigned to each of the J ships under construction during time period t must not exceed the number of hours available in the trade i workforce.
This constraint states that the size of the craft i workforce at time t is equal to its size during the preceeding period adjusted for the number of workers hired and laid off during that period.
This constraint states that there is a limit to the number of workers in trade i that can be hired during time period t.
This constraint states that there is a limit to the number of workers in trade i that can be laid off during time period t.
This constraint states that the cumulative number of hours of trade i assigned to ship j cannot exceed the cumulative number of hours of trade g assigned to ship j multiplied by a factor r_{igj} which represents the ratio of total number of hours required for trade i to the total number of hours required for trade g on ship j. This constraint is needed for only those situations in which the cumulative progress of one trade restricts the cumulative progress of another trade. For example, such a constraint would be needed to reflect the fact that the tons of steel plates welded into place cannot exceed the tons of plates that have been cut. In addition to the above constraints the decision variables are restricted to the ranges defined below.
The model as formulated above limits attention to a finite number of future time periods. The typical shipyard will continue to exist well beyond this time. Thus, it is necessary to ensure that the sizes of the workforces for the various trades be consistent with operations beyond that point.
If periods beyond the planning horizon are ignored, then the model as formulated could recommend dismissing all employees at the end of the recommended horizon. Fortunately, this problem can be handled by specifying a minimum size for the workforce for each craft at the end of the planning horizon.
It is possible that not all ships in the shipyards order backlog can be completed by the end of the planning horizon. When this arises it will be necessary to specify the amounts of work which must be done on each ship during the horizon.
The above model is a mixed integer quadratic programming problem. A procedure for solving this problem is described in the following section.
Solution Strategy
To date there have been no algorithms developed for solving the mixed integer quadratic programming problem that was formulated in the preceding section. A strategy which can be used to solve this problem consists of using the projection technique [3]. Application of this technique to the current problem involves use of a transformation that temporarily fixes the binary decision variables, z_{jt}, which are used to indicate whether or not construction on ship j is permitted during period t. The resulting problem, with binary decision variables fixed, will be referred to as the “inner minimization” problem. The problem which results from this transformation is imbedded in an “outer minimization” problem, the objective of which is to determine the optimum target completion date for each ship.
The process of fixing the binary decision variables results in an inner minimization problem which is a linear programming problem. This linear programming problem is imbedded in the outer minimization problem which is a integer optimization problem.
To solve the integer problem, a modified HookeJeeves pattern search algorithm can be employed. The conventional HookeJeeves method [2] evaluates the objective function of the unconstrained optimization problem in order to determine how the values of the decision variables should be perturbed. In the present application the value of the objective function for the outer minimization problem is determined by solving the LP problem which characterizes the inner minimization problem. Based on the outcome of the inner minimization LP problem, the HookeJeeves pattern search selects a set of values for integer variables which represent the target completion dates for each ship. The LP problem which corresponds to those completion dates is then solved. This procedure is repeated until there is no further improvement in the objective function value. Thus, the HookeJeeves algorithm was modified so that the simplex algorithm could be used to determine the value of the objective function for the unconstrained optimization problem. The flow chart for the modified HookeJeeves pattern search solution procedure is show in Figure 4.
Commercial linear programming codes appear to be able to handle real world size strategic shipyard planning problems. Lasdon [7] has noted that such codes are capable of handling problems with 8,000 to 16,000 rows provided sufficient core storage is available. He also notes that even larger problems with generalized upper bounding structure can be solved and notes that Hirschfeld [4] has reported solving a 50,000 row problem with generalized upper bounding structure. This is most encouraging since the strategic shipyard planning problem has a generalized upper bounding structure.
This linear programming problem will have to be solved a number of times since it is the inner maximization problem. However, the nature of the strategic shipyard planning problem is such that composition of the optimal basis for the linear programming problem should not change appreciably from one search iteration to the next. This situation can be exploited to reduce computation time by utilizing the capacity of commercial linear programming codes to save a previous optimal basis so as to provide an advanced starting solution for a subsequent problem [11].
Figure 4 Flowchart for Modified HookeJeeves Procedure
The solution to the LP problem in the inner minimization problem specifies how the available resources should be allocated to the activities associated with constructing the various ships. The HookeJeeves pattern search specifies how the target delivery dates for each ship should be varied to reduce total cost. By alternately solving the LP inner minimization problem and the unconstrained outer minimization problem a local optimal solution will be reached. The stopping criterion for the HookeJeeves algorithm indicates when this has occurred.
Conclusion
The problem of strategic planning for multiprojects involves: (1) establishing target completion dates for each of the projects; and (2) specifying how the size of each trade’s workforce should be varied as a function of time. The objective is to determine the combination of target completion dates and workforce profiles which will minimize the sum of the cost of changing the size of the workforce and lateness penalty charges for late delivery. This problem was formulated as a mixed integer quadratic programming problem. The projection technique was used to develop an algorithm for solving this problem.
References
[1] DarEl, E.M. and Y. Tur, “Resource Allocation of a MultiResource Project for Variable Resource Availabilties,” AIIE Trans., 1978.
[2] Fendley, L., “Towards the Development of a Complete MultiProject Scheduling System,” Journal of Industrial Engineering, 1968.
[3] Geoffrion, A., “Elements of LargeScale Mathematical Programming,” Management Science, July, 1970.
[4] Hirschfeld, D., “Mathematical Programming Development of Management Science Systems, Inc.,” Presented at SHARE 38, March, 1972.
[5] Labys, W.C., Dynamic Commodity Models: Specifications Estimation and Simulation, Lexington, Mass: D.C. Heath & Co., 1973.
[6] Lambourne, S., “Resource Allocation and Multiproject Scheduling (RAMPS)—A New Tool in Planning and Control,” Computer Journal, 1963.
[7] Lasdon, L.S., “Large Scale Programming,” in Moder, J. and Elmaghraby, E., Handbook of Operations Research Models and Applications, Volume 2, New York: Van Nostrand Reinhold Company.
[8] Levy, F.K., G.L. Thompson, and J.J. Wiest, “MultiShip, MultiShop, Workload Smoothing Problem,” Naval Research Logistics Quarterly, 1962.
[9] McGee, A.A., and M.D. Markarian, “Optimum Allocation of Research/Engineering Manpower Within a MultiProject Organizational Structure,” IRE Transactions Engineering Management, 1962.
[10] Moshman, M., I. Johnson, and W. Larsen, “RAMPS—A Technique for Resource Allocation and MultiProject Scheduling,” Proceedings Spring Joint Computer Conference, 1963.
[11] OrchardHays, W., “On the Proper Use of a Powerful MPS,” in Cottle, R.W. and J. Krarup, Optimization Methods, New York: Crane, Ruscak and Co., Inc., 1974.
[12] Patterson, J.H., “Alternate Methods of Project Scheduling with Limited Resources,” Naval Research Logistics Quarterly, 1973.
[13] Terry, W.R. and E.M. DarEl, “A MultiProject Planning System – An Application to Shipbuilding,” Technical Report UTEC ME 80143, Department of Mechanical and Industrial Engineering, University of Utah, Salt Lake City, Utah, 1980A and Project Management Quarterly, June, 1982.
[14] Terry, W.R. and E.M. DarEl, “Tactical Planning for MultiProjects,” Technical Report UTEC ME 80147, Department of Mechanical and Industrial Engineering, University of Utah, Salt Lake City, Utah, 1980C.
[15] Wiest, J.D., “A Heuristic Model for Scheduling Large Projects with Limited Resources,” Management Science, February, 1967.
Editor’s Note: Readers may wish to refer to these recent articles regarding the shipbuilding industry.
“Feast or Famine in Shipbuilding,” Business Week, 28 June 1982, pp. 132137.
Bill Paul, “Shipbuilding Industry in U.S. Flounders As Federal Aid Ebbs and Navy Orders Lag,” The Wall Street Journal, 25 May 1982, p. 34, col. 1.
Have a question about the Seminar/Symposium in Toronto? Listen to a three minute recorded message between 5:00 p.m. and 9:00 a.m. Eastern Daylight Savings time. What to wear, all about customs, making plane reservations, exchange rates, etc. Call (215) 6221796.
A Decade of Project Management: Selected Readings from the Project Management Quarterly 1970 through 1980 by John R. Adams, Ph.D. and Nicki S. Kirchof. Available from Drexel Hill or at 1982 Seminar/Symposium.
Advertisement
Advertisement
Related Content

Pulse of the Profession 2020
Are you future ready? Our Pulse of the Profession^{®} research shows that organizations that prioritize maturing their delivery capabilities enjoy more successful outcomes.
Advertisement