Exemple détaillé de Python résolvant la planification optimale des tâches basée sur un modèle d'arborescence de sous-ensemble de retour en arrière

Cet article présente principalement Python pour résoudre le problème de planification optimale des tâches basé sur le modèle d'arborescence de sous-ensembles de la méthode de backtracking. Il explique brièvement le problème de planification des tâches et le combine avec des exemples pour donner la solution de Python au problème de planification optimale des tâches en utilisant la méthode de backtracking. modèle d'arborescence de sous-ensembles. Pour connaître les étapes spécifiques et les compétences opérationnelles associées, les amis dans le besoin peuvent se référer à

Cet article décrit un exemple de la façon dont Python résout le problème de planification optimale des tâches basé sur le modèle d'arborescence de sous-ensembles de méthode de retour en arrière. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Problème

Étant donné n emplois, chaque travail a deux sous-tâches dont il a besoin à effectuer respectivement sur deux machines. Chaque tâche doit être traitée d'abord par la machine 1, puis par la machine 2.

Essayez de concevoir un algorithme pour trouver le meilleur calendrier pour accomplir ces n tâches, afin que la somme du temps nécessaire à la machine 2 pour terminer chaque tâche puisse être minimisée.

Analyse :

Regardez un exemple spécifique :

tji Machine 1 Machine 2
Job 1 2 1
Tâche 2 3 1
Tâche 3 2 3

Ordre de planification optimal : 1 3 2

Délai de traitement : 18

6 de ces 3 tâches Le possible les solutions de planification sont 1,2,3 ; 1,3,2 ; 2,3,1 ; 3,2,1 ; 

Prenons 1, 2, 3 comme exemple :

Le temps d'achèvement du travail 1 sur la machine 1 est de 2, et le temps d'achèvement sur la machine 2 est de 3

Le travail 2 est terminé en temps 5 sur la machine 1 et 6 sur la machine 2
Le travail 3 est terminé en temps 7 sur la machine 1 et 10 sur la machine 2

3+6+10 = 19

1, 3, 2

Le temps d'achèvement du travail 1 sur la machine 1 est de 2, et sur la machine 2, le temps d'achèvement du travail 3 est de 3 sur la machine 1 et le temps d'achèvement du travail 2 est 7.

Le temps d'achèvement du travail 2 est 7 et il est terminé sur la machine 2. Le temps est 8

3+7+8 = 18

Décodage : (X1,X2,..., Xn), Xi représente le numéro de tâche exécutée dans la séquence i. Une solution est donc une permutation des numéros de tâches.

Espace solution : {(X1,X2,...,Xn)| Xi appartient à S, i=1,2,...,n}, S={1,2,... , n}. Par conséquent, l’espace des solutions est l’arrangement complet des numéros de tâches.

Pour être juste, nous devrions utiliser le modèle d'arrangement complet de la méthode de backtracking.

Cependant, en prenant comme base les deux exemples précédents, le modèle d'arborescence de sous-ensembles de la méthode de backtracking est utilisé ici.

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

Rendu

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!