역추적 하위 집합 트리 템플릿을 기반으로 최적의 작업 스케줄링을 해결하는 Python의 자세한 예

이 문서에서는 주로 역추적 방법 하위 집합 트리 템플릿을 기반으로 최적의 작업 예약 문제를 해결하기 위해 Python을 소개합니다. 작업 예약 문제를 간략하게 설명하고 이를 예제와 결합하여 Python이 역추적 방법 하위 집합 트리 템플릿을 사용하여 달성할 수 있는 특정 단계를 제공합니다. 최적의 작업 스케줄링 문제 관련 운영 기술이 필요한 친구는 이를 참조할 수 있습니다.

이 기사에서는 Python이 역추적 방법 하위 집합 트리 템플릿을 기반으로 최적의 작업 스케줄링 문제를 해결하는 방법을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

Problem

n개의 작업이 주어지면 각 작업에는 두 대의 컴퓨터에서 완료해야 하는 두 개의 하위 작업이 있습니다. 각 작업은 먼저 Machine 1에서 처리된 다음 Machine 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,3,1, 2입니다. ;

해당 완료 시간은 각각 19, 18, 20, 21, 19, 19입니다. 최적의 스케줄링 계획은 1,3,2이고 완료 시간의 합은 18임을 쉽게 알 수 있습니다.

1,2,3을 예로 들어보세요.

머신 1에서 작업 1을 완료하는 데 걸리는 시간은 2이고, 머신 2에서 완료하는 데 걸리는 시간은 3입니다.
머신 1에서 작업 2를 완료하는 데 걸리는 시간은 5입니다. , and on 머신 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}에 속합니다. 따라서 솔루션 공간은 작업 번호의 완전한 배열입니다.

공정하게 말하자면 역추적 방식의 전체 배열 템플릿을 사용해야 합니다.

그러나 이전 두 가지 예를 기반으로 여기서는 역추적 방법의 하위 집합 트리 템플릿이 사용됩니다.

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

위 내용은 역추적 하위 집합 트리 템플릿을 기반으로 최적의 작업 스케줄링을 해결하는 Python의 자세한 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!