×
Ballestín, Francisco; Blanco, Rosa

Theoretical and practical fundamentals for multi-objective optimisation in resource-constrained project scheduling problems. (English) Zbl 1231.90173

Comput. Oper. Res. 38, No. 1, 51-62 (2011).
Summary: Project scheduling is an inherently multi-objective problem, since managers want to finish projects as soon as possible with the minimum cost and the maximum quality. However, there are only a few papers dealing with multiobjective resource-constrained project scheduling problems (MORCPSPs). Moreover, there is no theoretical study in the literature that establishes the fundamentals for correct algorithmic developments. In this paper we try to close the gap by proving several results for MORCPSPs. With these results as a basis, both exact and heuristic procedures capable of obtaining a set of efficient solutions for several important MORCPSPs can be created.
We develop algorithms for the case where all objective functions are of the same type, called regular. In this case, specific codifications, techniques, and procedures can be used. Extensive computational results help decide which algorithms or techniques are the most promising for the problem. With the aid of these algorithms we study the Pareto fronts in this case. Finally, we apply a metaheuristic algorithm to a particular example of the general case in order to analyse the differences in the Pareto fronts.
The project instances and Pareto fronts obtained can be downloaded from a website to facilitate comparisons with future research efforts.

Cited in 10 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90C29 Multi-objective and goal programming

Keywords:

resource-constrained project scheduling; multi-objective; heuristic algorithms
PDF BibTeX XML Cite
\textit{F. Ballestín} and \textit{R. Blanco}, Comput. Oper. Res. 38, No. 1, 51--62 (2011; Zbl 1231.90173)
Full Text: DOI

References:

[1] Brucker, P.; Drexl, A.; Möhring, R.; Neumann, K.; Pesch, E., Resource-constrained project scheduling: notation, classification, models and methods, European Journal of Operational Research, 112, 3-41 (1999) · Zbl 0937.90030
[2] Herroelen, W.; De Reyck, B.; Demeulemeester, E., Resource-constrained project scheduling: a survey of recent developments, Computers and Operations Research, 25, 279-302 (1998) · Zbl 1040.90525
[3] Kolisch, R.; Padman, R., An integrated survey of deterministic project scheduling, Omega, 49, 249-272 (2001)
[4] Özdamar, L.; Ulusoy, G., A survey on the resource-constrained project scheduling problem, IIE Transactions, 27, 574-586 (1995)
[5] Demeulemeester, E.; Herroelen, W., Project scheduling—a research handbook (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 1059.90068
[6] Neumann, K.; Schwindt, C.; Zimmermann, J., Project scheduling with time windows and scarce resources (2002), Springer
[7] Ehrgott, M.; Gandibleux, X., Approximative solution methods for multiobjective combinatorial optimization, TOP, 12, 1, 1-88 (2004) · Zbl 1148.90300
[8] Hansen, P., Bicriterion path problems, (Fandel, G.; Gal, T., Multiple criteria decision making theory and application. Lecture notes in economics and mathematical systems, vol. 177 (1979), Springer: Springer Berlin, Heidelberg, NewYork), 109-127
[9] Ehrgott, M., Approximation algorithms for combinatorial multicriteria optimization problems, International Transactions in Operational Research, 7, 5-31 (2000)
[10] Emelichev, V. A.; Perepelitsa, V. A., Complexity of vector optimization problems on graphs, Optimization, 22, 903-918 (1991) · Zbl 0736.90065
[11] Serafini, P., Some considerations about computational complexity for multi objective combinatorial problems, (Jahn, J.; Krabs, W., Recent advances and historical development of vector optimization. Lecture notes in economics and mathematical systems, vol. 294 (1986), Springer: Springer Berlin, Heidelberg, New York), 222-232
[12] Garey, M. R.; Johnson, D. S., Computers and intractability—a guide to the theory of NP-completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[13] Valiant, L. G.; Vazirani, V. V., NP is as easy as detecting unique solutions, Theoretical Computer Science, 47, 85-93 (1986) · Zbl 0621.68030
[14] Slowinski, R., Multiobjective network scheduling under multiple-category resource constraints, (Slowinski, R.; Weglarz, J., Advances in project scheduling (1989), Elsevier: Elsevier Amsterdam), 151-167
[15] Al-Fawzan, M. A.; Haouari, M., A bi-objective model for robust resource-constrained project scheduling, International Journal of Production Economics, 96, 175-187 (2005)
[19] Slowinski, R., Multiobjective network scheduling with efficient use of renewable and nonrenewable resources, European Journal of Operational Research, 7, 265-273 (1981) · Zbl 0455.90049
[21] SŁowiński, R.; Soniewiclu, B.; Węglarz, J., DSS for multiobjective project scheduling, European Journal of Operational Research, 79, 2, 220-229 (1994) · Zbl 0815.90099
[23] Hapke, M.; Slowinski, R., Fuzzy set approach to multi-objective and multi-mode project scheduling under uncertainty, (Slowinski, R.; Hapke, M., Scheduling under fuzziness (2000), Physica-Verlag: Physica-Verlag Heidelberg), 197-221, Chapter 9 · Zbl 0965.90024
[25] Hapke, M.; Jaszkiewicz, A.; Slowinski, R., Interactive analysis of multiple-criteria project scheduling problems, European Journal of Operational Research, 107, 315-324 (1998) · Zbl 0943.90030
[27] Nabrzyski, J.; Węglarz, J., Knowledge-based multiobjective project scheduling problems, (Węglarz, J., Project scheduling: recent models, algorithms and applications (1999), Kluwer: Kluwer Boston), 383-413, [chapter 17]
[28] Viana, A.; de Sousa, J. P., Using metaheuristics in multiobjective resource constraints project scheduling, European Journal of Operational Research, 120, 359-374 (2000) · Zbl 0955.90037
[29] Schwindt, C.; Zimmermann, J., Parametrische Optimierung als Instrument zur Bewertung von Investitionsprojekten, Zeitschrift für Betriebswirtschaft, 72, 593-617 (2002)
[30] Abbasi, B.; Shadrokh, S.; Arkat, J., Bi-objective resource-constrained project scheduling with robustness and makespan criteria, Applied Mathematics and Computation, 180, 146-152 (2006) · Zbl 1103.90039
[31] Kolisch, R.; Hartmann, S., Experimental investigation of heuristics for resource-constrained project scheduling: an update, European Journal of Operational Research, 174, 23-37 (2006) · Zbl 1116.90047
[34] Deb, K.; Agrawal, S.; Pratap, A.; Meyarivan, T., A fast elitist nondominated sorting genetic algorithm for multi-objective optimization: NSGA-II, (Schoenauer, M.; etal., Parallel problem solving from nature (PPSN VI) (2000), Springer: Springer Berlin, Germany), 849-858
[35] Suresh, R. K.; Mohanasundaram, K. M., Pareto archived simulated annealing for job shop scheduling with multiple objectives, International Journal on Advanced Manufacturing Technology, 29, 184-196 (2006)
[36] Czyzak, P.; Jaszkiewicz, A., Metaheuristic technique for solving multiobjective investment planning problem, Control and Cybernetics, 25, 1, 177-187 (1996) · Zbl 0847.90085
[37] Hartmann, S., A competitive genetic algorithm for resource-constrained project scheduling, Naval Research Logistics, 45, 733-750 (1998) · Zbl 0936.90024
[38] Valls, V.; Ballestín, F.; Quintanilla, S., Justification and RCPSP: a technique that pays, European Journal of Operational Research, 165, 375-386 (2005) · Zbl 1066.90045
[39] Drexl, A., Scheduling of project networks by job assignment, Management Science, 37, 1590-1602 (1991) · Zbl 0729.91011
[40] Hartmann, S., A self-adapting genetic algorithm for project scheduling under resource constraints, Naval Research Logistics, 49, 433-448 (2002) · Zbl 1013.90062
[42] Yamashita, D. S.; Armentano, V. A.; Laguna, M., Scatter search for project scheduling with resource availability cost, European Journal of Operational Research, 169, 623-637 (2006) · Zbl 1079.90066
[43] Shadrokh, S.; Kianfar, F., A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty, European Journal of Operational Research, 181, 86-101 (2007) · Zbl 1121.90062
[44] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C.; Grunert da Fonseca, V., Performance assessment of multiobjective optimizers: an analysis and review, IEEE Transactions on Evolutionary Computation, 7, 2, 117-132 (2003)
[45] Sayin, S., Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming, Mathematical Programming, 87, 3, 543-560 (2000) · Zbl 0970.90090
[48] Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource-constrained project scheduling problems, Management Science, 41, 1693-1703 (1995) · Zbl 0870.90070
[49] Ballestín, F.; Valls, V.; Quintanilla, S., Due dates and RCPSP, (Józefowska, J.; Weglarz, J., Perspectives in modern project scheduling (2006), Springer), [Chapter 4] · Zbl 1107.90014
[50] Hartmann, S.; Kolisch, R., Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem, European Journal of Operational Research, 127, 394-407 (2000) · Zbl 0985.90036
[51] Fisher, R. A., Statistical methods for research workers (1925), Oliver and Boyd: Oliver and Boyd Edinburgh · JFM 51.0414.08
[52] Dixon, W. J.; Mood, A. M., The statistical sign test, Journal of the American Statistical Association, 41, 557-566 (1946)
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.