A new any-order schedule generation scheme for resource-constrained project scheduling

Cyril Briand

RAIRO - Operations Research (2009)

  • Volume: 43, Issue: 3, page 297-308
  • ISSN: 0399-0559

Abstract

top
In this paper, a new schedule generation scheme for resource-constrained project scheduling problems is proposed. Given a project scheduling problem and a priority rule, a schedule generation scheme determines a single feasible solution by inserting one by one each activity, according to their priority, inside a partial schedule. The paper proposes a generation scheme that differs from the classic ones in the fact that it allows to consider the activities in any order, whether their predecessors have already been scheduled or not. Moreover, activity insertion is performed so that delaying some already scheduled activities is allowed. The paper shows that this strategy remains polynomial and often gives better results than more classic ones. Moreover, it is also interesting in the fact that some priority rules, which are quite poor when used with classic schedule generation schemes, become very competitive with the proposed schedule generation scheme.

How to cite

top

Briand, Cyril. "A new any-order schedule generation scheme for resource-constrained project scheduling." RAIRO - Operations Research 43.3 (2009): 297-308. <http://eudml.org/doc/250625>.

@article{Briand2009,
abstract = { In this paper, a new schedule generation scheme for resource-constrained project scheduling problems is proposed. Given a project scheduling problem and a priority rule, a schedule generation scheme determines a single feasible solution by inserting one by one each activity, according to their priority, inside a partial schedule. The paper proposes a generation scheme that differs from the classic ones in the fact that it allows to consider the activities in any order, whether their predecessors have already been scheduled or not. Moreover, activity insertion is performed so that delaying some already scheduled activities is allowed. The paper shows that this strategy remains polynomial and often gives better results than more classic ones. Moreover, it is also interesting in the fact that some priority rules, which are quite poor when used with classic schedule generation schemes, become very competitive with the proposed schedule generation scheme. },
author = {Briand, Cyril},
journal = {RAIRO - Operations Research},
keywords = {Project scheduling; schedule generation scheme; activity insertion. ; project scheduling; activity insertion},
language = {eng},
month = {7},
number = {3},
pages = {297-308},
publisher = {EDP Sciences},
title = {A new any-order schedule generation scheme for resource-constrained project scheduling},
url = {http://eudml.org/doc/250625},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Briand, Cyril
TI - A new any-order schedule generation scheme for resource-constrained project scheduling
JO - RAIRO - Operations Research
DA - 2009/7//
PB - EDP Sciences
VL - 43
IS - 3
SP - 297
EP - 308
AB - In this paper, a new schedule generation scheme for resource-constrained project scheduling problems is proposed. Given a project scheduling problem and a priority rule, a schedule generation scheme determines a single feasible solution by inserting one by one each activity, according to their priority, inside a partial schedule. The paper proposes a generation scheme that differs from the classic ones in the fact that it allows to consider the activities in any order, whether their predecessors have already been scheduled or not. Moreover, activity insertion is performed so that delaying some already scheduled activities is allowed. The paper shows that this strategy remains polynomial and often gives better results than more classic ones. Moreover, it is also interesting in the fact that some priority rules, which are quite poor when used with classic schedule generation schemes, become very competitive with the proposed schedule generation scheme.
LA - eng
KW - Project scheduling; schedule generation scheme; activity insertion. ; project scheduling; activity insertion
UR - http://eudml.org/doc/250625
ER -

References

top
  1. C. Artigues and F. Roubellat, A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple mode. Eur. J. Oper. Res. (2000) 127 297–316.  
  2. C. Artigues, P. Michelon and S. Reusser, Insertion Techniques for static and dynamic resource-constrained project scheduling. Eur. J. Oper. Res.149 (2003) 249–267.  
  3. M. Bartusch, R.H. Möhring and F.J. Radermacher, Scheduling project networks with resource constraints and time windows. Ann. Oper. Res.16 (1988) 201–240.  
  4. P. Brucker, A. Drexl, R.H. Möhring, K. Neumann and E. Pesh, Resource-constrained project scheduling: Notation, classification, models and methods. Eur. J. Oper. Res.112 (1999) 3–41.  
  5. J. Blazewicz, J. Lenstra and A. Rinnooy Kan, Scheduling subject to resource constraints: Classification and complexity. Discrete Appl. Math.5 (1983) 11–24.  
  6. P. Brucker, S. Knust, A. Schoo and O. Thiele, A branch-and-bound algorithm for the resource-constrained project scheduling problem. Eur. J. Oper. Res.107 (1998) 272–288.  
  7. E.L. Demeulemeester and W.S. Herroelen, New Benchmark Results for the Resource-Constrained Project Scheduling Problem. Manage. Sci. (1997) 1485–1492.  
  8. S. Hartmann and R. Kolisch, Experimental evaluation of the state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur. J. Oper. Res.127 (2000) 394–407.  
  9. R. Kolisch and S. Hartmann, Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update. Eur. J. Oper. Res.174 (2006) 23–37.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.