=================================================
Some Notes on the BAP Greedy Heuristic Algorithms 
=================================================
  LeongHW  (Started: Sept 2002; Modified Sep 2005)


Below are some motes on Greedy Heuristic Algorithms 
for BAP Partitioning;

Your assigned greedy heuristic is given at the end.


---------------------------------
Idea 1: Two step greedy approach;
---------------------------------
  Repeat the following steps:

  step 1: Select an unassigned vessel v; 
  step 2:   Then select the best section, s, for vessel v;
            Assign vessel v to section s;


Pseudo-Code (Two Step Greedy)
-----------------------------
begin
  // Given list of unassigned vessels 
  // list of initially empty sections

  V := list of unassigned vessels;
  S := list of sections; 

  while (V not empty) do
  {
     v := SelectVessel(V);      // select a vessel v from V
     s := SelectSection(S,v);   // select section for vessel v
     if ( s != NULL) then
     {  Assign vessel v to section s; 
        Update section s;
     }
     V := V - {v};
  }

end;



----------------------------------
Idea 2: Minimize Incremental Cost;
----------------------------------
  repeat the following:
    for each unassigned vessel v and each section s,
       compute Incremental-cost(s,v);
    For all possible (v,s) combinations,
       let (v*,s*) be the combination that 
       optimizes Incremental-cost(s,v);
    assign vessel v* to section s*;
  until there is no more feasible assignment;


Pseudo-Code (Min Incremental Cost)
----------------------------------
begin
  // Given list of unassigned vessels 
  // list of initially empty sections

  V := list of unassigned vessels;
  S := list of sections; 

  repeat 
     min-incr-cost := infinity;
     for (all vessel v in V) do
     {  for (all section s in S) do
        {
   	   incr-cost := Incremental-cost(s,v); 
   	   if (incr-cost < min-incr-cost) then
           {  min-incr-cost := incr-cost;
	      min-vessel    := v; 
              min-section   := s;
           }
        }
     }
     Assign vessel min-vessel to section min-section;
     Update section min-section;
     V := V - {min-vessel};
  until (no more vessels can be assigned);

end;


The two step greedy approach is specified by two
selection criteria for: 
  (a) selection of a vessel (v) to assign
  (b) choice of a "best" section s to assign the selected vessel v             

We list a number of possible selection criteria that you can use:

(a) for Vessel Selection:
      VL  = Vessel Length (longest vessel first)
      CM  = Number of Container Moved (most first)
      DS  = Vessel Duration of Stay (longest first)
      AT  = Arrival Time (smallest first)
      DT  = Departure Time (smallest first)

(b) for Section Selection (given a vessel v):
      FF  = first fit (first section that "fits")
      TC  = section that gives the minimum increase in transshipment cost
      BF  = best fit (section that gives best fits for the vessel)
      WF  = worst fit (section that give worst fit for the vessel)
      SD  = section that gives the minimum increase in section density


The incremental cost approach is specified by the cost function to be used.
     ITC  = increase in the (transshipment cost)
     ISD  = increase in the (sum of section densities)


Your assigned Heuristic Algorithm
=================================

 Student     Heuristic          Name of Partitioner
----------------------------------------------------
 Trung       (VL,TC)            [BAPGDY1Partitioner]
 YueChao     (CM,TC)            [BAPGDY2Partitioner]
 Anders      (DS,FF)            [BAPGDY3Partitioner]
 YeNan       (Incremental-ITC)  [BAPGDY4Partitioner]
 ZhengJia    (Incremental-ISD)  [BAPGDY5Partitioner]

----------------------
(CS3233, LeongHW)