×
Damay, Jean; Quilliot, Alain; Sanlaville, Eric

Linear programming based algorithms for preemptive and non-preemptive RCPSP. (English) Zbl 1121.90055

Eur. J. Oper. Res. 182, No. 3, 1012-1022 (2007).
Summary: 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.

Cited in 11 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90C05 Linear programming

Keywords:

scheduling; resource constrained project; preemption; linear programming; column generation

Software:

PSPLIB
PDF BibTeX XML Cite
\textit{J. Damay} et al., Eur. J. Oper. Res. 182, No. 3, 1012--1022 (2007; Zbl 1121.90055)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Baptiste, P.; Demassey, S., Tight LP bounds for resource constrained project scheduling, OR spectrum, 26, 251-262, (2004) · Zbl 1072.90012
[2] Bendali, F.; Quilliot, A., Representation of ordered families of intervals, and applications, RAIRO, recherche opérationnelle/operations research, 31, 1, 73-101, (1997) · Zbl 0881.90117
[3] Brucker, P.; Knust, S., A linear programming and constraint propagation-based lower bound for the RCPSP, European journal of operational research, 127, 355-362, (2000) · Zbl 0990.90055
[4] Demassey, S.; Artigues, C.; Michelon, P., Constraint propagation based cutting planes: an application to the resource-constrained project scheduling problem, INFORMS journal on computing, 17, 1, 52-65, (2005) · Zbl 1239.90062
[5] Demeulemeester, E.; Herroelen, W., An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem, European journal of operational research, 90, 334-348, (1996) · Zbl 0916.90149
[6] Kolisch, R.; Sprecher, A., PSPLIB - a project scheduling library, European journal of operational research, 205-216, (1996) · Zbl 0947.90587
[7] Mingozzi, A.; Maniezzo, V.; Ricciardelli, S.; Bianco, L., An exact algorithm for the resource-constrained project scheduling based on a new mathematical formulation, Management science, 44, 714-729, (1998) · Zbl 1004.90036
[8] Möhring, R.H.; Schulz, A.S.; Stork, F.; Uetz, M., Solving project scheduling problems by minimum cut computations, INFORMS management science, 49, 3, 330-350, (2003) · Zbl 1232.90213
[9] Moukrim, A.; Quilliot, A., A relation between multiprocessor scheduling and linear programming, Order, 14, 269-278, (1998) · Zbl 0912.90178
[10] Moukrim, A.; Quilliot, A., Optimal preemptive scheduling on a fixed number of identical machines, Operations research letters, 33, 143-150, (2005) · Zbl 1099.90022
[11] Le Pape, C.; Baptiste, Ph., Resource constraints for preemptive job-shop scheduling, Constraints, 3, 4, 263-287, (1998) · Zbl 0915.90152
[12] Schoo, A.; Thiele, O.; Brucker, P.; Knust, S., A branch and bound algorithm for the resource-constrained project scheduling problem, European journal of operational research, 107, 272-288, (1998) · Zbl 0970.90030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.