Resource-constrained multi-project scheduling with tardy costs: Comparing myopic, bottleneck, and resource pricing heuristics. (English) Zbl 0769.90050

Lawrence, Stephen R.; Morton, Thomas E.

Eur. J. Oper. Res. 64, No. 2, 168-187 (1993).

Summary: This paper addresses the problem of scheduling multiple resource- constrained projects with the objective of minimizing weighted tardiness costs. Extending our earlier heuristic scheduling work for production shops, we develop an efficient and effective means of generating low cost schedules for multiple projects requiring multiple resources. A ‘cost- benefit’ scheduling policy with resource pricing is developed which balances the marginal cost of delaying the start of an eligible activity with the marginal benefit of such a delay. A central part of this policy is the heuristic estimation of implicit resource prices, which form the basis for calculating marginal delay costs. The resulting policies are tested against a number of dispatch scheduling rules taken from the project scheduling literature, and against several new scheduling rules, with encouraging results for both the weighted tardiness problem and for the special case of weighted project delay.

MSC:

90B35

Deterministic scheduling theory in operations research

Keywords:

multiple resource-constrained projects; weighted tardiness costs; heuristic

References:

[1]	Alvarèz-Valdes, R.; Tamarit, J. M., Heuristic algorithms for resource-constrained project scheduling: A review and empirical analysis, (Słowiński, R.; Weglarz, J., Advances in Project Scheduling (1989), Elsevier Science Publishers: Elsevier Science Publishers Amsterdam), 113-134, Chapter 5
[2]	Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York
[3]	Boctor, F. F., Some efficient multi-heuristic procedures for resource-constrained project scheduling, European Journal of Operational Research, 49/1, 3-13 (1990) · Zbl 1403.90305
[4]	Cooper, D. F., Heuristics for scheduling resource-constrained projects: An experimental investigation, Management Science, 22/11, 1186-1194 (1976) · Zbl 0326.90029
[5]	Daniels, R. L., Resource allocation and multi-project scheduling, (Słowiński, R.; Weglarz, J., Advances in Project Scheduling (1989), Elsevier Science Publishers: Elsevier Science Publishers Amsterdam), 87-112, Chapter 4
[6]	Davies, E. M., An experimental investigation of resource allocation in multiactivity projects, Operational Research Quarterly, 24/4, 587-591 (1972)
[7]	Davis, E. W., Project network summary measures: Constrained-resource scheduling, AIIE Transactions, 7/2, 132-142 (1975)
[8]	Davis, E. W., Project scheduling under resource constraints-historical review and categorization of procedures, AIIE Transactions, 5/4, 297-313 (1973)
[9]	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)
[10]	Dumond, J.; Mabert, V. A., Evaluating project schedulling and due date assignment procedures: An experimental analysis, Management Science, 34/1, 101-118 (1988)
[11]	Fendley, L. G., Toward the development of a complete multiproject scheduling system, The Journal of Industrial Engineering, 19/10, 505-515 (October 1968)
[12]	Kelly, J.; Walker, M., Scheduling activities to satisfy resource constraints, (Muth, J.; Thompson, G., Industrial Scheduling (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ)
[13]	Kim, S. O.; Schniederjans, M. J., Heuristic framework for the resource constrained multi-project scheduling problem, Computers and Operations Research, 16/6, 541-556 (1989)
[14]	Kurtulus, I. S., Multiproject scheduling: Analysis of scheduling strategies under unequal delay penalties, Journal of Operations Management, 5/3, 291-307 (1985)
[15]	Kurtulus, I. S.; Davis, E. W., Multi-project scheduling: Categorization of heuristic rules performance, Management Science, 28/2, 161-172 (1982) · Zbl 0484.90063
[16]	Kurtulus, I. S.; Narula, S. C., Multi-project scheduling: Analysis of project performance, IE Transactions, 17/2, 58-66 (1985)
[17]	Lawrence, S. R., Scheduling a single machine to maximize net present value, International Journal of Production Research, 29/6, 1141-1160 (1991)
[18]	Park, O. E.; Lee, S. M.; Economides, S. C., Resource planning for multiple projects, Decision Sciences, 9/1, 49-67 (1978)
[19]	Meleton, M. P., OPT - fantasy or breakthrough, Production and Inventory Management, 2, 13-21 (1986)
[20]	Mohring, R. H., Minimizing costs of resource requirements in project networks subject to a fixed completion time, Operations Research, 31/1, 89-120 (1984) · Zbl 0531.90049
[21]	Morton, T. E.; Lawrence, S.; Rajagopalan, S.; Kekre, S., SCHED-STAR: a price-based shop scheduling module, Journal of Manufacturing and Operations Management, 1/2, 131-181 (1988)
[22]	Morton, T. E.; Singh, M. R., Implicit costs and prices for resources with busy periods, Journal of Manufacturing and Operations Management, 1/3, 305-322 (1988)
[23]	Ow, P. S.; Morton, T. E., The single machine early/tardy problem, Management Science, 35/2, 177-191 (1989) · Zbl 0666.90043
[24]	Pascoe, T. L., An experimental comparison of heuristic methods for allocating resources, (PhD Thesis (1965), Cambridge University: Cambridge University England)
[25]	Patterson, J. H., Project scheduling: The effects of problem structure on heuristic performance, Naval Research Logistics Quarterly, 23/1, 95-123 (1976) · Zbl 0325.90027
[26]	Watters, L. J.; Pritsker, A.; Wolffe, P. M., Multiproject scheduling with limited resources: A zero-one programming approach, Management Science, 16/1, 93-108 (1969)
[27]	Rachamadugu, R. V.; Morton, T. E., Myopic heuristic for the single machine weighted tardiness problem, (Working Paper No. 28-81-82 (1982), Graduate School of Industrial Administration, Carnegie-Mellon University: Graduate School of Industrial Administration, Carnegie-Mellon University Pittsburgh, PA)
[28]	(Słowiński, R.; Weglarz, J., Advances in Project Scheduling, Volume 9 of Studies in Production and Eingineering Economics (1989), Elsevier: Elsevier Amsterdam)
[29]	Tsubakitani, S.; Deckro, R. F., A heuristic for multi-project scheduling with limited resources in the housing industry, European Journal of Operational Research, 49/1, 80-91 (1990) · Zbl 06908676
[30]	Ullman, J. D., NP-complete scheduling problems, Journal of Computers and Systems Science, 10, 384-393 (1975) · Zbl 0313.68054
[31]	Vepsalainen, A. P.; Morton, T. E., Priority rules for job shops with weighted tardiness costs, Management Science, 33/8, 95-103 (1987)