最大完了時間を最小化するジョブショップスケジューリング問題のベンチマーク

最大完了時間を最小化するジョブショップスケジューリング問題についてです．

ベンチマーク問題がないか探したところ，次のサイトにあるにはあったが，15×15問題や20×20問題と比較的大きな問題を対象としている．

ﾉric Taillard's page

10×10問題などを探すと，GitHubに次のサイトを見つけた．

instancesのフォルダー中身のabz5を見ると，

#+++++++++++++++++++++++++++++
# instance abz5
#+++++++++++++++++++++++++++++
# Adams, Balas, and Zawack 10x10 instance (Table 1, instance 5)
10 10
4 88 8 68 6 94 5 99 1 67 2 89 9 77 7 99 0 86 3 92
5 72 3 50 6 69 4 75 2 94 8 66 0 92 1 82 7 94 9 63
9 83 8 61 0 83 1 65 6 64 5 85 7 78 4 85 2 55 3 77
7 94 2 68 1 61 4 99 3 54 6 75 5 66 0 76 9 63 8 67
3 69 4 88 9 82 8 95 0 99 2 67 6 95 5 68 7 67 1 86
1 99 4 81 5 64 6 66 8 80 2 80 7 69 9 62 3 79 0 88
7 50 1 86 4 97 3 96 0 95 8 97 2 66 5 99 6 52 9 71
4 98 6 73 3 82 2 51 1 71 5 94 7 85 0 62 8 95 9 79
0 94 6 71 3 81 7 85 1 66 2 90 4 76 5 58 8 93 9 97
3 50 0 59 1 82 8 67 7 56 9 96 6 58 4 81 5 59 2 96

https://github.com/tamy0612/JSPLIB/blob/master/instances/abz5

となっている．

Five instances donated as ABZ5-9 due to Adams et al. [1].

https://github.com/tamy0612/JSPLIB

のベンチマークと考えられる．5行目の"10 10"は，10×10問題の意味．6行目

4 88 8 68 6 94 5 99 1 67 2 89 9 77 7 99 0 86 3 92

は，Job1に関して，（機械，処理時間）のデータセットが10機械分ならんでいる．つまり，Job1における機械0～機械9までの処理順は，

4→8→6→5→1→2→9→7→0→3

で，先頭の"4 88"は，機械4での処理時間は88という意味である．以下，同じように，Job10まで続く．

一方，最初に紹介したサイトのベンチマークでは，機械の番号は1から振られていた．

確認のため，最初に紹介したサイトのベンチマークにおける15×15問題とGitHubの15×15問題「ta01」を比較すると，同じ内容であることがわかる．ただし，前者は機械の番号付けが1から，後者は0から，という違いがある．

また，ある論文には，GitHubのサイトが次のように引用されている．

JSPLib. 2014. JSPLIB: Benchmark Instances for Job-Shop
Scheduling Problem. https://github.com/tamy0612/JSPLIB.
Accessed: 2022-03-30.

https://arxiv.org/abs/2110.06365

GitHubのトップページには，instances.jsonのファイルがあり，中身をみると，次のようになっている．

[
	{
		"name" : "abz5",
		"jobs" : 10,
		"machines" : 10,
		"optimum" : 1234,
		"path" : "instances/abz5"
	},
	{
		"name" : "abz6",
		"jobs" : 10,
		"machines" : 10,
		"optimum" : 943,
		"path" : "instances/abz6"
	},

instaces.jsonのファイルの中身を見て，どのベンチマークにするかを選べばよい．

2022年度の4回生が以下のようにまとめてくれました．

mは製品数，nが機械数です．

ベンチマーク問題早見表