algorithms/SJohnson.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: SJohnson.h,v 1.4 2003/01/08 18:57:10 meierb Exp $
00008 
00009  Purpose : implementation of Johnson's algorithm for F2||C_max
00010 
00011  RCS-Log:
00012  $Log: SJohnson.h,v $
00013  Revision 1.4  2003/01/08 18:57:10  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.2  2002/11/13 18:18:29  taeubig
00020  Workarounds for using LEDA 4.4 and also the former releases
00021 
00022  Revision 1.1  2002/08/29 12:59:58  taeubig
00023  Added the sources
00024 
00025  Revision 1.5  2000/07/05 21:51:25  mayerh
00026  added method getLeaBibEntry and made some changes
00027 
00028  Revision 1.4  2000/05/24 12:21:04  taeubig
00029  New compiler (gcc-2.95) and new Qt (2.1)
00030  Replaced "list" by "leda_list" etc.
00031 
00032  Revision 1.3  2000/03/30 19:13:53  mayerh
00033  added member-functions getClassification() and getName()
00034 
00035  Revision 1.2  2000/01/12 11:31:39  zoidl
00036  added javadoc comments and cosmetic changes in getDescription
00037 
00038  Revision 1.1  2000/01/03 23:07:16  zoidl
00039  added Johnson's algorithm for F2||C_max
00040 
00041 
00042  * #end# ************************************************************* */
00043 
00044 // from:
00045 //
00046 // Blazewicz et al., Scheduling Computer and Manufactoring Processes, 1996
00047 // Chapt. 7.2.1, p. 252, Algorithm 7.2.1
00048 // and 
00049 // Brucker, Scheduling Algorithms, 1995
00050 // Chap. 6.3.1, p. 164
00051 
00052 // complexity: O(n log(n))
00053 
00054 #ifndef SJOHNSON_H
00055 #define SJOHNSON_H
00056 
00057 // system header files
00058 
00059 // project header files
00060 #include "SSchedAlgorithm.h"
00061 
00064 class SJohnson : public SSchedAlgorithm
00065 {
00066  public:
00067   virtual ~SJohnson() {};
00068   virtual void startup();
00069   virtual double innerLoop(const leda_list<STSysSchedEvent>& rEvents);
00070   virtual const leda_string getDescription() const;
00071   virtual const leda_string &getName() const;
00072   virtual const SClassification &getClassification() const;
00073   virtual SLeaBibEntry &getLeaBibEntry() const;
00074  private:
00075   // concatenation sequence (list of job indices)
00076   leda_list<int> _L;
00077   // for each machine the position in above list is stored
00078   leda_array<leda_list_item> _jobForMach;
00079 };
00080 
00081 #endif