用GA算法解不同交货期窗口下的E/T调度问题

Single machine earliness and tardiness scheduling problem with distinct due window using genetic algorithms

针对准时生产制下提前 /延迟 ( E/ T)费用的生产排序与调度问题 ,对不同交货期窗口下 E/ T指标的单机调度问题进行了分析 ,给出了在给定加工顺序条件下求解最优加工时间的动态规划算法。在此基础上 ,应用 GA( genetic al-gorithms)算法实现了求解。为提高算法优化性能 ,针对问题本身特性 ,分别从关键参数的选取 ;交叉操作的动态控制 ;变异操作的优化 3方面提出了相应改进策略。最后利用计算机仿真对算法性能进行研究 ,并得到一些经验性结论。仿真结果表明 ,该算法在优化性能和时间性能上均能满足工程上的要求。

A single machine earliness and tardiness (E/T) scheduling problem with distinct due window is considered. An optimal timing algorithm is presented which decides the optimal starting time of each job in a given job sequence. Idle times are inserted between blocks of jobs. The algorithm provides near optimality for the solution using by Genetic Algorithms. The performance of the genetic algorithm is improved through selection of key parameters, dynamic control of crossover operators and improvement of mutation operators. The proposed genetic algorithm effectively schedules many stochastic test problems.