Detailliertes Beispiel dafür, wie Python eine optimale Jobplanung basierend auf einer Backtracking-Teilmengenbaumvorlage löst

In diesem Artikel wird hauptsächlich Python zur Lösung des optimalen Jobplanungsproblems basierend auf der Teilmengenbaumvorlage der Backtracking-Methode vorgestellt. Er erläutert kurz das Jobplanungsproblem und kombiniert es mit Beispielen, um Pythons Lösung für das optimale Jobplanungsproblem mithilfe der Backtracking-Methode bereitzustellen Für spezifische Schritte und zugehörige Bedienkenntnisse können sich Freunde mit Bedarf auf

beziehen. Dieser Artikel beschreibt ein Beispiel dafür, wie Python das optimale Jobplanungsproblem basierend auf der Teilmengenbaumvorlage der Backtracking-Methode löst. Teilen Sie es wie folgt als Referenz mit allen:

Problem

Bei n Jobs hat jeder Job zwei Unteraufgaben. Er muss erledigt werden jeweils auf zwei Maschinen. Jeder Auftrag muss zuerst von Maschine 1 und dann von Maschine 2 bearbeitet werden.

Versuchen Sie, einen Algorithmus zu entwerfen, um den besten Zeitplan für die Erledigung dieser n Aufgaben zu finden, sodass die Summe der Zeit, die Maschine 2 für die Erledigung jeder Aufgabe benötigt, minimiert werden kann.

Analyse:

Sehen Sie sich ein konkretes Beispiel an:

tji Maschine 1 Maschine 2
Auftrag 1 2 1
Auftrag 2 3 1
Auftrag 3 2 3

Optimale Planungsreihenfolge: 1 3 2

Bearbeitungszeit: 18

6 dieser 3 Aufträge Das Mögliche Planungslösungen sind 1,2,3; 2,3,1; 3,2,1; Die Zeiten sind 19, 18, 20, 21, 19 und 19. Es ist leicht zu erkennen, dass der optimale Terminplan 1,3,2 ist und die Summe seiner Abschlusszeiten 18 beträgt.

Nehmen Sie 1, 2, 3 als Beispiel:

Die Abschlusszeit von Job 1 auf Maschine 1 beträgt 2 und die Abschlusszeit auf Maschine 2 beträgt 3

Auftrag 2 wird in Zeit 5 auf Maschine 1 und 6 in Maschine 2 erledigt

Auftrag 3 wird in Zeit 7 auf Maschine 1 und 10 in Maschine 2 erledigt

3+6+10 = 19

1, 3, 2

Die Fertigstellungszeit von Job 1 auf Maschine 1 beträgt 2, und auf Maschine 2 beträgt die Fertigstellungszeit auf Maschine 3 3

Die Zeit zum Abschließen von Job 3 beträgt 4 auf Maschine 1 und die Zeit zum Abschließen auf Maschine 2 beträgt 7

Die Zeit zum Abschließen von Job 2 beträgt 7 auf Maschine 1 und wird auf Maschine 2 abgeschlossen. Die Zeit beträgt 8

3+7+8 = 18

Dekodierung: (X1,X2,..., Xn), Xi repräsentiert die Nummer der nacheinander ausgeführten Aufgabe i. Daher ist eine Lösung eine Permutation von Aufgabennummern.

Lösungsraum: {(X1,X2,...,Xn)|. Xi gehört zu S, i=1,2,...,n}, S={1,2,... , N}. Daher ist der Lösungsraum die vollständige Anordnung der Aufgabennummern.

Um fair zu sein, sollten wir die vollständige Arrangement-Vorlage der Backtracking-Methode verwenden.

Auf der Grundlage der beiden vorherigen Beispiele wird hier jedoch die Subset-Tree-Vorlage der Backtracking-Methode verwendet.

Code

'''
最佳作业调度问题
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

Rendering

Das obige ist der detaillierte Inhalt vonDetailliertes Beispiel dafür, wie Python eine optimale Jobplanung basierend auf einer Backtracking-Teilmengenbaumvorlage löst. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!