A column-generation-based algorithm for a resource-constrained project scheduling problem with a fractional shared resource

What is it about?

This article considers a resource-constrained project scheduling problem with a single shared resource. In this model, multiple processors are required to complete jobs with a certain amount of shared resource. The supply of the resource is limited and must be shared between processors. A column-generation-based algorithm with some enhancement techniques, including stabilization, a mechanism to update the solution pool, and an approximate solution technique, is proposed. Finally, extensive computational experiments are conducted to evaluate the performance of the proposed method by comparing it with Lagrangian relaxation, CPLEX®® and a self-adapting genetic algorithm. The results prove the proposed method has an advantage in terms of the objective and CPU time. Numerical experiments are also conducted to verify the effectiveness of the proposed enhancements.

Featured Image