Linear programming based algorithms for preemptive and non-preemptive RCPSP |
| |
Authors: | Jean Damay Alain Quilliot Eric Sanlaville |
| |
Affiliation: | Laboratoire LIMOS-CNRS UMR 6158, Université de Clermont II, Complexe Scientifique des Cézeaux, 63173 Aubière Cedex, France |
| |
Abstract: | In this paper, the RCPSP (resource constrained project scheduling problem) is solved using a linear programming model. Each activity may or may not be preemptive. Each variable is associated to a subset of independent activities (antichains). The properties of the model are first investigated. In particular, conditions are given that allow a solution of the linear program to be a feasible schedule. From these properties, an algorithm based on neighbourhood search is derived. One neighbour solution is obtained through one Simplex pivoting, if this pivoting preserves feasibility. Methods to get out of local minima are provided. The solving methods are tested on the PSPLIB instances in a preemptive setting and prove efficient. They are used when preemption is forbidden with less success, and this difference is discussed. |
| |
Keywords: | Scheduling Resource constrained project Preemption Linear programming Column generation |
本文献已被 ScienceDirect 等数据库收录! |
|