A preemptive bound for the Resource Constrained Project Scheduling Problem
| Autor: | Mohamed Haouari, Anis Kooli, Emmanuel Neron, Jacques Carlier |
|---|---|
| Přispěvatelé: | Ecole Polytechnique de Tunisie, Department of Mechanical and Industrial Engineering, College of Engineering, Qatar University-Qatar University, Unité Recherche Opérationnelle pour l'Industrie (ROI), Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Heuristique et Diagnostic des Systèmes Complexes [Compiègne] (Heudiasyc), Université de Technologie de Compiègne (UTC)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA) |
| Rok vydání: | 2013 |
| Předmět: |
Mathematical optimization
021103 operations research Supply chain management Linear programming Resource constrained 0211 other engineering and technologies General Engineering Scheduling (production processes) [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] 02 engineering and technology Management Science and Operations Research Upper and lower bounds Project scheduling problem Set (abstract data type) Preemptive relaxation Artificial Intelligence 0202 electrical engineering electronic engineering information engineering Benchmark (computing) Resource constrained project scheduling problem 020201 artificial intelligence & image processing Destructive lower bounds Software Mathematics |
| Zdroj: | Journal of Scheduling Journal of Scheduling, Springer Verlag, 2014, 17, pp.237-248. ⟨10.1007/s10951-013-0354-9⟩ |
| ISSN: | 1099-1425 1094-6136 |
| Popis: | International audience; The Resource Constrained Project Scheduling Problem is one of the most intensively investigated schedul- ing problems. It requires scheduling a set of interrelated activities, while considering precedence relationships, and limited renewable resources allocation. The objective is to minimize the project duration. We propose a new destructive lower bound for this challenging NP -hard problem. Starting from a previously suggested LP model, we propose several original valid inequalities that aim at tightening the model representation. These new inequalities are based on prece- dence constraints, incompatible activity subsets, and nonpre- emption constraints. We present the results of an extensive computational study that was carried out on 2,040 bench- mark instances of PSPLIB , with up to 120 activities, and that provide strong evidence that the new proposed lower bound exhibitsanexcellentperformance.Inparticular,wereportthe improvement of the best known lower bounds of 5 instances |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink