algorithms/SSmithsRatioRule.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: SSmithsRatioRule.h,v 1.5 2003/01/08 18:57:11 meierb Exp $
00008 
00009  Purpose : implementation of Smith's "ratio rule", also known as
00010            Smith's weighted shortest processing time (WSPT) rule.
00011      Optimal for:  1 || sum(w_j C_j) ; if all w_j > 0 
00012                          1 || sum(C_j)     ; if all w_j = 1
00013 
00014  RCS-Log:
00015  $Log: SSmithsRatioRule.h,v $
00016  Revision 1.5  2003/01/08 18:57:11  meierb
00017  added randomized release times
00018 
00019  Revision 1.2  2002/12/23 21:52:18  meierb
00020  *** empty log message ***
00021 
00022  Revision 1.1.1.1  2002/12/02 22:26:19  meierb
00023  my_schedule
00024 
00025  Revision 1.3  2002/11/13 18:18:29  taeubig
00026  Workarounds for using LEDA 4.4 and also the former releases
00027 
00028  Revision 1.2  2002/11/10 13:32:52  taeubig
00029  namespace and header include changes
00030 
00031  Revision 1.1  2002/08/29 12:59:58  taeubig
00032  Added the sources
00033 
00034  Revision 1.8  2000/07/05 21:51:49  mayerh
00035  added method getLeaBibEntry and made some changes
00036 
00037  Revision 1.7  2000/05/24 12:21:13  taeubig
00038  New compiler (gcc-2.95) and new Qt (2.1)
00039  Replaced "list" by "leda_list" etc.
00040 
00041  Revision 1.6  2000/03/30 19:14:01  mayerh
00042  added member-functions getClassification() and getName()
00043 
00044  Revision 1.5  2000/01/12 11:31:40  zoidl
00045  added javadoc comments and cosmetic changes in getDescription
00046 
00047  Revision 1.4  1999/12/21 15:35:36  zoidl
00048  changed getDescription(), now returning string instead string&
00049 
00050  Revision 1.3  1999/12/21 09:02:34  zoidl
00051  added getDescription() (info about problem, complexity, ... )
00052 
00053  Revision 1.2  1999/12/20 08:46:50  zoidl
00054  added constructor
00055 
00056  Revision 1.1  1999/12/16 17:04:37  zoidl
00057  added Smith's "ratio rule" algorithm for 1||sum(w_j C_j)
00058 
00059 
00060  * #end# ************************************************************* */
00061 
00062 // from:
00063 //
00064 // Blazewicz et al., Scheduling Computer and Manufactoring Processes, 1996
00065 // Chapt. 4.2, p. 83f
00066 //   and
00067 // Brucker, Scheduling Algorithms, 1995
00068 // Chap. 4.3.1, p. 77f
00069 
00070 // short description of Smith's ratio rule (P. Brucker):
00071 // "Put the jobs in order of nondecreasing ratios 
00072 //  p_j / w_j, which applies if all w_j > 0."
00073 
00074 
00075 #ifndef SSMITHSRATIORULE_H
00076 #define SSMITHSRATIORULE_H
00077 
00078 // system header files
00079 #include <LEDA/p_queue.h>
00080 
00081 #ifndef leda_pq_item
00082 #define leda_pq_item pq_item
00083 #endif
00084 
00085 // project header files
00086 #include "SSchedAlgorithm.h"
00087 
00092 class SSmithsRatioRule : public SSchedAlgorithm
00093 {
00094  public:
00095   virtual ~SSmithsRatioRule() {};
00096   virtual void startup();
00097   virtual double innerLoop(const leda_list<STSysSchedEvent>& rEvents);
00098   virtual bool isFinished() const;
00099   virtual const leda_string getDescription() const;
00100   virtual const leda_string &getName() const;
00101   virtual const SClassification &getClassification() const;
00102   virtual SLeaBibEntry &getLeaBibEntry() const;
00103  private:
00104   leda_string _descr;
00105   leda_p_queue<double,SJob*> _jobsOrder;
00106 
00107 // for creating statistics(will be deleted after testing) *********
00108   int numjobs;
00109   int count;
00110   double* weightarray;
00111   double* meanarray;
00112   double* timearray;
00113   // ********************
00114   
00115 };
00116 
00117 #endif