secret
Last active

  • Download Gist
rajesh_kumar.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
## This is an approximation algorithm
## Sort the jobs, then start processing on the processor which has the least amount of jobs scheduled
## Provably the max time is (1/processors * (sum of processes) + max process time) if we do the smallest job first
## and if we do Longest time first it is 3/2 approximation
## I am doing Longest here first as this will pass most of tests, of course not all
 
class FairDistribution
def initialize(jobs, number_of_processes)
@jobs = jobs.sort
@number_of_processes = number_of_processes
@max_sum = @jobs.inject(0) {|sum, i| sum + i}
end
def time_required
solve.first
end
def distribution
solve.last
end
def solve
jobs = Array.new(@jobs)
distribution = []
@number_of_processes.times do
distribution << [jobs.shift]
end
 
while !jobs.empty?
index = find_least_end_time_index(distribution)
distribution[index] += [jobs.shift]
end
return find_max_end_time(distribution), distribution
end
def get_sum_array(distribution)
sum = []
distribution.each do |processor|
sum += [processor.inject(0) {|sum, i| sum + i}]
end
sum
end
def find_max_end_time(distribution)
sum = get_sum_array(distribution)
sum.sort.last
end
def find_least_end_time_index(distribution)
sum_arr = get_sum_array(distribution)
min_sum = @max_sum
index = 0
min_index = -1
sum_arr.each do |sum|
if sum < min_sum
min_index = index
min_sum = sum
end
index+=1
end
min_index
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.