バックトラッキング サブセット ツリー テンプレートに基づいて最適なジョブ スケジューリングを解決する Python の詳細な例

この記事では、バックトラッキング手法のサブセット ツリー テンプレートに基づいて最適なジョブ スケジューリング問題を解決するための Python を主に紹介し、ジョブ スケジューリングの問題を簡単に説明し、例と組み合わせて、Python がバックトラッキング手法のサブセット ツリー テンプレートを使用して達成するための具体的な手順を示します。最適なジョブ スケジューリングの問題。関連する操作スキルについては、必要な友人が参照できます

この記事では、Python がバックトラッキング手法のサブセット ツリー テンプレートに基づいて最適なジョブ スケジューリング問題を解決する方法の例について説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

問題

n 個のジョブがあるとすると、各ジョブには 2 つのサブタスクがあり、2 台のマシンで完了する必要があります。各ジョブは、最初にマシン 1 で処理され、次にマシン 2 で処理される必要があります。

マシン 2 が各ジョブを完了するのにかかる時間の合計が最小化されるように、これらの n 個のタスクを完了するための最適なスケジュールを見つけるアルゴリズムを設計してみてください。

分析:

具体的な例を見てみましょう:

tji machine 1 machine 2
job 1 2 1
job 2 3 1
job 3 2 3

最適なスケジュール順序: 1 3 2

処理中時間: 18

これら 3 つのジョブの 6 つのスケジュール ソリューションは、1,2,3; 2,1,2; です。 ;

対応する完了時間はそれぞれ 19、18、20、21、19、19 です。最適なスケジュール計画は 1、3、2 であり、その完了時間の合計は 18 であることが簡単にわかります。

例として 1、2、3 を考えてみましょう:

マシン 1 でジョブ 1 を完了するまでの時間は 2、マシン 2 で完了するまでの時間は 3 です
マシン 1 でジョブ 2 を完了するまでの時間は 5 です、マシン 2 で完了する時間は 6
マシン 1 でジョブ 3 を完了する時間は 7、マシン 2 で完了する時間は 10
3+6+10 = 19

1、 3, 2

ジョブ 1 はマシン 1 で時間 2、マシン 2 で時間 3 で完了します。
ジョブ 3 はマシン 1 で時間 4、マシン 2 で時間 7 で完了します。
ジョブ 2 はマシン 1 で完了します。マシン 2 は 7、マシン 2 での完了時間は 8 です

3+7+8 = 18

デコード: (X1,X2,...,Xn)、Xi は順序を表しますi によって実行されたタスク番号。したがって、解決策はタスク番号を並べ替えることです。

解空間: {(X1,X2,...,Xn)| Xi は S に属します、i=1,2,...,n}、S={1,2,...,n}。したがって、解空間はタスク番号の完全な配置になります。

公平を期すためには、バックトラック方式のフルアレンジメントテンプレートを使用する必要があります。

ただし、前の 2 つの例を基礎として、ここではバックトラッキング手法のサブセット ツリー テンプレートが使用されます。

コード

'''
最佳作业调度问题
tji     机器1   机器2
作业1     2     1
作业2     3     1
作业3     2     3
'''
n = 3 # 作业数
# n个作业分别在两台机器需要的时间
t = [[2,1],
   [3,1],
   [2,3]]
x = [0]*n  # 一个解（n元数组，xi∈J）
X = []   # 一组解
best_x = [] # 最佳解（一个调度）
best_t = 0 # 机器2最小时间和
# 冲突检测
def conflict(k):
  global n, x, X, t, best_t
  # 部分解内的作业编号x[k]不能超过1
  if x[:k+1].count(x[k]) > 1:
    return True
  # 部分解的机器2执行各作业完成时间之和未有超过 best_t
  #total_t = sum([sum([y[0] for y in t][:i+1]) + t[i][1] for i in range(k+1)])
  j2_t = []
  s = 0
  for i in range(k+1):
    s += t[x[i]][0]
    j2_t.append(s + t[x[i]][1])
  total_t = sum(j2_t)
  if total_t > best_t > 0:
    return True
  return False # 无冲突
# 最佳作业调度问题
def dispatch(k): # 到达第k个元素
  global n, x, X, t, best_t, best_x
  if k == n: # 超出最尾的元素
    #print(x)
    #X.append(x[:]) # 保存（一个解）
    # 根据解x计算机器2执行各作业完成时间之和
    j2_t = []
    s = 0
    for i in range(n):
      s += t[x[i]][0]
      j2_t.append(s + t[x[i]][1])
    total_t = sum(j2_t)
    if best_t == 0 or total_t < best_t:
      best_t = total_t
      best_x = x[:]
  else:
    for i in range(n): # 遍历第k个元素的状态空间，机器编号0~n-1，其它的事情交给剪枝函数
      x[k] = i
      if not conflict(k): # 剪枝
        dispatch(k+1)
# 测试
dispatch(0)
print(best_x) # [0, 2, 1]
print(best_t) # 18

レンダリング

以上がバックトラッキング サブセット ツリー テンプレートに基づいて最適なジョブ スケジューリングを解決する Python の詳細な例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。