Two continuous-time assignment-based models for the multi-mode resource-constrained project scheduling problem. (March 2019) - Gnägi, Mario; Rihm, Tom; Zimmermann, Adrian; Trautmann, Norbert
Highlights: We present two novel mixed-integer linear programming models for the MRCPSP. We test our models against existing models on standard and novel test instances. Our models show a superior performance for instances with a long planning horizon. Further advantages are the simple structure and enhanced flexibility of our models. Abstract: In the multi-mode resource-constrained project scheduling problem, a set of precedence-related project activities and, for each activity, a set of alternative execution modes are given. Each activity requires some time and some scarce resources during execution; these requirements depend on the selected execution mode. Sought is a project schedule, i.e, a start time and an execution mode for each activity, such that the project makespan is minimized. In the literature, besides a large variety of specific solution approaches, several Mixed-Integer Linear Programming (MILP) models have been proposed for this problem. We present two novel MILP models that are based on mode-selection, resource-assignment and sequencing variables; we enhance the performance of the models by eliminating some symmetric solutions from the search space and by adding some redundant sequencing constraints for pairs and for triples of activities that cannot be processed in parallel. In a comparison with reference models from the literature, it turned out that the advantages of the novel models are a simple structure, an enhanced flexibility, and a superior performance when the range of the activities' durations is relatively large.