scheduler_for_buckets

scheduler_for_buckets.rb

# // # // Implement a function that orders inputs to schedule for min TAT (Turn around time == Total Run Time)
# // # // Input: (list of runtimes, number of parallel buckets)
# // # // Output: Should parallelize individual tasks such that total TAT is minimum.
# // # // Example:
# // # // In: [4, 3, 100, 2, 1], parallel = 2
# // # // Out: [[100], [4, 3, 2, 1]], TAT: 100
# // # //     [100, 10] -> 100
# // # // In: [4, 3, 100, 2, 1], parallel = 1
# // # // Out: [[100, 4, 3, 2, 1]], TAT: 110
# // # // 
# // # // In: [4, 3, 1, 2], parallel = 2
# // # // Out: [[4, 1], [3, 2]], TAT: 5, 2x speed u


# [4, 3, 100, 2, 1] -> [100, 4, 3, 2, 1]
# p=2 [4, 3, 2], [8, 1] limit 105
# 1. p=3 -> [...], [], [] => 
# 2. loop
#  for el in [...]
#     try to move
#     if time < lowest
#      lowest = time
#      remember move
#  if found new lowest time
#     aplly
#  else
#    break

def bestSchedule (times, parallel)
  # 1 phase
  buckets = [times.sort]
  return times.map { |x| [x] } if times.size <= parallel

  sums = [times[0..(parallel - 1)].sum]
  1.upto(parallel - 1) do
    last = buckets[0][-1]
    buckets[0].delete_at(-1)
    buckets << [last]
    sums << last
  end
  min_time = [sums.max, buckets[0].sum].max

  # 2 phase
  loop do
    best_el = -1
    best_bucket = -1
    sums0 = buckets.map(&:sum).max

    buckets[0].each_with_index do |el, index|
      # TODO: use sums
      # check all buckets
      local_best_bucket = -1
      # new first bucket time
      max = sums0 - el
      1.upto(parallel - 1) do |i|
        # i-th backet
        new_time = 0

        # new_time = max time for all buckets
        1.upto(parallel - 1) do |j|
          sum = buckets[j].sum
          nt = i == j ? sum + el : sum
          new_time = nt if nt > new_time
        end
        # max = total time
        if max < new_time
          max = new_time
          local_best_bucket = i
        end
      end
      if max < min_time
        min_time = max
        best_el = index
        best_bucket = local_best_bucket
      end
    end

    break if best_el == -1

    buckets[best_bucket] << buckets[0][best_el]
    buckets[0].delete_at(best_el)
  end

  return buckets
end

timesNparallel = [
    [[1, 2, 3, 4, 5], 2],
    [[1, 2, 3, 4, 100], 2],
    [[1, 2, 3, 4, 5], 5],
    [[1, 2, 3, 4, 5], 4],
    [[1, 3, 5, 8, 21, 15, 12, 7], 2],
    [[1, 3], 4],
    [[1, 1, 1, 1, 1], 2],
    [[1, 1, 1, 1, 1], 4]
]
timesNparallel.each_with_index do |tp|
 buckets = bestSchedule(tp[0], tp[1])
 print "The backets for #{tp[0]} with #{tp[1]} cores are #{buckets.inspect}   (#{buckets.map{|a| a.sum}.inspect})\n"
end