algorithms/SCoffmanGraham.h Source File

00001 /* #start# ***********************************************************
00002 
00003                              Scheduling Simulator
00004                     Lehrstuhl f"ur Effiziente Algorithmen
00005                        Technische Universit"at M"unchen
00006 
00007  File    : $Id: SCoffmanGraham.h,v 1.4 2003/01/08 18:57:10 meierb Exp $
00008 
00009  Purpose : implementation of the algorithm by Coffman and Graham
00010            for P2 | prec, p_j=1 | C_max
00011 
00012  RCS-Log:
00013  $Log: SCoffmanGraham.h,v $
00014  Revision 1.4  2003/01/08 18:57:10  meierb
00015  added randomized release times
00016 
00017  Revision 1.1.1.1  2002/12/02 22:26:19  meierb
00018  my_schedule
00019 
00020  Revision 1.2  2002/11/13 18:18:29  taeubig
00021  Workarounds for using LEDA 4.4 and also the former releases
00022 
00023  Revision 1.1  2002/08/29 12:59:58  taeubig
00024  Added the sources
00025 
00026  Revision 1.5  2000/07/05 21:51:20  mayerh
00027  added method getLeaBibEntry and made some changes
00028 
00029  Revision 1.4  2000/05/24 12:21:02  taeubig
00030  New compiler (gcc-2.95) and new Qt (2.1)
00031  Replaced "list" by "leda_list" etc.
00032 
00033  Revision 1.3  2000/03/30 19:13:48  mayerh
00034  added member-functions getClassification() and getName()
00035 
00036  Revision 1.2  2000/01/12 11:31:34  zoidl
00037  added javadoc comments and cosmetic changes in getDescription
00038 
00039  Revision 1.1  1999/12/29 19:11:08  zoidl
00040  added algorithm of Coffman and Graham
00041 
00042 
00043  * #end# ************************************************************* */
00044 
00045 // from:
00046 //
00047 // Blazewicz et al., Scheduling Computer and Manufactoring Processes, 1996
00048 // Chapt. 5.1.1, p. 153, Algorithm 5.1.12
00049 
00050 // complexity: O(n^2)
00051 
00052 #ifndef SCOFFMANGRAHAM_H
00053 #define SCOFFMANGRAHAM_H
00054 
00055 // system header files
00056 
00057 // project header files
00058 #include "SSchedAlgorithm.h"
00059 
00063 class SCoffmanGraham : public SSchedAlgorithm
00064 {
00065  public:
00066   virtual ~SCoffmanGraham();
00067   virtual void startup();
00068   virtual double innerLoop(const leda_list<STSysSchedEvent>& rEvents);
00069   virtual const leda_string getDescription() const;
00070   virtual const leda_string &getName() const;
00071   virtual const SClassification &getClassification() const;
00072   virtual SLeaBibEntry &getLeaBibEntry() const;
00073  private:
00074   // task list
00075   leda_list<leda_node> _L;
00076   // current position in the task list _L
00077   leda_list_item _posInL;
00078   
00079   // helper for startup()
00080   void insertN(leda_list<int*> &N, int* newlist, leda_node_array<int> &pos, int max, 
00081          leda_list<leda_node> &tasks, leda_node w, leda_list<int> &hl);
00082   bool test_node(const leda_graph &g, leda_node w, leda_node_array<int> &num);
00083 };
00084 
00085 #endif