A genetic algorithm approach to a general category project scheduling problem
Author:
- 1 February 1999
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews)
- Vol. 29 (1) , 44-59
Abstract
A genetic algorithm (GA) approach is proposed for the general resource-constrained project scheduling model, in which activities may be executed in more than one operating mode, and renewable as well as nonrenewable resource constraints exist. Each activity's operation mode has a different duration and requires different amounts of renewable and nonrenewable resources. The objective is the minimization of the project duration or makespan. The problem under consideration is known to be one of the most difficult scheduling problems, and it is hard to find a feasible solution for such a problem, let alone the optimal one. The GA approach described in this paper incorporates problem-specific scheduling knowledge by an indirect chromosome encoding that consists of selected activity operating modes and an ordered set of scheduling rules. The scheduling rules in the chromosome are used in an iterative scheduling algorithm that constructs the schedule resulting from the chromosome. The proposed GA is denoted a hybrid GA (HGA) approach, since it is integrated with traditional scheduling tools and expertise specifically developed for the general resource-constrained project scheduling problem. The results demonstrate that HGA approach produces near-optimal solutions within a reasonable amount of computation time.Keywords
This publication has 22 references indexed in Scilit:
- Evolution based learning in a job shop scheduling environmentComputers & Operations Research, 1995
- Adaptive probabilities of crossover and mutation in genetic algorithmsIEEE Transactions on Systems, Man, and Cybernetics, 1994
- Managing genetic search in job shop schedulingIEEE Expert, 1993
- NONPREEMPTIVE MULTI-MODE RESOURCE-CONSTRAINED PROJECT SCHEDULINGIIE Transactions, 1993
- New Search Spaces for Sequencing Problems with Application to Job Shop SchedulingManagement Science, 1992
- Heuristic Performance and Network/Resource Characteristics in Resource-constrained Project SchedulingJournal of the Operational Research Society, 1989
- AN ALGORITHM FOR A GENERAL CLASS OF PRECEDENCE AND RESOURCE CONSTRAINED SCHEDULING PROBLEMS1989
- Optimization of Control Parameters for Genetic AlgorithmsIEEE Transactions on Systems, Man, and Cybernetics, 1986
- Resource-Constrained Project Scheduling with Time-Resource Tradeoffs: The Nonpreemptive CaseManagement Science, 1982
- Adaptive System Design: A Genetic ApproachIEEE Transactions on Systems, Man, and Cybernetics, 1980