A critical chains based distributed multi-project scheduling approach

摘要

In this paper, we discuss the distributed resource constrained multi-project scheduling problem (DRCMPSP) and focus on handling resource conflicts. The resource conflicts among projects are originally caused by precedence constraints and resource constraints. To reflect the influences of both constraints, this paper incorporates the critical chain concept into the distributed problem and introduces a corresponding heuristic strategy. Besides, to deal with large scale instances, an elimination mechanism is proposed, which identifies a few conflict time slots in advance and allocates global resources in those time slots only. Depending upon the heuristics and elimination mechanism, we develop a distributed multi-agent system based algorithm called DMAS/EM. Experiments show that DMAS/EM algorithm can generate satisfactory solutions with low average project delay and significant time savings. Furthermore, we observe that our algorithm provides great scalability with respect to variations in the size of instances processed and the degree of conflicts.