結合優勢性質與基因遺傳演算法於具有整備時間之單機與非等效平行機台之研究

A Genetic Algorithm with Dominance Properties for Single and Unrelated Parallel Machine Scheduling with Setup Time Problems

熊詩敏(Shih-Min Hsiung)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/碩士(2007年)

https://doi.org/10.6838/YZU.2007.00021

摘要

近幾年來，隨著經濟、科技的快速發展與消費者需求的多變化，使得消費市場需求型態由早期的少樣多量生產模式，逐漸轉換成多樣少量的生產模式，其整備時間佔總生產時間比率越來越高，因此整備時間的考量將越來越重要，且對排程準確性的影響也將會越來越大。因此，本研究主要在探討順序相依整備時間（Sequence-dependent Setup）的條件下，考慮以下二種型態的排程問題：第一部份是探討具有相同交期，目標為最小化交期總偏差值( Tardiness& Earliness )的單機排程問題；第二部份則是考慮非等效平行機台的最小化總時程（Makespan）的問題。

本研究所推導的Dominance Property（DP），是透過數學推導的方式，瞭解工件排序上的前後關係，得到一個較佳的排序，但是其容易陷入局部最佳解，因此本研究加入全域搜尋的演算法，本研究採用基因遺傳演算法（Genetic Algorithms），與模擬退火演算法（Simulated Annealing），並將第一階段DP的結果當作是第二階段的初始解，成為為一種二階段的啟發式演算法；實驗結果發現，在單機及平行機台上在結合DP之後，GADP與SADP的求解效果均與單純的GA與SA有顯著差異，且求解品質也更穩定。另外，在平行機台第一階段DP的求解效果甚至超過單純GA及SA。DP亦可以與其他任何啟發式演算法做結合，且得到更好的求解效果。

關鍵字

順序相依整備時間 ； 優勢性質 ； 基因遺傳演算 ； 模擬退火演算法

並列摘要

With the changing of production types, taking setup time into consideration is getting more and more important for industrial schedulers. Therefore, in this research, we explore the single machine scheduling problem that all jobs have a common due date that has been predetermined using the median of the set of sequenced, the objective is to find an optimal sequence with minimizing the total absolute deviation（Tardiness& Earliness）and the unrelated parallel machine scheduling with minimizing makespan under Sequence-dependent Setup time.
Dominance Properties（DP） are developed according to the sequence swapping of two jobs and getting a new better sequence . Because DP trap into local optima easily, we combined dominance properties with global search algorithm, Genetic Algorithm and Simulated Annealing, became GADP and SADP. The hybrid algorithm is a two-stage procedure; the first phase result of DP is the initial solution of the second phase. We compared GADP and SADP with SGA and SA, the result shows that there is significant difference between them in single machine scheduling problems and Parallel Machine Scheduling Problems. In addition, DP outperforms GA and SA significantly in parallel machine Scheduling Problem. Therefore, DP is able to combine with meta-heuristic and get better solutions.

並列關鍵字

Sequence-dependent Setup ； Dominance Properties ； Genetic Algorithms ； simulated Annealing.

參考文獻

60. 陳啟嘉，「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」，碩士論文，元智大學，2006。

1. Allahverdi , A., J. N. D. Gupta and T. Aldowaisan “A review of scheduling research involving setup considerations” Omega, The International Journal of Management Science, 27, pp. 219-239 ,1999.

2. Al-Salem, A.“ Scheduling to minimize makespan on unrelated Parallel machines with sequence dependent setup times.” Engineering Journal of the University of Qatar, 17, pp.177–187 , 2004.

3. Azizoglu. M. and O. Kirka “ Scheduling jobs on unrelated parallel machines to minimize regular total cost functions.” IIE Transactions, 31, pp.153–159, 1999.

4. Balakrishnan, N., J. J. Kanet and S. V. Sridharan. “ Early tardy scheduling with sequence dependent setups on uniform parallel machines ” Computer & Operation Research 26 pp.127-141,1999.