フローショップ・スケジューリングのジョンソン・アルゴリズムの実装（Ruby）

johnson.rb

require 'forwardable'

# ジョブを表すクラス
class Job
  # ジョブの名前
  # @return [String]
  attr_reader :name
  # ジョブの所要時間
  # @return [Array<Numeric>]
  attr_reader :length

  # コンストラクタ
  # @param [String] name ジョブの名前
  # @param [Numeric] len1 第1工程の時間
  # @param [Numeric] len2 第2工程の時間
  def initialize(name, len1, len2)
    @name = name
    @length = [len1, len2]
  end

  # 等しいか？
  # @param [Job] other
  def ==(other)
    @name == other.name && @length == other.length
  end

  # 短い方の所要時間を返す
  # @return [Array] 短い方の所要時間とどちらの工程かを表すシンボル
  def shorter_length
    len1 = length[0]
    len2 = length[1]

    len1 <= len2 ? [len1, :first] : [len2, :second]
  end
end

# ジョブの一覧を表すクラス
class JobList
  extend Forwardable
  include Enumerable

  # ジョブの配列
  attr_reader :jobs
  protected :jobs

  def_delegators(:@jobs,
                 :push,
                 :<<,
                 :each)

  # 配列からジョブの一覧を生成する
  # @param [Array<Job>] jobs ジョブの配列
  # @return [JobList]
  def self.from_array(jobs)
    new_list = new

    jobs.each do |job|
      new_list << job
    end

    new_list
  end

  # コンストラクタ
  def initialize
    @jobs = []
    @sorted_jobs = nil
  end

  # 等しいか？
  def ==(other)
    @jobs == other.jobs
  end

  # 短い方の所要時間を基準にしてソートする
  # @return [JobList]
  def sort_by_shorter_length
    self.class.from_array(sorted_jobs)
  end

  # 所要時間が最も短いジョブを返す
  # @return [Job]
  def shortest_job
    sorted_jobs.first
  end

  # 全体の所要時間が最も短くなるように並び替える
  # @return [JobList]
  def fastest_order
    rest_jobs = sorted_jobs.dup.reverse
    acc_jobs1 = []
    acc_jobs2 = []

    until rest_jobs.empty?
      shortest = rest_jobs.pop
      case shortest.shorter_length[1]
      when :first
        acc_jobs1 << shortest
      when :second
        acc_jobs2.unshift(shortest)
      else
        raise 'must not happen!'
      end
    end

    ordered = acc_jobs1 + acc_jobs2
    self.class.from_array(ordered)
  end

  private

  def sorted_jobs
    @sorted_jobs ||= @jobs.sort_by { |job| job.length.min }
  end
end

test_johnson.rb

require 'test/unit'
require_relative 'johnson'

class JohnsonTest < Test::Unit::TestCase
  def setup
    @j1 = Job.new('J1', 5, 2)
    @j2 = Job.new('J2', 1, 6)
    @j3 = Job.new('J3', 9, 7)
    @j4 = Job.new('J4', 3, 8)
    @j5 = Job.new('J5', 10, 3)

    @jobs = JobList.from_array([@j1, @j2, @j3, @j4, @j5])
  end

  def test_job_name
    assert_equal('J1', @j1.name, 'J1')
    assert_equal('J2', @j2.name, 'J2')
  end

  def test_job_length
    assert_equal([5, 2], @j1.length, 'J1')
    assert_equal([1, 6], @j2.length, 'J2')
  end

  def test_job_shorter_length
    assert_equal([2, :second], @j1.shorter_length, 'J1')
    assert_equal([1, :first], @j2.shorter_length, 'J2')
  end

  def test_job_list_sort_by_shorter_length
    expected = JobList.from_array([@j2, @j1, @j4, @j5, @j3])
    assert_equal(expected, @jobs.sort_by_shorter_length)
  end

  def test_job_list_shortest_job
    assert_equal(@j2, @jobs.shortest_job)
  end

  def test_job_list_fastest_order
    expected = JobList.from_array([@j2, @j4, @j3, @j5, @j1])
    assert_equal(expected, @jobs.fastest_order)
  end
end