×

Computational experience with a backtracking algorithm for solving a general class of precedence and resource-constrained scheduling problems. (English) Zbl 1403.90678

Summary: In this paper, computational results are presented with a very general, yet powerful backtracking procedure for solving the duration minimization and net present value maximization problems in a precedence and resource-constrained network. These networks are generally of the PERT/CPM variety, although it is not required that they be so. Among the advantages cited for our approach are low computer memory (storage) requirements and the ability to obtain improved solutions rapidly (heuristic properties). Since the resource-constrained project scheduling problem subsumes the job shop, flow shop, assembly line balancing, and related scheduling problems, our procedure can be used with little or no modification to solve a wide variety of problem types. Computational experience is reported for both mainframe and personal computer implementations.

MSC:

90C90 Applications of mathematical programming
90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
90C35 Programming involving graphs or networks

Software:

Algorithm 520
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Blazewicz, J.; Cellary, W.; Slowinski, R.; Weglarz, J., Scheduling under resource constraints — deterministic models, (1986), J.C. Baltzer AG Basel
[2] Davis, E.W., Project scheduling under resource constraints — historical review and categorization of procedures, AIIE transactions, 5, 4, 297-312, (1973)
[3] Davis, E.W., An exact algorithm for the multiple constrained-resource project scheduling problem, (May 1968), Yale University, Unpublished Ph.D. Dissertation
[4] Davis, E.W.; Heidorn, G.E., An algorithm for optimal project scheduling under multiple resource constraints, Management science, 17, 12, B803-B816, (1971) · Zbl 0224.90030
[5] Davis, E.W.; Patterson, J.H., A comparison of heuristic and optimal solutions in resource-constrained project scheduling, Management science, 21, 8, 944-955, (1975)
[6] Elmaghraby, S.E., Activity networks: project planning and control network models, (1977), Wiley New York · Zbl 0385.90076
[7] Doersch, R.H.; Patterson, J.H., Scheduling a project to maximize its present value: A zero-one programming approach, Management science, 23, 8, 882-889, (1977) · Zbl 0354.90043
[8] Hindelang, T.J.; Muth, J.F., A dynamic programming algorithm for decision CPM networks, Operations research, 27, 2, 225-241, (1979) · Zbl 0396.90097
[9] Patterson, J.H., A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem, Management science, 30, 7, 854-867, (1984)
[10] Patterson, J.H.; Huber, W.D., A horizon-varying, zero-one approach to project scheduling, Management science, 20, 6, 990-998, (1974) · Zbl 0303.90026
[11] Patterson, J.H.; Roth, G.W., Scheduling a project under multiple resource constraints: A zero-one programming approach, AIIE transactions, 8, 4, 449-455, (1976)
[12] Patterson, J.H.; Slowinski, R.; Talbot, F.B.; Weglarz, J., (), Chapter 1 in
[13] Pritsker, A.B.; Watters, L.J.; Wolfe, P.M., Multiproject scheduling with limited resources: A zero-one programming approach, Management science, 16, 1, 93-108, (1969)
[14] Slowinski, R., Two approaches to the problem of resource allocation among project activities—A comparative study, Journal of the operational research society, 31, 8, 711-723, (1980) · Zbl 0439.90042
[15] Slowinski, R., Multiobjective network scheduling with efficient use of renewable and non-renewable resources, European journal of operational research, 7, 3, 265-273, (1981) · Zbl 0455.90049
[16] Stinson, J.B.; Davis, E.W.; Khumawala, B.M., Multiple resource-constrained scheduling using branch and bound, AIIE transactions, 10, 3, 252-259, (1978)
[17] Talbot, F.B., An integer programming algorithm for the resource-constrained project scheduling problem, (November 1976), The Pennsylvania State University, Unpublished Ph.D. Dissertation
[18] Talbot, F.B., Project scheduling with resource-duration interactions: the nonpreemptive case, Management science, 28, 10, 1197-1210, (1982) · Zbl 0493.90042
[19] Talbot, F.B.; Patterson, J.H., An efficient integer programming algorithm with network cuts for solving resource-constrained scheduling problems, Management science, 24, 11, 1163-1174, (1978) · Zbl 0395.90036
[20] Weglarz, J., On certain models of resource allocation problems, Kybernetes, 9, 1, 61-66, (1980) · Zbl 0421.90049
[21] Weglarz, J., New models and procedures for resource allocation problems, (), 521-530
[22] Weglarz, J.; Blazewicz, J.; Cellary, W.; Slowinsky, R., An automatic revised simplex method for constrained resource network scheduling, ACM transactions on mathematical software, 3, 3, 295-300, (1977) · Zbl 0374.90033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.