algorithms/SMcNaughton.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: SMcNaughton.h,v 1.5 2003/01/08 18:57:11 meierb Exp $
00008 
00009  Purpose : implementation of McNaughton's rule for P|pmtn|C_max
00010 
00011  RCS-Log:
00012  $Log: SMcNaughton.h,v $
00013  Revision 1.5  2003/01/08 18:57:11  meierb
00014  added randomized release times
00015 
00016  Revision 1.1.1.1  2002/12/02 22:26:19  meierb
00017  my_schedule
00018 
00019  Revision 1.3  2002/11/13 18:18:29  taeubig
00020  Workarounds for using LEDA 4.4 and also the former releases
00021 
00022  Revision 1.2  2002/11/10 13:32:52  taeubig
00023  namespace and header include changes
00024 
00025  Revision 1.1  2002/08/29 12:59:58  taeubig
00026  Added the sources
00027 
00028  Revision 1.6  2001/07/05 09:07:19  taeubig
00029  Removed description string variable
00030 
00031  Revision 1.5  2000/07/05 21:51:37  mayerh
00032  added method getLeaBibEntry and made some changes
00033 
00034  Revision 1.4  2000/05/24 12:21:07  taeubig
00035  New compiler (gcc-2.95) and new Qt (2.1)
00036  Replaced "list" by "leda_list" etc.
00037 
00038  Revision 1.3  2000/03/30 19:13:55  mayerh
00039  added member-functions getClassification() and getName()
00040 
00041  Revision 1.2  2000/01/12 11:31:43  zoidl
00042  added javadoc comments and cosmetic changes in getDescription
00043 
00044  Revision 1.1  1999/12/21 15:35:15  zoidl
00045  added algorithm "McNaughton's rule"
00046 
00047 
00048  * #end# ************************************************************* */
00049 
00050 // from:
00051 //
00052 // Blazewicz et al., Scheduling Computer and Manufactoring Processes, 1996
00053 // Chapt. 5.1.1, p. 146, Algorithm 5.1.8
00054 // and 
00055 // Brucker, Scheduling Algorithms, 1995
00056 // Chap. 5.1.1, p. 100f
00057 
00058 // complexity: O(n)
00059 
00060 // short description (P.Brucker):
00061 // "Fill the machines successively, scheduling the jobs in any order and 
00062 //  splitting jobs into two parts whenever the above time bound is met.
00063 //  Schedule the second part of a preempted job on the next machine at 
00064 //  time zero."
00065 
00066 #ifndef SMCNAUGHTON_H
00067 #define SMCNAUGHTON_H
00068 
00069 // system header files
00070 #include <LEDA/sortseq.h>
00071 
00072 #ifndef leda_seq_item
00073 #define leda_seq_item seq_item
00074 #endif
00075 
00076 // project header files
00077 #include "SSchedAlgorithm.h"
00078 
00081 class SMcNaughton : public SSchedAlgorithm
00082 {
00083  public:
00084   virtual ~SMcNaughton();
00085   virtual void startup();
00086   virtual double innerLoop(const leda_list<STSysSchedEvent>& rEvents);
00087   virtual const leda_string getDescription() const;
00088   virtual const leda_string &getName() const;
00089   virtual const SClassification &getClassification() const;
00090   virtual SLeaBibEntry &getLeaBibEntry() const;
00091 
00092  private:
00093   // length of a preemptive schedule cannot be smaller than ...
00094   double _C;
00095 
00096   // over all simTimes store allocation information
00097   struct AllocInfo {
00098     int job;
00099     int mach; 
00100   };
00101   typedef leda_list<AllocInfo*> AllocInfoList;
00102   leda_sortseq<double, AllocInfoList*> _allocate;
00103 
00104   // over all simTimes store deallocation information
00105   typedef leda_list<int> DeallocInfoList;
00106   leda_sortseq<double, DeallocInfoList*> _deallocate;
00107 
00108   // these are "sequence pointers" that mark the current position 
00109   // in the sorted sequences (so we need not call sortseq::lookup() )
00110   leda_seq_item _allocSeqItem;    // points into _allocate
00111   leda_seq_item _deallocSeqItem;  // points into _deallocate
00112 };
00113 
00114 #endif
00115