Bi-Variate Artificial Chromosomes with Genetic Algorithm for Single Machine Scheduling Problems with Sequence-Dependent Setup Times
學年 99
學期 2
發表日期 2011-06-05
作品名稱 Bi-Variate Artificial Chromosomes with Genetic Algorithm for Single Machine Scheduling Problems with Sequence-Dependent Setup Times
作品名稱(其他語言)
著者 Chen, S. H.; Chen, M. C.
作品所屬單位
出版者
會議名稱 2011 IEEE Congress of Evolutionary Computation (CEC)
會議地點 New Orleans, U.S.A.
摘要 Artificial chromosomes with genetic algorithm (ACGA) is one of the latest Estimation of Distribution Algorithms (EDAs). This algorithm has been used to solve different kinds of scheduling problems successfully. However, due to its proba bilistic model does not consider the variable interactions, ACGA may not perform well in some scheduling problems, particularly the sequence-dependent setup times are considered because a former job influences the processing time of next job. It is not sufficient that probabilistic model just captures the ordinal information from parental distribution. As a result, this paper proposes a bi-variate probabilistic model added into the ACGA. The new algorithm is named extended artificial chromosomes with genetic algorithm (eACGA) and it is used to solve single machine scheduling problem with sequence-dependent setup times in a common due-date environment. Some heuristics are also employed with eACGA. The results indicate that the average error ratio of eACGA is one-half of the ACGA. In addition, when eACGA works with other heuristics, the hybrid algorithm achieves the best solution quality when it is compared with other algorithms in literature. Thus, the proposed algorithms are effective for solving this scheduling problem with setup consideration.
關鍵字 ACGA;Bi-Variate EDAs;Scheduling Problems;Sequence-Dependent Setup Times;Common Due-Date
語言 en
收錄於
會議性質 國際
校內研討會地點
研討會時間 20110605~20110608
通訊作者
國別 USA
公開徵稿
出版型式
出處 Proceeding of Congress of Evolutionary Computation 2011, p.45-53
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/121480 )