Entropy-Based Heuristic for Resource-Constrained Project Scheduling

Abstract

A heuristic is presented for the resource-constrained project scheduling problem (RCPSP), based on maximizing the entropy of the project's resource histogram. The proposed RCPSP algorithm makes use of the general theory of entropy, two of its principal properties (subadditivity and maximality), and a newly proposed maximum-entropy (MaxEnt) rule, to heuristically prioritize schedule activities subject to imposed resource constraints so as to maximize the histogram's total entropy. Maximal entropy is, by definition, reached at the equiprobability distribution and thus at a leveled allocation of resources. The proposed heuristic is evaluated by use of case-study networks and its performance compared to the performance of the earliest late start (ELS) rule.