「ジョブスケジューリング問題」をPythonで解きたい

### 前提・実現したいこと

ここに質問の内容を詳しく書いてください。
「ジョブスケジューリング問題」についてPythonを用いて、一番ペナルティが少ない組み合わせを求めたいです。
A~E のリストには、0番目が必要時間、1番目があるべき終了時間、2番目がその終了時間を超えた場合、１単位に付き加えられるペナルティです。
このコードではとりあえず、全ての組み合わせの結果のペナルティの合計をその組み合わせ数分、表示したいのですが何も表示されませんでした。

初めての質問のため、分かりづらい点が多数あると思われますがご指摘くださるとありがたいです。
よろしくお願いします。

何も表示されません。

エラーメッセージ

Python
1
2
3### import itertools
4
5A = [10, 20, 8]
6B = [20, 25, 2]
7C = [15, 20, 3]
8D = [25, 35, 2]
9E = [50, 30, 5]
10
11per = [A, B, C, D, E]
12
13for aaa in itertools.permutations(per,  5):
14    qqa = aaa[0]
15    qqb = aaa[1]
16    qqc = aaa[2]
17    qqd = aaa[3]
18    qqe = aaa[4]
19
20#1人目
21    wwa = qqa[1] - qqa[0]
22    if wwa < 0:
23        alla = (-wwa) * qqa[2]
24#2人目
25        wwb = abs(wwa) + qqb[0]
26        wwb = qqb[1] - wwb
27        if wwb < 0:
28            allb = (-wwb) * qqb[2]
29    #3人目
30            wwc = abs(wwb) + qqc[0]
31            wwc = qqc[1] - wwc
32            if wwc < 0:
33                allc = (-wwc) * qqc[2]
34        #4人目
35                wwd = abs(wwc) + qqd[0]
36                wwd = qqd[1] - wwd
37                if wwd < 0:
38                    alld = (-wwd) * qqd[2]
39            #5人目
40                    wwe = wwd + qqe[0]
41                    wwe = qqe[1] - wwe
42                    if wwe < 0:
43                        alle = (-wwe) * qqe[2]
44
45                        print(alla + allb + allc + alld + alle)
46
47
48

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

ppaul

2021/05/05 06:22

print(alla + allb + allc + alld + alle) の下にある ```Python という行を、 import itertools の前の行に移動してください。そうでないと、ソースコードが読めません。

rrkkr

2021/05/05 06:28

ご指摘ありがとうございます。修正してみました。確認できますでしょうか。

ppaul

2021/05/05 07:13

はい、表示されました。 print文のインデントを修正して、あと初期化を加えれば出力が出るようにすることはできますが、たぶん求める答えではないでしょう。 rrkkrさんの解きたい「ジョブスケジューリング問題」が何なのかが不明確です。どこかのサイトに問題の定義があるなら、そのURLを教えてください。サイトにないのであれば、簡単で良いので問題を説明してください。そうすれば回答できると思います。

rrkkr

2021/05/05 07:51

知識不足のため、有名な問題だと勘違いしていました。問題の詳細は、追加した画像で確認していただけますでしょうか。

ppaul

2021/05/05 09:05

いくつか想定してみた問題の内のひとつですね。ご質問は 1 print文が何も出力しない理由を知りたい。 2 どういうアルゴリズムで考えれば良いかを知りたい。 3 Python言語の仕様を理解したい 4 全ての組み合わせのコストを出力したい 5 なるべく高速な解を知りたいのどれでしょう。それぞれの質問で回答は全く違うものになります。

rrkkr

2021/05/05 10:15

はじめの質問内容の時点では、１の内容のつもりでしたが、特に、２について詳しく回答を得たいと思っています。大変押し付けがましい事ではありますが、お時間があれば1~5の内容全てご教授くださると嬉しいです。

行動規範の内容に同意します

回答2件

ベストアンサー

アルゴリズムについて知りたいとのことですね。
わたしは、この問題を初めて知ったので、一般的にどのように考えていくかという方向性を説明します。

N人の怪我人の場合を考えます。
全ての組み合わせでペナルティを計算すると、組み合わせがN!(Nの階乗)個あり、それぞれの組み合わせの中でN個の怪我人について比較1回、乗算1回、加算2回が実行されるので、N!*5Nの計算を行うことになります。

この計算量を減らすにはどうすれば良いかを考えてみましょう。
問題は5人ですが4人に減らして考えてみましょう。4人の場合は計算量は4!54=480です。
ABCDの4人を前半でABの二人、後半でCDの二人を手術するというように考えると、前半はABとBAのどちらかで、ペナルティはAが先なら10、Bが先なら80です。終わったときの経過時間は同じ30ですので、CDの実行順序によらずAを先に手術した方が良い事がわかります。
これを考えると、時間ゼロから考えてABの実行順序を決めるために2!52=20の計算、CDの実行順序を決めるためにも20の計算で合計40の計算によって、ペナルティ最小を決めることが出来ます。これは、ABCDをABとCDに分けたときだけですので、分け方の数6通りを掛けて総計算量は40*6=240となります。
これを一般化して、N=2^nの場合には再帰的に前半と後半に分けて計算することを繰り返sして、計算量を減らすのは一般的な手法です。

今回の問題では、残っている全ての人の「あるべき終了時間」を過ぎてしまった場合には、もう少し効率の良い計算方法が見つかりそうな気がします。それば見つかればさらに効率の良い計算ができるでしょう。思いついたら追加します。

投稿2021/05/06 01:37

ppaul

総合スコア24670

rrkkr

2021/05/06 03:32

ご回答ありがとうございます。 ”比較1回、乗算1回、加算2回”の部分で、全体を考えてから整理することが必要だと学びました。最後の内容は私も、もう少し考えてみます。

行動規範の内容に同意します

Python
1import itertools
2
3A = [10, 20, 8]
4B = [20, 25, 2]
5C = [15, 20, 3]
6D = [25, 35, 2]
7E = [50, 30, 5]
8
9per = [A, B, C, D, E]
10
11minPena = float('inf')
12minOrder = []
13for aaa in itertools.permutations(per,  5):
14    time = 0
15    pena = 0
16    for p in aaa:
17        time += p[0]
18        if p[1] < time:
19            pena += (time - p[1]) * p[2]
20    if minPena > pena:
21        minPena = pena
22        minOrder = aaa
23    print(pena, aaa)
24print(minPena, minOrder)