Skip to content

Instantly share code, notes, and snippets.

@aurelienbottazini
Created February 15, 2010 23:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aurelienbottazini/305120 to your computer and use it in GitHub Desktop.
Save aurelienbottazini/305120 to your computer and use it in GitHub Desktop.
=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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment