An exchange heuristic for resource constrained scheduling with consideration given to opportunities for parallel processing

Abstract

This paper describes a heuristic which produces efficient makespans for resource-constrained scheduling problems with parallel processing capabilities. This heuristic was initially developed for the scheduling of army battalion training exercises. The original heuristic has also been successfully applied to solve problems in project scheduling with limited resources, generalized job shop scheduling, and resource-constrained scheduling. The exchange heuristic requires an initial feasible solution upon which it improves the makespan by efficiently and systematically shuffling activities while maintaining feasibility. The method has recently been modified twice, termed the intelligent version and naive version, respectively, such that its ability to reduce the initial makespan is enhanced. In this study

Keywords:

• scheduling
• resource constrained scheduling
• parallel processing
• heuristic algorithm
• nonlinear search technique