基因演算法於單機交期絕對偏差及整備成本最小化排程問題之應用

Single Machine Scheduling Problem Subject to Minimization of Total Absolute Deviation and Setup Cost by Genetic Algorithm

趙文涼(Chao Wei-Liang)

指導教授 ： 張百棧

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

摘要

無資料

關鍵字

順序相依整備時間 ； 基因演算法 ； 變動突變率 ； 交期絕對偏差

並列摘要

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 explores the single machine scheduling problem with minimizing the total absolute deviation and setup cost where setup times are sequence dependent. Genetic algorithm is applied to search the optimal or near-optimal solutions in this research owing to its outstanding parallel searching capability. Moreover, through experimental design and statistical analysis, genetic algorithm is verified to receive comparative improvement.
Besides the above-mentioned results, this research investigates the optimal designs of parameters used in the genetic algorithm. We discuss the effect of number of chromosomes per population, crossover rate, mutation rate, number of generations and propose the difference between variable mutation rate and fixed mutation rate. Algorithm with variable mutation rate results in superior solutions, but it is difficult to convergent state. On the other hand, the convergence of fixed mutation rate is superior to variable mutation rate, and the solution quality is more robust than variable mutation rate.

並列關鍵字

Sequence Dependent Setup Times. ； Genetic Algorithm. ； Variable Mutation Rate. ； Absolute Deviation.

參考文獻

【1】Adamopoulos G.I. and C.P. Pappis, “ Scheduling Jobs with Different, Job-dependent Earliness and Tardiness Penalties Using the SLK Method, “ European Journal of Operational Research, 88, pp.336-344, 1996.

【2】Ali Allahverdi, et al., “ A Review of Scheduling Research Involving Setup Consideration, “ OMEGA, 27, pp.219-239, 1999.

【3】Asano M. and H. Ohta, “ Single Machine Scheduling Using Dominance Relation to Minimize Earliness Subject to Ready and Due Times, “ International Journal of Production Economics, 44, pp.35-43, 1996.

【4】Barnes J.W. and L.K. Vanston, “ Scheduling Jobs with Linear Delay Penalties and Sequence Dependent Setup Costs, “ Operations Research, 29, pp.146-160, 1981.

【5】Bianco L. et al., “ Scheduling Tasks with Sequence-dependent Processing Times, “ Naval Research Logistics Quarterly, 35, pp.177-184, 1988.