Bi-Criteria Algorithm for Scheduling Jobs on Cluster Platforms
-Pierre-Francois Dutot, Lionel Eyraud, Gregory Mounie, Denis Trystram

Summary: This paper presents an algorithm that attempts to optimize both makespan
and average task completion time (assuming multiple users with tasks). The algorithm
estimates an optimal offline makespan and calculates the number of periods to
schedule tasks as well as the size of the periods, based on the esimated optimal
offline makespan and the minimum processing time for all the tasks. The size of the
periods (they called it "shelves") increase exponentially, with each succeeding
period twice as large as the previous period. The rationale is to allow the smaller
tasks to be scheduled earlier and finish earlier for a faster average task completion
time. The algorithm then tries to minimize makespan by compacting the schedule, 
allowing tasks to start earlier on a processor when that processor is idle. 
Additionally, the algorithm does some random shuffling of batch order to get the best
resulting compact schedule.

From the experiments, we learn of other scheduling algorithms:
Gang - Each task is scheduled on all processors. Since the assumption is that all
  tasks can be subdivided into an arbitrarily large number of subtasks, each task can
  be scheduled on all processors although the model for speedup varies for highly
  parallel and loosely parallel tasks.
Sequential - Each task scheduled on single processor in sequential order, scheduling
  large processing times first.
List Scheduling - First list the tasks of the large shelves, then the tasks of the
  small shelves
LPTF (Weighted largest processing time first) - Tasks sorted using ratio between
  weighted and their execution time. Good for makespan minimization.
SAF (Smallest area first) - tasks sorted accoring to their area. Goal is to improve
  average performance ratio for the average completion time.

Results seem to indicate SAF performed quite well in all cases (better than DEMT --
  their algorithm) except for what they consider more realistic application scenarios)