フローショップスケジューラ

import sys, os, time, random

from functools import partial
from collections import namedtuple
from itertools import product

import neighbourhood as neigh
import heuristics as heur

##########
## 設定 ##
##########
TIME_LIMIT = 300.0            # ソルバを実行する時間 (単位は秒)
TIME_INCREMENT = 13.0         # ヒューリスティックの変更頻度 (単位は秒)
DEBUG_SWITCH = False          # True なら、実行中にヒューリスティックの情報を表示
MAX_LNS_NEIGHBOURHOODS = 1000 # LNS で探索する近傍の最大個数

if __name__ == '__main__':

    if len(sys.argv) == 2:
        data = parse_problem(sys.argv[1], 0)
    elif len(sys.argv) == 3:
        data = parse_problem(sys.argv[1], int(sys.argv[2]))
    else:
        print "\nUsage: python flow.py <Taillard problem file> [<instance number>]\n"
        sys.exit(0)

    (perm, ms) = solve(data)
    print_solution(data, perm)

def solve(data):
    """ フローショップスケジューリング問題のインスタンスを解く。 """

    # 循環インポートの問題を避けるため、戦略の初期化をここで行う。
    initialize_strategies()
    global STRATEGIES

    # 各戦略に対して、次の情報を記録する。
    #  improvements: この戦略による改善
    #  time_spent: この戦略が消費した時間
    #  weights: この戦略の優秀さに応じた重み
    #  usage: この戦略を利用した回数
    strat_improvements = {strategy: 0 for strategy in STRATEGIES}
    strat_time_spent = {strategy: 0 for strategy in STRATEGIES}
    strat_weights = {strategy: 1 for strategy in STRATEGIES}
    strat_usage = {strategy: 0 for strategy in STRATEGIES}

    # ジョブのランダムな置換から開始する。
    perm = range(len(data))
    random.shuffle(perm)

    # 最良の解を記録する。
    best_make = makespan(data, perm)
    best_perm = perm
    res = best_make

    # 反復の統計と時刻に関する情報を記録する。
    iteration = 0
    time_limit = time.time() + TIME_LIMIT
    time_last_switch = time.time()

    time_delta = TIME_LIMIT / 10
    checkpoint = time.time() + time_delta
    percent_complete = 10

    print "\nSolving..."

    while time.time() < time_limit:

        if time.time() > checkpoint:
            print " %d %%" % percent_complete
            percent_complete += 10
            checkpoint += time_delta

        iteration += 1

        # ヒューリスティックを使って最良の戦略を選択する
        strategy = pick_strategy(STRATEGIES, strat_weights)

        old_val = res
        old_time = time.time()

        # 候補の集合 (選択された戦略の近傍) から、選択された戦略の
        # ヒューリスティックを使って次の置換を選択する
        candidates = strategy.neighbourhood(data, perm)
        perm = strategy.heuristic(data, candidates)
        res = makespan(data, perm)

def makespan(data, perm):
    """ 与えられた解のメイクスパンを計算する。 """
    return compile_solution(data, perm)[-1][-1] + data[perm[-1]][-1]

        # 利用した戦略に関する統計情報を更新する。
        strat_improvements[strategy] += res - old_val
        strat_time_spent[strategy] += time.time() - old_time
        strat_usage[strategy] += 1

        if res < best_make:
            best_make = res
            best_perm = perm[:]

    print " %d %%\n" % percent_complete
    print "\nWent through %d iterations." % iteration

    print "\n(usage) Strategy:"
    results = sorted([(strat_weights[STRATEGIES[i]], i)
                      for i in range(len(STRATEGIES))], reverse=True)
    for (w, i) in results:
        print "(%d) \t%s" % (strat_usage[STRATEGIES[i]], STRATEGIES[i].name)

    return (best_perm, best_make)

def parse_problem(filename, k=1):
    """
    Taillard 問題ファイルの k 番目のインスタンスをパースして返す。

    Taillard 問題ファイルはフローショップスケジューリング問題の
    標準的なベンチマークセットである。
    """

    print "\nParsing..."

    with open(filename, 'r') as f:
        # インスタンスを分離する文字列
        problem_line = ('/number of jobs, number of machines, initial seed, '
                        'upper bound and lower bound :/')

        # ファイルを行ごとに分割し、さらに各行の両端にある空白文字を削除する。
        lines = map(str.strip, f.readlines())

        # 次の処理のために最初の行を調整する。
        lines[0] = '/' + lines[0]

        # ファイルに含まれないと分かっている文字 '/' を分離文字として使いながら、
        # k 番目のインスタンスが含まれる部分を切り出す。
        try:
            lines = '/'.join(lines).split(problem_line)[k].split('/')[2:]
        except IndexError:
            max_instances = len('/'.join(lines).split(problem_line)) - 1
            print "\nError: Instance must be within 1 and %d\n" % max_instances
            sys.exit(0)

        # スペースで行を分割し、各要素を int に変換する。
        data = [map(int, line.split()) for line in lines]

    # zip を適用して行と列を入れ替える。
    # 返り値の各要素は特定のジョブの各タスクの所要時間が入ったリストとなる。
    return zip(*data)

def compile_solution(data, perm):
    """ ジョブの置換を受け取り、機械のスケジュールを組み立てる。 """

    num_machines = len(data[0])

    # 注意: [[]] * m とはできない。
    # そうすると同じリストを m 個持つリストが作成されてしまう。
    machine_times = [[] for _ in range(num_machines)]

    # 最初のジョブに含まれるタスクを各機械に割り当てる。
    machine_times[0].append(0)
    for mach in range(1,num_machines):
        # このタスクを開始できるのは、一つ前のタスクが終わったとき
        machine_times[mach].append(machine_times[mach-1][0] +
                                   data[perm[0]][mach-1])

    # 残りのジョブの開始時刻を割り当てる。
    for i in range(1, len(perm)):

        # 最初の機械では停止時間が生じない。
        job = perm[i]
        machine_times[0].append(machine_times[0][-1] + data[perm[i-1]][0])

        # それ以外の機械では、次の二つのうち遅い方の時刻にタスクが開始される:
        # - 同じジョブの一つ前のタスクが完了した時刻
        # - 一つ前のジョブの同じタスクが完了した時刻
        for mach in range(1, num_machines):
            machine_times[mach].append(max(
                machine_times[mach-1][i] + data[perm[i]][mach-1],
                machine_times[mach][i-1] + data[perm[i-1]][mach]))

    return machine_times

def print_solution(data, perm):
    """ 計算された解に関する情報を出力する。 """

    sol = compile_solution(data, perm)

    print "\nPermutation: %s\n" % str([i+1 for i in perm])

    print "Makespan: %d\n" % makespan(data, perm)

    row_format ="{:>15}" * 4
    print row_format.format('Machine', 'Start Time', 'Finish Time', 'Idle Time')
    for mach in range(len(data[0])):
        finish_time = sol[mach][-1] + data[perm[-1]][mach]
        idle_time = (finish_time - sol[mach][0]) - sum([job[mach] for job in data])
        print row_format.format(mach+1, sol[mach][0], finish_time, idle_time)

    results = []
    for i in range(len(data)):
        finish_time = sol[-1][i] + data[perm[i]][-1]
        idle_time = (finish_time - sol[0][i]) - sum([time for time in data[perm[i]]])
        results.append((perm[i]+1, sol[0][i], finish_time, idle_time))

    print "\n"
    print row_format.format('Job', 'Start Time', 'Finish Time', 'Idle Time')
    for r in sorted(results):
        print row_format.format(*r)

    print "\n\nNote: Idle time does not include initial or final wait time.\n"

def neighbours_random(data, perm, num = 1):
    # num 個のランダムなジョブの置換を返す。
    # 返り値のリストは perm を含む。
    candidates = [perm]
    for i in range(num):
        candidate = perm[:]
        random.shuffle(candidate)
        candidates.append(candidate)
    return candidates

def neighbours_swap(data, perm):
    # 任意の要素の組を入れ替えた置換全体からなるリストを返す。
    candidates = [perm]
    for (i,j) in combinations(range(len(perm)), 2):
        candidate = perm[:]
        candidate[i], candidate[j] = candidate[j], candidate[i]
        candidates.append(candidate)
    return candidates

def neighbours_idle(data, perm, size=4):
    # 待機時間が長い size 個のジョブを入れ替えた置換を返す。
    candidates = [perm]

    # 各ジョブの待機時間を計算する。
    sol = flow.compile_solution(data, perm)
    results = []

    for i in range(len(data)):
        finish_time = sol[-1][i] + data[perm[i]][-1]
        idle_time = (finish_time - sol[0][i]) - sum([t for t in data[perm[i]]])
        results.append((idle_time, i))

    # 待機時間が長い size 個のジョブを取る。
    subset = [job_ind for (idle, job_ind) in reversed(sorted(results))][:size]

    # 待機時間が長いジョブを入れ替えた置換を列挙する。
    for ordering in permutations(subset):
        candidate = perm[:]
        for i in range(len(ordering)):
            candidate[subset[i]] = perm[ordering[i]]
        candidates.append(candidate)

    return candidates

def neighbours_LNS(data, perm, size = 2):
    # 巨大近傍探索における近傍を返す。
    candidates = [perm]

    # 近傍の個数が多くなりすぎないように部分集合のサイズを制限する。
    neighbourhoods = list(combinations(range(len(perm)), size))
    random.shuffle(neighbourhoods)

    for subset in neighbourhoods[:flow.MAX_LNS_NEIGHBOURHOODS]:

        # 部分集合ごとに、最良の候補を記録する。
        best_make = flow.makespan(data, perm)
        best_perm = perm

        # 注目している部分集合の全ての置換を考える。
        for ordering in permutations(subset):
            candidate = perm[:]
            for i in range(len(ordering)):
                candidate[subset[i]] = perm[ordering[i]]
            res = flow.makespan(data, candidate)
            if res < best_make:
                best_make = res
                best_perm = candidate

        # 最良の置換だけを LNS としての最終的な候補に加える。
        candidates.append(best_perm)

    return candidates

def heur_random(data, candidates):
    # 候補をランダムに選んで返す。
    return random.choice(candidates)

def heur_hillclimbing(data, candidates):
    # 候補の中で最良の置換を返す。
    scores = [(flow.makespan(data, perm), perm) for perm in candidates]
    return sorted(scores)[0][1]

def heur_random_hillclimbing(data, candidates):
    # メイクスパンでソートしたときの順位に反比例する確率で候補を選択して返す。
    scores = [(flow.makespan(data, perm), perm) for perm in candidates]
    i = 0
    while (random.random() < 0.5) and (i < len(scores) - 1):
        i += 1
    return sorted(scores)[i][1]

##########
## 戦略 ##
########################################################
## 戦略 (strategy) は近傍 (次の候補の集合) 生成関数と
## ヒューリスティック (候補の選択) 関数の組である。
##

STRATEGIES = []

# 名前付きタプルを使うと、辞書を使うよりも少しだけコードが読みやすくなる。
# 例えば strategy['name'] は strategy.name となる。
Strategy = namedtuple('Strategy', ['name', 'neighbourhood', 'heuristic'])

def initialize_strategies():

    global STRATEGIES

    # これから利用する近傍生成関数を (パラメータと共に) 定義する。
    neighbourhoods = [
        ('Random Permutation', partial(neigh.neighbours_random, num=100)),
        ('Swapped Pairs', neigh.neighbours_swap),
        ('Large Neighbourhood Search (2)', partial(neigh.neighbours_LNS, size=2)),
        ('Large Neighbourhood Search (3)', partial(neigh.neighbours_LNS, size=3)),
        ('Idle Neighbourhood (3)', partial(neigh.neighbours_idle, size=3)),
        ('Idle Neighbourhood (4)', partial(neigh.neighbours_idle, size=4)),
        ('Idle Neighbourhood (5)', partial(neigh.neighbours_idle, size=5))
    ]

    # これから利用するヒューリスティック関数を定義する。
    heuristics = [
        ('Hill Climbing', heur.heur_hillclimbing),
        ('Random Selection', heur.heur_random),
        ('Biased Random Selection', heur.heur_random_hillclimbing)
    ]

    # 両者の任意の組が戦略となる。
    for (n, h) in product(neighbourhoods, heuristics):
        STRATEGIES.append(Strategy("%s / %s" % (n[0], h[0]), n[1], h[1]))

def pick_strategy(strategies, weights):
    # ルーレット選択: 重みを考慮しつつランダムに戦略を選択する。
    # 戦略をランダムに選択するのではなく、これまでに優れた結果を示している戦略を
    # (大きな重みを通して) 多く選択する。
    total = sum([weights[strategy] for strategy in strategies])
    pick = random.uniform(0, total)
    count = weights[strategies[0]]

    i = 0
    while pick > count:
        count += weights[strategies[i+1]]
        i += 1

    return strategies[i]

        # 戦略の重みを定期的に再計算する。
        # こうすることで、優れた結果を示す戦略が探索で使われやすくなる。
        if time.time() > time_last_switch + TIME_INCREMENT:
            time_last_switch = time.time()

            # 改善量を計算時間で割って正規化する。
            results = sorted([
                (float(strat_improvements[s]) / max(0.001, strat_time_spent[s]), s)
                for s in STRATEGIES])

            # 成績の良い戦略の重みを相対的に増加させる。
            for i in range(len(STRATEGIES)):
                strat_weights[results[i][1]] += len(STRATEGIES) - i

                # 未使用の戦略の重みを増加させ、飢餓を防ぐ。
                if results[i][0] == 0:
                    strat_weights[results[i][1]] += len(STRATEGIES)

            if DEBUG_SWITCH:
                print "\nComputing another switch..."
                print "Best: %s (%d)" % (results[0][1].name, results[0][0])
                print "Worst: %s (%d)" % (results[-1][1].name, results[-1][0])
                print results
                print sorted([strat_weights[STRATEGIES[i]]
                              for i in range(len(STRATEGIES))])

            strat_improvements = {strategy: 0 for strategy in STRATEGIES}
            strat_time_spent = {strategy: 0 for strategy in STRATEGIES}