Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (27): 78-80.

• 学术探讨 • Previous Articles     Next Articles

Shortest idle time evolution algorithm for Job-shop scheduling

SU Zi-lin   

  1. School of Traffic,Ludong University,Yantai,Shandong 264025,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-09-21 Published:2007-09-21
  • Contact: SU Zi-lin

最小化空闲时间的Job-shop调度进化算法

苏子林   

  1. 鲁东大学 交通学院,山东 烟台 264025
  • 通讯作者: 苏子林

Abstract: In order to study job-shop scheduling problem,analyze scheduling result and scheduling procedure,and think that the scheduling process of classical job-shop scheduling model actually is reducing and minimizing idle time’s combination optimization process,different idle time has different influence to scheduling result.Put forward two-process procedure for minimizing idle time and process order rules for different idle time.Design the shortest idle time initial population generating procedure,recombination operator and mutation operator.Classic scheduling benchmark problem contrast and test shows:the shortest idle time analysis result is right;the shortest idle time procedures are efficient and credible;the shortest idle time evolution algorithm reduces search space,greatly improves search efficiency,efficiently avoids premature convergence problem,is stable and credible.

Key words: production scheduling, shortest idle time, evolution algorithm, evolution computing, Job-shop scheduling problem

摘要: 为了研究Job-shop调度问题,分析了调度结果和调度过程,认为传统Job-shop调度模型的调度过程,实质是减少并减小空闲时间的组合优化过程,而且不同空闲时间对调度结果的影响程度不同。据此提出了最小化空闲时间的两个处理过程和不同空闲时间的处理顺序规则;并设计了进化算法中最小化空闲时间的初始种群生成过程、重组算子和变异算子。经典的调度基准问题对比测试表明最小化空闲时间的分析结论是正确的;最小化空闲时间过程高效可靠;最小化空闲时间的进化算法缩小了算法的搜索空间,大大提高了搜索效率,有效避免了早熟收敛现象,稳定可靠。

关键词: 生产调度, 最小化空闲时间, 进化算法, 进化计算, Job-shop调度问题