public

  • Download Gist
fair_distribution.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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
=begin
Original problem url: http://rubylearning.com/blog/2010/01/26/rpcfn-fair-distribution-6/
 
The goal of this class is to schedule printing jobs between printing machines (presses)
 
Jobs should be distributed "in such a manner that (a) all t-shirts are printed in the least amount of time,
and (b) the distribution of work across machines is as fair as possible (i.e. the standard deviation
of the time each machine spends working is minimized)."
 
Usage:
jobs = [5,5,4,4,3,3,3]
number_of_presses = 3
 
fd = FairDistribution.new(jobs, number_of_presses)
fd.time_required
fd.distribution
 
Note:
Class ensure that jobs is an array containing only positive numeric
Class ensure that number_of_presses is valid (positive and an integer)
 
tested with ruby 1.8.6-p388, 1.8.7-p249 and 1.9.1-p378
=end
class FairDistribution
 
attr_accessor :distribution, :time_required
 
def initialize jobs, number_of_presses
 
if number_of_presses.integer? == false || number_of_presses < 1
raise ArgumentError, "The number of presses needs to be an integer greater or equal to 1"
end
 
if jobs.is_a?(Array) == false
raise ArgumentError, "jobs should be an array containing positive numeric"
end
 
jobs.each do |job|
if job.is_a?(Numeric) == false || job < 0
raise ArgumentError, "All Jobs should be positive numeric"
end
end
 
@number_of_presses = number_of_presses
 
# starting with the highest time possible (sum of all jobs)
@time_required = jobs.inject(0.0) { |sum, n| sum + n }
 
# will hold signatures of tested distributions (so that we don't
# try to compute equivalent distribution)
@signatures = Hash.new
 
# initializing an empty distribution with the correct number of presses
@distribution = []
number_of_presses.times { @distribution << Array.new }
 
# sets @time_required and @distribution
distribute_jobs [[]], jobs.dup
end
 
 
private
 
# Recusive procedure
# It should be called initially with a list of jobs and an empty
# distribution containing one empty press ( = [[]]).
# It will try to find the optimal distribution and store it in
# @distribution. It will also store the time required by this
# optimal distribution in @time_required.
def distribute_jobs distrib, jobs
 
# we can stop, we have reached the maximum number of press
if distrib.size == @number_of_presses
 
# copy the remaining jobs in last press and empty jobs array
while !jobs.empty?
distrib.last << jobs.pop
end
 
# we don't have any solution yet, copy this one
if FairDistribution.is_distribution_empty?(@distribution)
@distribution = distrib
# let's check if this distribution is better than our previous
# best and make it the new solution if it is
elsif FairDistribution.time_required(distrib) <= @time_required &&
FairDistribution.standard_deviation(distrib) < FairDistribution.standard_deviation(@distribution)
@distribution = distrib
@time_required = FairDistribution.time_required(@distribution)
end
 
return
end
 
# create a signature for this distribution so that we don't test
# equivalent distributions.
# ex: [[5, 4], [5, 4], [3, 3, 3]] and [[4, 5], [5, 4], [3, 3, 3]]
# are equivalent and only one of them needs to be tested.
signature = String.new
distrib.each_with_index {|e, index| distrib[index] = e.sort }
distrib.sort {|a,b| a.inject(0.0) { |sum, n| sum + n } <=> b.inject(0.0) { |sum, n| sum + n } }.each do |press|
press.each { |job| signature << "#{job};" }
signature << "|"
end
 
# have we tried yet this distribution?
if @signatures.key?(signature) == false
 
# we have exceeded the @time_required of our current best
# distribution, we don't need to test this distribution
if FairDistribution.time_required(distrib) <= @time_required
# mark this distribution has tried
@signatures[signature] = 1
 
jobs.each_with_index do |job, index|
 
# we create two new distributions
# First one : we add one job in last press
# Second one: we add one job in last press and we add one
# more press
distrib_copy = FairDistribution.dup_distrib(distrib)
distrib_copy.last << job
distrib_copy2 = FairDistribution.dup_distrib(distrib_copy)
distrib_copy2 << Array.new
 
# copying remaining jobs list and removing the job we added
# in the two new distributions
jobs_copy = jobs.dup
jobs_copy.slice!(index)
 
distribute_jobs distrib_copy, jobs_copy
distribute_jobs distrib_copy2, jobs_copy.dup
end
end
end
end
 
def self.dup_distrib distrib
 
new_distrib = Array.new
distrib.each do |d|
new_distrib << d.dup
end
 
return new_distrib
end
 
def self.standard_deviation distrib
 
sums = Array.new
distrib.each do |d|
sums << d.inject(0.0) { |sum, n| sum + n }
end
 
mean = sums.inject(0.0) { |sum, n| sum + n } / distrib.size
variance = sums.inject(0.0) {|sum, n| sum + (n - mean) * (n - mean) } / distrib.size
return Math.sqrt(variance)
end
 
def self.time_required distrib
 
time_required = 0.0
if distrib != nil
distrib.each do |d|
d_time_required = d.inject(0) { |sum, n| sum + n }
if d_time_required > time_required
time_required = d_time_required
end
end
end
 
return time_required
end
 
# empty meaning distribution containing no press or presses
# but without any jobs
def self.is_distribution_empty? distrib
is_empty = true
 
distrib.each do |d|
if d.size > 0
is_empty = false
break
end
end
 
return is_empty
end
 
end
fair_distribution_test.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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
require 'test/unit'
require 'fair_distribution'
 
#FairDistribution = LowMemoryFairDistribution
 
class FairQueueTest < Test::Unit::TestCase
def test_basic1
jobs = [10, 15, 20, 24, 30, 45, 75]
number_of_presses = 2
 
exp_max = 110
 
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal exp_max, fd.time_required
 
# A Solution
# [75, 20, 15],
# [45, 30, 24, 10,]
end
 
def test_basic2
jobs = [1.0, 4.75, 2.83, 1.1, 5.8, 3.5, 4.4]
number_of_presses = 4
 
exp_max = 6.33
exp_distribution = [
[1.0, 4.75],
[2.83, 3.5],
[1.1, 4.4],
[5.8]
]
 
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal exp_max, fd.time_required
assert_distributions_are_equivalent exp_distribution, fd.distribution
end
 
def test_basic3
jobs = [0.23, 0.47, 0.73, 1.5, 3.0, 3.2, 1.75, 2.3, 0.11, 0.27, 1.09]
number_of_presses = 4
 
exp_max = 3.73
 
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal exp_max, fd.time_required
 
# A Solution
# [3.2, 0.47],
# [3.0, 0.73],
# [2.3, 1.09, 0.23],
# [1.75, 1.5, 0.27, 0.11]
end if ARGV[0] == "full" # only use this TC if 'full' is added as an argument.
 
def test_basic4
jobs = [5,5,4,4,3,3,3]
number_of_presses = 3
 
exp_max = 9
exp_distribution = [
[5,4],
[5,4],
[3,3,3],
]
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal exp_max, fd.time_required
assert_distributions_are_equivalent exp_distribution, fd.distribution
end
 
def test_basic5
fd = FairDistribution.new([0.23, 0.47, 0.73, 1.5, 3.0, 3.2], 4)
assert_equal 3.2, fd.time_required
assert_distributions_are_equivalent [[3.0], [3.2], [0.23, 0.47, 0.73], [1.5]], fd.distribution
end
 
def test_basic6
jobs = [5,5,4,4,3,3,3,1,1,1]
number_of_presses = 3
 
exp_max = 10
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal exp_max, fd.time_required
end
 
def test_basic7
jobs = [10,10,1,1,1,1,1,1]
number_of_presses = 3
 
exp_max = 10
exp_distribution = [
[10],
[10],
[1,1,1,1,1,1],
]
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal exp_max, fd.time_required
end
 
def test_empty_jobs
jobs = []
number_of_presses = 2
fd = FairDistribution.new(jobs, number_of_presses)
assert_equal 0.0 , fd.time_required
assert_distributions_are_equivalent [[],[]], fd.distribution
 
number_of_presses = 1
fd = FairDistribution.new(jobs, number_of_presses)
assert_distributions_are_equivalent [[]], fd.distribution
end
 
def test_zero_press
jobs = [1,2,3,4,5,6]
number_of_presses = 0
 
assert_raise(ArgumentError) { FairDistribution.new(jobs, number_of_presses) }
end
 
def test_float_number_of_press
jobs = [3,4,5,6,7,8]
number_of_presses = 2.3
 
assert_raise(ArgumentError) { FairDistribution.new(jobs, number_of_presses) }
end
 
def test_bad_jobs
jobs = ["dscscds", 1, 2.3]
number_of_presses = 3
 
assert_raise(ArgumentError) { FairDistribution.new(jobs, number_of_presses)}
 
jobs = [5, 2, -3]
assert_raise(ArgumentError) { FairDistribution.new(jobs, number_of_presses)}
 
jobs = "wrong"
assert_raise(ArgumentError) { FairDistribution.new(jobs, number_of_presses)}
end
 
# Testing Implementation
# def test_arrays_have_same_elements
# assert arrays_have_same_elements?([1,2,3], [3,1,2])
# assert !arrays_have_same_elements?([], [1,2,3])
# assert !arrays_have_same_elements?([1,2,3], [1,2,3,4])
# assert !arrays_have_same_elements?([1,2,3,4], [1,2,3])
# assert !arrays_have_same_elements?([1,1], [1])
# assert !arrays_have_same_elements?([1], [1,1])
# end
#
# def test_distributions_are_equivalent
# assert distributions_are_equivalent?([[1, 2], [2, 3]], [[3, 2], [2, 1]])
# assert !distributions_are_equivalent?([[1, 3], [2, 2]], [[3, 2], [2, 1]])
# assert !distributions_are_equivalent?([[1, 2], [3, 2]], [[3, 2], [3, 2]])
# assert !distributions_are_equivalent?([[1, 2], [1, 2]], [[3, 2], [2, 1]])
# end
 
private
def assert_distributions_are_equivalent(dist1, dist2, msg=nil)
failure_message = "Distributions not equivalent: #{msg}: #{dist1.inspect} not equivalent to #{dist2.inspect}"
assert(distributions_are_equivalent?(dist1, dist2), failure_message)
end
 
def distributions_are_equivalent?(dist1, dist2)
return false if dist1.size != dist2.size
my_dist1 = dist1.dup
my_dist2 = dist2.dup
 
my_dist1.reject! {|queue1|
dist2.detect {|queue2| arrays_have_same_elements?(queue1, queue2)}
}
 
my_dist2.reject! {|queue2|
dist1.detect {|queue1| arrays_have_same_elements?(queue1, queue2)}
}
 
my_dist1.empty? && my_dist2.empty?
end
 
def arrays_have_same_elements?(arr1, arr2)
arr1.size == arr2.size && (arr1 - arr2).empty?
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.