天天看點

5.3 回溯法解決最佳排程問題

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}。以下圖為例:

5.3 回溯法解決最佳排程問題

解空間如圖。在這個圖中能清晰地說明問題。

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
           

求每台機器的工作時間。

3.3 實驗結果

5.3 回溯法解決最佳排程問題

繼續閱讀