私は、NP-Hard/Complete の問題を実装およびテストするプロジェクトに取り組んでいます。私はスケジューリングで何かをするという一般的なアイデアを持っていて、ジョブショップの問題についてたくさん読んだことがあります。OR ライブラリから使用する有名なテスト ケース/ベンチマークがあることは知っています。テストインスタンスを読み取り、そのデータを保存するためのコード (Java) があります。今、私は、スケジュールを作成するアルゴリズム/方法を見つけて、最適なスケジュールを提示しようとしてループに詰まっているように感じます. 私は多くの学術論文を読んでいますが、特に複雑な集合表記については、それらの中で少し迷ってしまいます。疑似コードの例をもっと見つけたいと思います。私はこれが古典的な問題であることを知っており、ジョブショップに対する単純な古典的な解決策、特に疑似コードの例もある提案を誰かが持っているかどうか疑問に思っています。このプロジェクトのために独自の調査を行う必要はありません。NP 困難な問題を解決するための既知の手法を適用し、コードを記述し、テストを実行し、実験結果を提示し、それらにコメントする方法を学ぶ必要があるだけです。アドバイスや助けをいただければ幸いです。
「多くの仕事を行う必要があり、すべての仕事は一定の時間、多くのマシンを使用することから成り立っています。問題は、すべてのジョブをすべての異なるマシンで最短時間で実行するための最適な計画を見つけることです。 ."
問題の例:
データライン セクションの各行は、10 組の連続した数字でジョブを指定します。数値の各ペアは、ジョブの 1 つのタスクを定義します。これは、マシン上でのジョブの処理を表します。各ペアについて、最初の数字はそれが実行されるマシンを識別し、2 番目の数字は期間です。10 個のペアの順序によって、ジョブのタスクの順序が定義されます。
「ローレンス 10x10 インスタンス」(表 6、インスタンス 4); (seta4) または (A4) とも呼ばれます (Applegate および Cook、1991 年) -10 台のマシン、0 ～ 9 の番号が付けられている -10 行 = 10 ジョブ --最適: 842
2 44 3 5 5 58 4 97 0 9 7 84 8 77 9 96 1 58 6 89
4 15 7 31 1 87 8 57 0 77 3 85 2 81 5 39 9 73 6 21
9 82 6 22 4 10 3 70 1 49 0 40 8 34 2 48 7 80 5 71
1 91 2 17 7 62 5 75 8 47 4 11 3 7 6 72 9 35 0 55
6 71 1 90 3 75 0 64 2 94 8 15 4 12 7 67 9 20 5 50
7 70 5 93 8 77 2 29 4 58 6 93 3 68 1 57 9 7 0 52
6 87 1 63 4 26 5 6 2 82 3 27 7 56 8 48 9 36 0 95
0 36 5 15 8 41 9 78 3 76 6 84 4 30 7 76 2 36 1 8
5 88 2 81 3 13 6 82 4 54 7 13 8 29 9 40 1 78 0 75
9 88 4 54 6 64 7 32 0 52 2 6 8 54 5 82 3 6 1 26