國立虎尾科技大學 |

Language: English

Back

於流程式生產排程以基因演算法將總完工時間最小化之研究 = A Study...

Po-Chieng Hu

於流程式生產排程以基因演算法將總完工時間最小化之研究 = A Study of Genetic Algorithms for Flowshop Scheduling to Minimize Makespan

Record Type:	Language materials, printed : monographic
Paralel Title:	A Study of Genetic Algorithms for Flowshop Scheduling to Minimize Makespan
Author:	李正羿,
Secondary Intellectual Responsibility:	胡伯潛,
Secondary Intellectual Responsibility:	國立虎尾科技大學
Place of Publication:	[雲林縣]
Published:	國立虎尾科技大學;
Year of Publication:	民96[2007]
Edition:	初版
Description:	78面圖,表 : 30公分;
Subject:	互熵法
Subject:	Cross Entropy Method
Online resource:	http://140.130.12.251/ETD-db/ETD-search-c/view_etd?URN=etd-0625107-161639
Summary:	排程(Scheduling)被廣泛地應用在各個領域，如製造、生產管理、資訊工程等等。一個好的排程可以節省時間、降低成本且滿足顧客的要求，而流程式生產排程(Flow-Shop Scheduling)問題則是排程中常見於現實生活環境的一種排程問題。對於流程式生產而言，當我們對所有的工作進行排序時，會有n!個可行解。這樣的問題為一非多項式時間可解問題(NP-complete)，當工作數目和機器數目增大時，求解的複雜度變的相當高，因此要在有限時間內找到一個最佳解幾乎是不可能的，故有許多學者以啟發式演算法來求得近似解。近年來，啟發式演算法已經成為求解最佳化問題中之非多項式時間可解問題的主流。在本研究中，我們應用基因演算法（Genetic Algorithms, GA）來求解最佳化之流程式生產排程的問題，並且以類似粒子群最佳化演算法(Similar Particle Swarm Optimization Algorithms, SPSOA)與互熵法(Cross Entropy Method, CE)所求得之總完工時間(Makespan)做比較。研究結果發現，本研究所提出之演算法，在求解流程式生產排程問題時，相較於其他啟發式演算法，能夠尋找到較好的最佳近似解，因此可以證明基因演算法具有不錯之求解效能。 Scheduling is widely used in many fields, like information engineering, manufacture, production management and so on. A good scheduling can save time and reduce cost without decreasing the satisfaction of customers. The “flow-shop scheduling” is the most common problem in the daily life. For this specific problem, there will be n! feasible solutions when we sequence all of the jobs by flow-shop scheduling problems, and this will become a NP-complete problems in mathematics. In other words, the complexity of finding the solutions will be increased with the number of the elements, and it will almost be impossible to find the optimal solution in a short time. Recently, the heuristics algorithms have become the most popular ones to find the optimal solutions of the NP-complete problems, and many literatures in the area had been published. In this paper we application the genetic algorithms (GA) to find the optimal solutions of the flow-shop scheduling problems and shows the comparisons of the results of makespan which derived from the GA method and similar particle swarm optimization algorithms (SPSOA) and cross-entropy method (CE).It has been found that the proposed algorithm, genetic algorithms, is better than other heuristics ones when finding the optimal approximate solutions of the flow-shop scheduling problems.

於流程式生產排程以基因演算法將總完工時間最小化之研究 = A Study of Genetic Algorithms for Flowshop Scheduling to Minimize Makespan
李, 正羿

於流程式生產排程以基因演算法將總完工時間最小化之研究 = A Study of Genetic Algorithms for Flowshop Scheduling to Minimize Makespan / 李正羿撰 - 初版. - [雲林縣] : 國立虎尾科技大學, 民96[2007]. - 78面 ; 圖,表 ; 30公分.
互熵法Cross Entropy Method

胡, 伯潛

於流程式生產排程以基因演算法將總完工時間最小化之研究 = A Study of Genetic Algorithms for Flowshop Scheduling to Minimize Makespan
LDR:03854nam0 2200253 450 001 540264
010 0 $b 平裝
100 $a 20090417h akaa0chia50020302ba
101 0 $a chi
102 $a cw
105 $a ak am 000yy
200 1 $a 於流程式生產排程以基因演算法將總完工時間最小化之研究 $d A Study of Genetic Algorithms for Flowshop Scheduling to Minimize Makespan $f 李正羿撰
205 $a 初版
210 $a [雲林縣] $d 民96[2007] $c 國立虎尾科技大學
215 0 $a 78面 $c 圖,表 $d 30公分
314 $a 指導教授：胡伯潛
328 $a 碩士論文--國立虎尾科技大學工業工程與管理究所
330 $a 排程(Scheduling)被廣泛地應用在各個領域，如製造、生產管理、資訊工程等等。一個好的排程可以節省時間、降低成本且滿足顧客的要求，而流程式生產排程(Flow-Shop Scheduling)問題則是排程中常見於現實生活環境的一種排程問題。對於流程式生產而言，當我們對所有的工作進行排序時，會有n!個可行解。這樣的問題為一非多項式時間可解問題(NP-complete)，當工作數目和機器數目增大時，求解的複雜度變的相當高，因此要在有限時間內找到一個最佳解幾乎是不可能的，故有許多學者以啟發式演算法來求得近似解。近年來，啟發式演算法已經成為求解最佳化問題中之非多項式時間可解問題的主流。在本研究中，我們應用基因演算法（Genetic Algorithms, GA）來求解最佳化之流程式生產排程的問題，並且以類似粒子群最佳化演算法(Similar Particle Swarm Optimization Algorithms, SPSOA)與互熵法(Cross Entropy Method, CE)所求得之總完工時間(Makespan)做比較。研究結果發現，本研究所提出之演算法，在求解流程式生產排程問題時，相較於其他啟發式演算法，能夠尋找到較好的最佳近似解，因此可以證明基因演算法具有不錯之求解效能。 Scheduling is widely used in many fields, like information engineering, manufacture, production management and so on. A good scheduling can save time and reduce cost without decreasing the satisfaction of customers. The “flow-shop scheduling” is the most common problem in the daily life. For this specific problem, there will be n! feasible solutions when we sequence all of the jobs by flow-shop scheduling problems, and this will become a NP-complete problems in mathematics. In other words, the complexity of finding the solutions will be increased with the number of the elements, and it will almost be impossible to find the optimal solution in a short time. Recently, the heuristics algorithms have become the most popular ones to find the optimal solutions of the NP-complete problems, and many literatures in the area had been published. In this paper we application the genetic algorithms (GA) to find the optimal solutions of the flow-shop scheduling problems and shows the comparisons of the results of makespan which derived from the GA method and similar particle swarm optimization algorithms (SPSOA) and cross-entropy method (CE).It has been found that the proposed algorithm, genetic algorithms, is better than other heuristics ones when finding the optimal approximate solutions of the flow-shop scheduling problems.
510 1 $a A Study of Genetic Algorithms for Flowshop Scheduling to Minimize Makespan
610 0 $a 互熵法 $a 基因演算法 $a 流程式生產排程 $a 總完工時間 $a 類似粒子群最佳化演算法
610 1 $a Cross Entropy Method $a Flow-Shop Scheduling $a Genetic Algorithms $a Makespan $a Similar Particle SwarmOptimization Algorithms
681 $a 008.169M $b 4011
700 $a 李 $b 正羿 $3 523745
702 $a 胡 $b 伯潛 $3 472880
712 $a 國立虎尾科技大學 $b 工業工程與管理究所 $3 523742
770 $a Cheng-Yi Li $3 586627
772 $a Po-Chieng Hu $3 586628
801 0 $a cw $b 虎尾科技大學 $c 20071207 $g CCR
801 2 $a cw $b 虎尾科技大學 $c 20090417 $g CCR
856 7 $u http://140.130.12.251/ETD-db/ETD-search-c/view_etd?URN=etd-0625107-161639