×

A genetic algorithm for the resource constrained multi-project scheduling problem. (English) Zbl 1146.90412

Summary: This paper presents a genetic algorithm for the resource constrained multi-project scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on a set of randomly generated problems. The computational results validate the effectiveness of the proposed algorithm.

MSC:

90B35 Deterministic scheduling theory in operations research

Software:

PSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ash, R., 1999. Activity scheduling in the dynamic, multi-project setting: choosing heuristics through deterministic simulation. In: Proceedings of the 1999 Winter Simulation Conference, Pheoenix, USA, pp. 937-941.; Ash, R., 1999. Activity scheduling in the dynamic, multi-project setting: choosing heuristics through deterministic simulation. In: Proceedings of the 1999 Winter Simulation Conference, Pheoenix, USA, pp. 937-941.
[2] Bean, J. C., Genetics and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 154-160 (1994) · Zbl 0807.90060
[3] Beasley, D.; Bull, D. R.; Martin, R. R., An overview of genetic algorithms: Part 1, fundamentals, University Computing, 15, 2, 58-69 (1993)
[4] 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
[5] Bock, D. B.; Patterson, J. H., A comparison of due date setting resource assignment and job preemption heuristics for the multi-project scheduling problem, Decision Sciences, 21, 387-402 (1990)
[6] Buriol, L. S.; Resende, M. G.C.; Ribeiro, C. C.; Thorup, M., A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing, Networks, 46, 1, 36-56 (2005) · Zbl 1072.90528
[7] Darwin, C. R., On the Origin of Species Through Natural Selection (1859), John Murray: John Murray London
[8] Deckro, R. F.; Winkofsky, E. P.; Hebert, J. E.; Gagnon, R., A decomposition approach to multi-project scheduling, European Journal of Operational Research, 51, 110-118 (1991) · Zbl 0732.90039
[9] DeJong, K., Spears, W., 1991. On the virtues of parameterised uniform crossover. In: R.K. Belew, L.B. Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufman, San Mateo, CA, pp. 230-236.; DeJong, K., Spears, W., 1991. On the virtues of parameterised uniform crossover. In: R.K. Belew, L.B. Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufman, San Mateo, CA, pp. 230-236.
[10] Drexl, A., Scheduling of project networks by job assignment, Management Science, 37, 12, 1590-1602 (1991) · Zbl 0729.91011
[11] Dumond, J.; Mabert, V. A., Evaluating project scheduling and due date assignment procedures: An experimental analysis, Management Science, 34, 1, 101-118 (1988)
[12] Ericsson, M.; Resende, M. G.C.; Pardalos, P. M., A genetic algorithm for the weight setting problem in OSPF routing, Journal of Combinatorial Optimization, 6, 299-333 (2002) · Zbl 1068.90092
[13] Fendley, L. G., Towards the development of a complete multiproject scheduling system, Journal of Industrial Engineering, 19, 10, 505-515 (1968)
[14] Garey, M. R.; Johnson, D. S., Computers and Intractability a Guide to the Theory of NP-completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039
[15] Goldberg, D. E., Genetic Algorithms in Search Optimization and Machine Learning (1989), Addison-Wesley · Zbl 0721.68056
[16] Gonçalves, J. F.; Almeida, J. R., A hybrid genetic algorithm for assembly line balancing, Journal of Heuristics, 8, 629-642 (2002)
[17] Gonçalves, J. F.; Beirão, N. C., Um algoritmo genético baseado em chaves aleatórias para sequenciamento de operações, Revista Associação Portuguesa Investigação Operacional, 19, 123-137 (1999), In Portuguese
[18] Gonçalves, J. F.; Resende, M. G.C., An evolutionary algorithm for manufacturing cell formation, Computers and Industrial Engineering, 47, 247-273 (2004)
[19] Gonçalves, J. F.; Mendes, J. J.M.; Resende, M. G.C., A hybrid genetic algorithm for the job shop scheduling problem, European Journal of Operational Research, 167, 77-95 (2005) · Zbl 1075.90028
[20] Kolisch, R.; Schwindt, C.; Sprecher, A., Benchmark instances for scheduling problems, (Weglarz, J., Handbook on Recent Advances in Project Scheduling (1998), Kluwer: Kluwer Amsterdam), 197-212
[21] Kurtulus, I. S.; Davis, E. W., Multi-project scheduling: categorization of heuristic rules performance, Management Science, 28, 161-172 (1982) · Zbl 0484.90063
[22] Kurtulus, I. S.; Narula, S. C., Multi-project scheduling: analysis of project performance, IIE Transactions, 17, 58-66 (1985)
[23] Lawrence, S. R.; Morton, T. E., Resource-constrained multi-project scheduling with tardy costs: comparing myopic bottleneck and resource pricing heuristics, European Journal of Operational Research, 64, 168-187 (1993) · Zbl 0769.90050
[24] Lova, A., Tormos, P., 2002. Combining random sampling and backward-forward heuristics for resource-constrained multi-project scheduling. In: Proceedings of the Eight International Workshop on Project Management and Scheduling, Valencia, Spain, April, pp. 244-248.; Lova, A., Tormos, P., 2002. Combining random sampling and backward-forward heuristics for resource-constrained multi-project scheduling. In: Proceedings of the Eight International Workshop on Project Management and Scheduling, Valencia, Spain, April, pp. 244-248.
[25] Lova, A.; Maroto, C.; Tormos, P., A multicriteria heuristic method to improve resource allocation in multiproject scheduling, European Journal of Operational Research, 127, 408-424 (2000) · Zbl 0990.90057
[26] Mendes, J.J.M., 2003. Sistema de apoio à decisão para planeamento de sistemas de produçÃo do tipo projecto. PhD thesis, Departamento de Engenharia Mecânica e Gestão Industrial, Faculdade de Engenharia da Universidade do Porto, Porto, Portugal. In Portuguese.; Mendes, J.J.M., 2003. Sistema de apoio à decisão para planeamento de sistemas de produçÃo do tipo projecto. PhD thesis, Departamento de Engenharia Mecânica e Gestão Industrial, Faculdade de Engenharia da Universidade do Porto, Porto, Portugal. In Portuguese.
[27] Mohanthy, R. P.; Siddiq, M. K., Multiple projects multiple resources-constrained scheduling: some studies, International Journal of Production Research, 27, 2, 261-280 (1989)
[28] Ozdamar, L.; Ulusoy, G.; Bayyigit, M., A heuristic treatment of tardiness and net present value criteria in resource constrained project scheduling, International Journal of Physical Distribution and Logistics Management, 28, 805-824 (1998)
[29] Pritsker, A.; Allan, B.; Watters, L. J.; Wolfe, P. M., Multiproject scheduling with limited resources: a zero-one programming approach, Management Science, 16, 93-108 (1969)
[30] Shankar, V., Nagi, R., 1996. A flexible optimization approach to multi-resource, multi-project planning and scheduling. In: Proceedings of 5th Industrial Engineering Research Conference, Minneapolis, MN, USA.; Shankar, V., Nagi, R., 1996. A flexible optimization approach to multi-resource, multi-project planning and scheduling. In: Proceedings of 5th Industrial Engineering Research Conference, Minneapolis, MN, USA.
[31] Tsubakitani, S.; Deckro, R. F., A heuristic for multi-project scheduling with limited resources in the housing industry, European Journal of Operational Research, 49, 80-91 (1990) · Zbl 06908676
[32] Vercellis, C., Constrained multi-project planning problems: a Lagrangean decomposition approach, European Journal of Operational Research, 78, 267-275 (1994) · Zbl 0813.90067
[33] Wiley, V. D.; Deckro, R. F.; Jackson, J. A., Optimization analysis for design and planning of multi-project programs, European Journal of Operational Research, 107, 492-506 (1998) · Zbl 0943.90053
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.