应用蚁群演算法于排程问题.pptVIP

* 單機台和多機台排程問題 報告:陳崇宇 * 單機台問題定義 在一個有多個工作需要在單部機器上完成處理的狀態下。 同一個工作會依照機器分成許多製令分別產生。製令:製造命令 不同的工作和工作的製令並無先後關係，製令分開處理。 * 單機台問題的限制 1.同一個製令只會生產一次。 2.不同的工作間沒有處理順序關係。 3.製令生產過程不允許中斷。 4.機器在同一時間內，只能處理一件製令。 5.同一工作的製令間沒有先後處理順序關係。 6.機台所能安置的成品容量空間不構放置下一批製令數量就必須換線。 * 單機台目的 目的求出單機台最短能完成所有工作的時間。 * 變數定義 i : 製令編號。 l : 加工順序。 n : 製令總數。 Di : 處理第i個製令所需時間。 W : 機器單次換線所花費時間。 Ail :第i個製令於l個順序加工時，是否須進 行換線之判定執，是則Ail =1，否則=0。 * 變數定義 Til :將第i個製令排程於第l個順序加工所花 費的時間。 Bil :製令i是否排程於第l個順序加工的判定 執，是則Bil =1，否則Bil =0。 Z :排程後總處理時間。 * 變數詳細說明 Til :將第i個製令排程於第l個順序加工所花 費的時間。 Ail:第i個製令於l個順序加工時，是否須進行換線之判定執，是則Ail =1，否則=0。 i製令如果在第l個順序超過機器的限制時間就必須換線處，所以本身製令處理時間(Di)加上換線所花費的時間，才是這製令的總花費時間。 * 變數詳細說明 Bil :製令i是否排程於第l個順序加工的判定 執，是則Bil =1，否則Bil =0。 所有製令i都必須被處理，且只能處理一次。 * 變數詳細說明 所有製令所花費的時間就是排程後總處理時間。 目標 求出最少的排程總時間。 * 步驟 1.設定所有製令的處理順序。 2.求出排程後的總時間Z，跳回步驟1。 3.多次排程後總時間未更動求出min(Z)。 * 多機台問題定義 在一個有多個工作需要在多部機器上完成處理的狀態下。 同一個工作會依照機器分成許多製令分別產生。製令:製造命令 不同的工作和工作的製令並無先後關係，製令分開處理。 * 多機台問題的限制 1.同一個製令只會生產一次。 2.不同的工作間沒有處理順序關係。 3.製令生產過程不允許中斷。 4.機器在同一時間內，只能處理一件製令。 5.同一工作的製令間沒有先後處理順序關係。 6.每台機器所能安置的成品容量也不同，如果成品安置空間不構就必須換線。 * 多機台目的 依照使用者設定的機台使用數量(m)，來求出最短完成所有工作的時間。 * 變數定義 i : 製令編號。 l : 加工順序。 k : 機器編號。 n : 製令總數。 Di : 處理第i個製令所需時間。 W : 機台單次換線所花費時間。 m : 機台使用數量。 uk : 安排在機台上的製令數。 * 變數定義 Akil :在K機台內第i個製令於l個順序加工時， 是否須進行換線之判定執，是則Ail =1， 否則=0。 Tkil :在K機台內將第i個製令排程於第l個順序 加工所花費的時間。 Bkil :在K機台內製令i是否排程於第l個順序加 工的判定執，是則Bil =1，否則Bil =0。 Z :排程後總處理時間。 * 變數詳細說明 n : 製令總數。 m : 機台使用數量。 k : 機器編號。 uk : 安排在機台上的製令數。 所有機台安排的製令數量加總等於總製令數。 * 變數詳細說明 Tkil:在K機台內將第i個製令排程於第l個順序加工所花費的時 間。 Di : 處理第i個製令所需時間。 W : 機台單次換線所花費時間。 k機台內i製令如果在第l個順序超過機器的限制時間就必須換線處，所以本身製令處理時間(Di)加上換線所花費的時間，才是這製令的總花費時間。 * 變數詳細說明 Vk :第k部完成排成製令的時間。 Tkil:在K機台內將第i個製令排程於第l個順序加工所花費的時間。 Bkil:在K機台內製令i是否排程於第l個順序加工的判定執，是則Bil =1，否則Bil =0。 機台排程時間為機台內所有安排的製令時間加總。 * 變數詳細說明 Z :排程後總處理時間。 排成後總處理時間為所有機台裡面最後完成所有製令的時間。 目標 求出最少的排程總時間。 * 演算法 1.設定機台使用數量m。 2.設定所有製令的處理順序。 3.依序將製令安排至機台。 4.依照目前所有機器排程時間決定下一排放機