1.實驗目的
回溯法解決最佳排程問題
2.實驗内容
2.1 問題描述
設有n個任務由k個可并行工作的機器來完成,完成任務i需要時間為ti。試設計一個算法找出完成這n個任務的最佳排程,使完成全部任務的時間最早。
2.2 問題分析
該算法可抽象為子集樹回溯算法,針對特定的任務數和機器數定義解空間,對于n個任務和k個機器,
解編碼:(X1,X2,。。。,Xn),Xi表示給任務i配置設定的機器編号;解空間:{(X1,X2,。。。,Xn)| Xi屬于S,i=1到n},S={1,2,。。。,k}。以下圖為例:
解空間如圖。在這個圖中能清晰地說明問題。
3叉樹表示機器數為3。深度為4,總共4層,表示任務數為4。
用3台機器去排程4個任務,把這棵樹深度周遊,最後選出最優值。
3.實驗過程及結果
3.1 資料輸入
Machine = 4
time = []
for i in range(100):
time.append(random.randint(1,50))
time.sort()
time.reverse()
total = [0,0,0,0]
假設有4台機器,随機生成100個任務,任務的時間範圍在0~50
3.2 實驗代碼
def main(time):
for i in time:
min_time = total[0]
k = 0
for j in range(1,4):
if min_time > total[j]:
k = j
min_time = total[j]
total[k] += i
print(total)
return 0
求每台機器的工作時間。