學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
4 results
Search Results
Item 以多目標演化演算法求解動態電力調度之成本及汙染問題(2022) 柯炫任; Ko, Hsuan-Jen在科技發達的社會中，人類對電力的依賴日漸增加。由於目前綠色能源之發展仍在進行，火力發電仍為電力供給的主要方法。動態電力調度之成本及汙染問題為有限制的多目標連續型最佳化問題，給定若干個發電機組資訊和一天二十四小時的電力需求，需求取每小時中各機組的發電量配置。發電配置必須滿足每小時的電力需求，也必須符合各發電機組的負載範圍及調降安全範圍；目標則為同時最小化發電成本和空污排放量。綜合上述，動態電力調度之成本及汙染問題為一具挑戰性之最佳化問題，且有實務應用價值，是非常值得研究的問題。本論文提出多目標差分演化演算法以求解動態電力調度之成本及汙染問題，針對演算法中的合法性修復、環境選擇、計算資源分配及突變選擇四項重要機制進行探究。我們以六組公開測試模型檢驗上述四項機制對求解效能之影響，實驗結果顯示本論文所使用之機制均有良好成效。最後，本論文之方法和十五個既有方法相比，展現優秀的求解能力。Item 以強化突變機制之基因演算法求解多目標彈性零工式工廠排程問題(2013) 陳弘奇如何有效分配資源以及提高生產效率、降低生產成本，是製造業一直以來想要達到的目標，這就是為何十幾年來生產排程問題可以如此的熱門。排程問題大部分都屬於組合最佳化問題，零工式工廠排程問題（Job-shop Scheduling Problem, JSP）便是其一。由於此類問題的複雜度很高，通常難以求得最佳解。彈性零工式工廠排程問題（Flexible Job-shop Scheduling Problem, FJSP）則為零工式工廠排程問題的延伸，主要透過分配製程的作業機台（路由問題），以及變換製程在機台上的順序（排序問題）來最小化最大完工時間（makespan）、機台總工作量（total workload）和最大機台工作量（maximum workload）。 本論文所提出的演算法主體為基因演算法（Genetic Algorithm, GA），搭配交換關鍵製程以及重新插入關鍵製程來做突變，並且強化插入關鍵製程的方式。而為了求得在多個目標上的最佳化，本論文採用柏拉圖分級法（Pareto ranking）當作選擇機制，目的在於找到柏拉圖最佳解（Pareto optimal solutions）。 實驗的問題為 BR data 的十個測試問題。本論文提出的演算法在非凌越解（non-dominated solutions）個數較多的問題中能大幅度更新目前的已知非凌越解。Item 混合式基因演算法於多目標彈性零工式工廠排程問題之研究(2011) 林孝柔; Hsiao-Jou Lin生產排程主要是透過有效地資源分配來提高生產效率、降低生產成本，為了能達到既定的目標 (滿足交貨時間或縮短機台閒置時間)，生產排程至今仍是多目標最佳化領域中常見的研究題目。大部分的排程問題都是屬於組合最佳化問題並且難以求出最佳解，零工式工廠生產排程問題就是屬於此問題之一，多目標彈性零工式工廠排程問題 (Multi-objective Flexible Job-shop Scheduling Problem) 旨在如何分配適當的機台給每一零件的製程使用 (路由問題)以及如何將這些已選定機台的製程排序 (排程問題) 以最小化完工時間 (makespan)、最大機台工作量 (maximal machine workload)、總機台工作量 (total workload) 。 本論文提供基因演算法 (Genetic Algorithm, GA) 搭配禁忌搜尋法 (Tabu Search, TS) 去解多目標彈性零工式工廠生產排程問題，有別於文獻中合併函式 (aggregation function) 適應值 (fitness) 的算法，我們利用柏拉圖法 (Pareto) 計算適應值以求得柏拉圖最佳解 (Pareto front)。其中在禁忌搜尋法中加入變動鄰域尋優演算法 (Variable Neighborhood Descent, VND),從開始時間到完工時間的最長路徑 (critical path) 找到關鍵製程 (critical operations)，利用交換與插入關鍵製程改變最長路徑來縮短最小完工時間。 實驗問題包含Kacem data與BR data共十五個測試問題。本研究在Kacem data皆能透過一次的實驗就能找到過去所有文獻中提出的最佳解，而BR data則有五個測試問題可以更新文獻中的最佳解。Item 以MOEA/D結合適應性區域搜尋求解多目標定序流線型工廠排程問題(2017) 張祐騰; Chang, Yu-Teng本論文將MOEA/D應用於求解多目標定序流線型工廠排程問題（multi-objective permutation flowshop scheduling problem），已知多目標定序流線型工廠排程問題是一個 NP-hard 問題，無法確保在多項式時間內將該問題求得最佳解。在這個問題中有多個零件（job）需要依序送入機器（machine）中加工，而每個零件根據製程（operation）不同而有不同的加工時間（processing time）；所有零件皆加工完成的時間為最大完工時間（makespan），而每個零件的完工時間總和為總流程時間（total flow time），我們希望能同時最小化最大完工時間與總流程時間，但縮短最大完工時間可能使得總流程時間增加，反之亦然；然而，我們可以求出非凌越解（non-dominated solution），這些解在目標空間形成一條柏拉圖前緣（Pareto front），我們的目標是求解得到盡量靠近真實解，且分佈越完整的柏拉圖前緣。 過往文獻中，使用 MOEA/D 這種將目標空間（objective space）分解的方法並不多；本論文深入探討 MOEA/D 流程中各個操作對效能之影響；除此之外，我們使用區域搜尋強化解的品質，並探討不同搜尋方式對效能之影響。我們使用Taillard 測試問題集進行實驗分析，並與知名演算法比較，本論文提出的演算法在中、大型的問題具有較好的效果。