An implementation of the parallel schedule-generation scheme for applying Microsoft Excel's Evolutionary Solver to the resource-constrained project scheduling problem RCPSP

摘要

Since the 2010 version, the Solver Add-in of Microsoft Excel comprises the so-called Evolutionary Solver. The application of this Solver to a combinatorial optimization problem requires a spreadsheet which determines the objective function value corresponding to given values for the decision variables. This paper refers to the resource-constrained project-scheduling problem; we study how to implement the parallel schedule-generation scheme on a spreadsheet. We compare the performance against the serial schedule-generation scheme based on the j30 PSPLIB test set. It turns out that the CPU time required for scheduling an activity is considerably lower in the parallel than in the serial schedule-generation scheme; as a consequence, more schedules can be analyzed within a prescribed amount of time. For the novel implementation of the parallel scheme, the average deviation from the minimum makespan is considerably smaller than for the serial scheme, and the number of instances solved to optimality is surprisingly high.