A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty. (English) Zbl 1121.90062
Summary: A genetic algorithm for solving a class of project scheduling problems, called Resource investment problem, is presented. Tardiness of project is permitted with defined penalty. Elements of algorithm such as chromosome structure, unfitness function, crossover, mutation, immigration and local search operations are explained. The performance of this genetic algorithm is compared with the performance of other published algorithms for resource investment problem. Also 690 problems are solved and their optimal solutions are used for the performance tests of the genetic algorithm. The tests results are quite satisfactory.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
PSPLIBReferences:
| [1] | Baker, K., Introduction to Sequencing and Scheduling (1974), John Wiely and Sons, Inc |
| [2] | Bedworth, D. D.; Bailey, J. E., Integrated Production Control Systems - Management, Analysis, Design (1982), Wiley: Wiley New York |
| [3] | Brucker, P.; Drexl, A.; Möhring, R. H.; 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 |
| [4] | Demeulemeester, E. L., Minimizing resource availability costs in time limited project networks, Management Science, 41, 1590-1598 (1995) · Zbl 0861.90071 |
| [5] | Demeulemeester, E. L.; Herroelen, W., A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Management Science, 38, 1803-1818 (1992) · Zbl 0761.90059 |
| [6] | Drexl, A.; Kimms, A., Optimization guided lower & upper bounds for the resource investment problem, Journal of the Operational Re search Society, 52, 340-351 (2001) · Zbl 1131.90378 |
| [7] | Hartmann, S., A competitive genetic algorithm for resource-constrained project scheduling, Naval Research Logistics, 45, 733-750 (1998) · Zbl 0936.90024 |
| [8] | Kelley, J. E., The critical path method: Resources planning and scheduling, (Muth, J. F.; Thompson, G. L., Industrial Scheduling (1963), Prentice-Hall: Prentice-Hall New Jersey), 347-365 |
| [9] | Kimms, A., 2002. Personal communication.; Kimms, A., 2002. Personal communication. |
| [10] | Kolisch, R., Serial and parallel resource constrained project scheduling methods revisited: Theory and computation, European Journal of Operational Research, 90, 320-333 (1996) · Zbl 0916.90151 |
| [11] | Kolisch, R.; Hartmann, S., Heuristic algorithms for solving the resource-constrained project scheduling problem: Classification and computational analysis, (Weglarz, J., Project Scheduling: Recent Models, Algorithms and Applications (1999), Kluwer Academic Publishers), 147-178 |
| [12] | Kolisch, R.; Sprecher, A., PSBLIB - A project scheduling problem library, European Journal of Operational Research, 96, 205-216 (1997) · Zbl 0947.90587 |
| [13] | 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 |
| [14] | Möhring, R. H., Minimizing costs of resource requirements in project networks subject to a fix completion time, Operations Research, 32, 89-120 (1984) · Zbl 0531.90049 |
| [15] | Nuamann, K.; Schwindt, C.; Zimmerman, J., Project Scheduling with Time Windows and Scarce Resources (2003), Springer: Springer Berlin · Zbl 1059.90001 |
| [16] | Nübel, H., The resource renting problem subject to temporal constraints, OR Spektrum, 23, 574-586 (2001) · Zbl 0985.90041 |
| [17] | Pritsker, A. A.B.; Watters, L. J.; Wolfe, P. M., Multi-project scheduling with limited resources, Management Science, 16, 93-108 (1969) |
| [18] | Schwindt, C., 1996, Generation of resource constrained scheduling problems with minimal and maximal time lags, Report WIOR-489, Universität Karlsruhe.; Schwindt, C., 1996, Generation of resource constrained scheduling problems with minimal and maximal time lags, Report WIOR-489, Universität Karlsruhe. |
| [19] | Sprecher, A.; Kolisch, R.; Drexl, A., Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem, European Journal of Operational Research, 80, 94-102 (1995) · Zbl 0927.90054 |
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.
