二機開放工場具有工作連接性限制之排程演算法效率比較

Tunghai University Institutional Repository > 工學院 > 工業工程與經營資訊學系所 > 碩博士論文 > Item 310901/6475

Please use this identifier to cite or link to this item: http://140.128.103.80:8080/handle/310901/6475

Title:	二機開放工場具有工作連接性限制之排程演算法效率比較
Other Titles:	An Openshop Two Machine Problem with Blocking─A Comparison of Random Search Algorithm and Genetic Algorithm
Authors:	賴崇瑋 Chung-Wei Lai
Contributors:	姚銘忠;曾宗瑤 Yao, Ming - Jong;Tseng, Tsueng-Yao 東海大學工業工程與經營資訊學系
Keywords:	排程;最佳化;遺傳基因演算法;開放工場;工作連接性;不等候特性 Scheduling;optimize;Genetic Algorithms;Openshop Problem;Blocking;No waiting
Date:	2001
Issue Date:	2011-05-25T09:32:21Z (UTC)
Abstract:	在不同的生產系統中，因為製造機具或是物料特性，對於其生產排程具有不同的要求，如Blocking是本研究中排程問題所探討之特別現象。所謂Blocking現象是指工作一旦進入製造系統當中，在機器與機器之間不可以有閒置時間，即物料於走完其完整的途程中，不離開生產機具，而且在其完成途程的同時，也完成製程中所有工作。(Yao, et al., 2000) 本研究中所考慮的為二機開放工場且具有工作連接性限制現象的排程問題：假定工作在兩機台的處理時間均已給定，本研究的目標為將n個工作排入此二機開放工場排程中，求其總製程時間之極小化。而根據Graham., et al., (1979)所提出之排程問題標準化標記方法，我們將這個問題標記為O2\|Blocking\|Cmax問題。相關文獻中曾經指出，在工作連接性限制的現象下，用於二機開放工場的排程問題，其複雜度(Complexity)為NP-hard，而本研究中使用了兩個啟發式演算法，利用MATLAB程式實際求解並測試O2\|Blocking\|Cmax問題，期望在兼顧解答品質與求解時間的雙重考慮之下，找出適合本研究問題的演算法，並建議決策者演算法中適用參數的設定，以期快速、有效針對此問題提供一個令決策者滿意的答案。本研究中所探討第一種演算法，隨機搜尋演算法(Random Search Algorithm; RSA)是根據Yao, et al.(2000)所提出；第二種演算法是眾多文獻中均證明對於組合最佳化問題有相當優異求解能力之基因演算法(Genetic Algorithm)，本研究之主要貢獻除了實作程式外針對RSA參數部分進行敏感度分析。並且比較兩個演算法的解答品質(Solution Quality)與求解時間(Run-time)，提供決策者在不同決策環境下設定RSA演算法參數之法則。 In this paper, considering a two-machine scheduling problem in an openshop with blocking jobs. We are given the processing times of n blocking jobs on both machines, and the objective is to minimize the makespan. Symbolically, we are dealing with the problem O2\|Blocking\|Cmax. Here tests two algorithms “Random Search Algorithm (RSA)” and “Genetic Algorithm (GA)” respectively. The results of RSA gave two parameters in adjust to algorithm,Υandβ. Decision table is also suggested in the thesis’ document. The result is that the performance of RSA is more efficiently than GA under these setting proposed in the paper to this problem. The results from our numerical experiments suggest that one should use LOX (Linear Order Crossover) and PBM (Position-Based Mutation) as the genetic operators if one would like use the genetic algorithm (GA) to solve the O2\|Blocking\|Cmax problem. And, we state useful guidelines for parameter settings in GA, for instance, population size, crossover rate, mutation rate and number of generations, etc. From the 600 random examples, we also observe that the number of jobs and the variance of the processing time for the jobs significantly affect the performance of the GA. Indeed, our study provides valuable decision support information for the decision makers who uses the GA to improve the solution quality in solving the O2\|Blocking\|Cmax problem.
Appears in Collections:	[工業工程與經營資訊學系所] 碩博士論文

Files in This Item:

File	Size	Format
089THU00030024-001.pdf	451Kb	Adobe PDF	895	View/Open

Loading...