algorithms/SLineClustersAlg.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: SLineClustersAlg.h,v 1.4 2003/01/08 18:57:11 meierb Exp $
00008 
00009  Purpose : Dynamic scheduling on a line topology without dependencies
00010            All resource requirements of the jobs are known
00011      (but processing times are not known in advance).
00012      Competitive ratio: 2.5
00013      [A.Feldmann / J.Sgall / S.-H.Teng:
00014       "Dynamic scheduling on parallel machines", p.13-16]
00015 
00016  RCS-Log:
00017  $Log: SLineClustersAlg.h,v $
00018  Revision 1.4  2003/01/08 18:57:11  meierb
00019  added randomized release times
00020 
00021  Revision 1.1.1.1  2002/12/02 22:26:19  meierb
00022  my_schedule
00023 
00024  Revision 1.2  2002/11/13 18:18:29  taeubig
00025  Workarounds for using LEDA 4.4 and also the former releases
00026 
00027  Revision 1.1  2002/08/29 12:59:58  taeubig
00028  Added the sources
00029 
00030  Revision 1.3  2000/07/05 21:51:33  mayerh
00031  added method getLeaBibEntry and made some changes
00032 
00033  Revision 1.2  2000/06/26 11:03:56  taeubig
00034  Updated startup() method
00035 
00036  Revision 1.1  2000/06/25 01:14:10  taeubig
00037  Added algorithm CLUSTERS for dynamic multiprocessor task scheduling
00038  on line topologies
00039 
00040 
00041  * #end# ************************************************************* */
00042 
00043 #ifndef SLINECLUSTERSALG_H
00044 #define SLINECLUSTERSALG_H
00045 
00046 // system header files
00047 #include <LEDA/d2_dictionary.h>
00048 
00049 #ifndef leda_dic2_item
00050 #if __LEDA__ < 440
00051 #define leda_dic2_item dic2_item
00052 #else
00053 #define leda_dic2_item leda::dic2_item
00054 #endif
00055 #endif
00056 
00057 // project header files
00058 #include "SSchedAlgorithm.h"
00059 
00060 class SCluster {
00061  public:
00062   SCluster(): _left(NULL), _middle(NULL), _right(NULL) {};
00063 
00064   SJob *_left, *_middle, *_right;
00065   int _occupied;
00066 };
00067 
00068 class SLineClustersAlg : public SSchedAlgorithm {
00069  public:
00070   SLineClustersAlg() {};
00071   virtual ~SLineClustersAlg() {};
00072   virtual void startup();
00073   virtual double innerLoop(const leda_list<STSysSchedEvent>& rEvents);
00074   virtual const leda_string getDescription() const;
00075   virtual const leda_string &getName() const;
00076   virtual const SClassification &getClassification() const;
00077   virtual SLeaBibEntry &getLeaBibEntry() const;
00078 
00079   void incLoad(SJob *pJob);
00080 
00081  private:
00082   leda_list<SJob*> _largeJobs, _smallJobs;
00083   int _phase;
00084   leda_d2_dictionary<int, int, SCluster*> _clusters;
00085 };
00086 
00087 #endif //SLINECLUSTERSALG_H