組合せ最適化 - 典型問題 - ジョブショップ問題

典型問題と実行方法

##ジョブショップ問題

与えられた$n$個のジョブ$V=\{1,\dots,n\}$を$m$台の機械で処理する。1つの機械では、同時に1つのジョブしか処理できない。全てのジョブの終了時間を最小にするスケジュールを求めよ。
どのジョブに対しても機械の処理順序が決まっている場合、フローショップ問題という。

##実行方法(2機械フローショップ問題の例)

usage

Signature: two_machine_flowshop(p)
Docstring:
2機械フローショップ問題
    2台のフローショップ型のジョブスケジュールを求める(ジョンソン法)
入力
    p: (前工程処理時間, 後工程処理時間)の製品ごとのリスト
出力
    処理時間と処理順のリスト

python

from ortoolpy import two_machine_flowshop
two_machine_flowshop([(4, 3), (3, 1), (1, 4)])

結果

(9, [2, 0, 1])

python

# pandas.DataFrame
from ortoolpy.optimization import TwoMachineFlowshop
TwoMachineFlowshop('data/flowshop.csv')[1]

	first	second
2	1	4
0	4	3
1	3	1

##データ

• data/flowshop.csv