×
Yamashita, Denise Sato; Armentano, Vinícius Amaral; Laguna, Manuel

Scatter search for project scheduling with resource availability cost. (English) Zbl 1079.90066

Eur. J. Oper. Res. 169, No. 2, 623-637 (2006).
Summary: This paper considers a project scheduling problem with the objective of minimizing resource availability costs, taking into account a deadline for the project and precedence relations among the activities. Exact methods have been proposed for solving this problem, but we are not aware of existing heuristic methods. Scatter search is used to tackle this problem, and our implementation incorporates advanced strategies such as dynamic updating of the reference set, the use of frequency-based memory within the diversification generator, and a combination method based on path relinking. We also analyze the merit of employing a subset of different types when combining solutions. Extensive computational experiments involving more than 2400 instances are performed. For small instances, the performance of the proposed procedure is compared to optimal solutions generated by an exact cutting plane algorithm and upper and lower bounds from the literature. For medium and larger size instances, we developed simple multi-start heuristics and comparative results are reported.

Cited in 18 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Keywords:

Project scheduling; Resource availability cost; Heuristics; Scatter search

Software:

Scatter Search
PDF BibTeX XML Cite
\textit{D. S. Yamashita} et al., Eur. J. Oper. Res. 169, No. 2, 623--637 (2006; Zbl 1079.90066)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Blazewicz, J.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Scheduling subject to resource constraints: classification and complexity, Discrete applied mathematics, 5, 11-24, (1983) · Zbl 0516.68037
[2] Brucker, P.; Drexl, A.; Mohring, 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
[3] Campos, V.; Glover, F.; Laguna, M.; Martí, M., An experimental evaluation of a scatter search for the linear ordering problem, Journal of global optimization, 21, 397-414, (2001) · Zbl 1175.90424
[4] Campos, V., Laguna, M., Martí, M., Context-independent scatter and tabu search for permutation problems, INFORMS. Journal on Computing, in press. · Zbl 1239.90109
[5] Cavique, L.; Rego, C.; Themido, I., A scatter search algorithm for the maximum clique problem, (), 227-244 · Zbl 1006.90069
[6] Demeulemeester, E., Minimizing resource availability costs in time-limited project networks, Management science, 41, 1590-1598, (1995) · Zbl 0861.90071
[7] Demeulemeester, E.; Herroelen, S., A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Management science, 38, 1803-1818, (1992) · Zbl 0761.90059
[8] Drexl, A.; Kimms, A., Optimization guided lower and upper bounds for the resource investment problem, Journal of the operational research society, 52, 340-351, (2001) · Zbl 1131.90378
[9] Glover, F., A template for scatter search and path relinking, (), 13-54
[10] Glover, F., Heuristics for integer programming using surrogate constraints, Decision sciences, 8, 156-166, (1977)
[11] Glover, F., Genetic algorithms and scatter search: unsuspected potentials, Statistics and computing, 4, 131-140, (1994)
[12] Glover, F.; Laguna, M.; Martí, R., Fundamentals of scatter search and path relinking, Control and cybernetics, 39, 653-683, (2000) · Zbl 0983.90077
[13] Greistorfer, P., A tabu scatter search metaheuristic for the arc routing problem, Computers & industrial engineering, 44, 249-266, (2003)
[14] Hamiez, J.-P.; Hao, J.-K., Scatter search for graph coloring, (), 168-179 · Zbl 1054.68649
[15] 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
[16] Herroelen, W.; De Reyck, B.; Demeulemeester, E., Resource-constrained project scheduling: A survey of recent developments, Computers & operations research, 25, 279-302, (1998) · Zbl 1040.90525
[17] Jain, A.S.; Meeran, S., A multi-level hybrid framework applied to the general flow-shop scheduling problem, Computers & operations research, 29, 1873-1901, (2002)
[18] 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
[19] Kolisch, R.; Hartmann, S., Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis, (), 147-178
[20] Laguna, M.; Martí, R., Scatter search: methodology and implementations in C, (2003), Kluwer Academic Publishers Boston · Zbl 1055.68103
[21] Larrañaga, P.; Kuijpers, C.M.H.; Murga, R.H.; Inza, I.; Dizdarevic, S., Genetic algorithms for the travelling salesman problem: A review of representations and operators, Artificial intelligence, 13, 129-170, (1999)
[22] Martí, R.; Lourenço, H.; Laguna, M., Assigning proctors to exams with scatter search, (), 215-227
[23] Martí, R., Laguna, M., Campos, V., Scatter search vs. genetic algorithms: An experimental evaluation with permutation problems, in Rego, C., Alidaee, B., (Eds.), Adaptive memory and evolution: Tabu search and scatter search, Kluwer Academic Publishers, in press.
[24] Martí, R.; Laguna, M.; Glover, F., Principles of scatter search, European journal of operational research, 169, 359-372, (2006) · Zbl 1079.90178
[25] Möhring, R.F., Minimizing costs of resource requirements in project networks subject to a fixed completion time, Operations research, 32, 89-120, (1984) · Zbl 0531.90049
[26] Rangaswamy, B., 1998. Multiple resource planning and allocation in resource-constrained project networks. Ph.D. thesis, Graduate School of Business, University of Colorado.
[27] Reeves, C.R.; Yamada, T., Genetic algorithms, path relinking and the flowshop sequencing problem, Evolutionary computation journal, 6, 45-60, (1998)
[28] Rego, C., Leão, P., 2001. A scatter search tutorial for graph-based permutation problems. Technical Paper, Business School Administration, University of Mississippi.
[29] Tormos, P.; Lova, A., An efficient multi-pass heuristic for project scheduling with constrained resources, International journal of production research, 41, 1071-1086, (2003) · Zbl 1038.90038
[30] Valls, V.; Laguna, M.; Lino, P.; Pérez, A.; Quintanilla, S., Project scheduling with stochastic activity interruptions, (), 333-353
[31] Yamada, T.; Reeves, C.R., Permutation flowshop scheduling by genetic local search, (), 232-238
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.