Abstract: To decrease makespan and walking time of one worker job shop considering learning effect,one worker one-operation-job and multi-machine job shop scheduling model with sum-of-processing-time based learning effect was proposed.Multi-objective Greedy algorithm based on Learning effect (MOGL) was presented.Combined fast elitist Non-dominated Sorting Genetic Algorithm (NSGA-Ⅱ) with local search based on greedy algorithm,Iterated Multi-objective Genetic Algorithm (IMOGA) was proposed,and the initial solutions based on MOGL was designed.Numerical experiments were design to evaluate the performance of IMOGA,and compared IMOGA with traditional algorithms by Hypervolume indicator.The experimental results showed that IMOGA could solve the problem effectively,revising its initial solutions and local search based on greedy algorithm can improve performance of NSGA-Ⅱ effectively.

Key words: fast elitist non-dominated sorting genetic algorithm, job shop scheduling, greedy algorithm, multi-objective optimization, walking time, makespan

摘要： 为减少受学习效应影响的单人作业车间的最大完工时间和工人行走时间,建立了考虑依赖加工时间和的学习效应的单人单工序多机车间调度模型,提出考虑学习效应的多目标贪婪算法(MOGL),融合了带精英策略的非支配排序遗传算法(NSGA-Ⅱ)与基于贪婪的邻域搜索,构造了迭代多目标遗传算法(IMOGA),并基于MOGL设计了初始解集。设计实验评估了IMOGA的性能,使用Hypervolume指标比较了IMOGA与传统算法。结果表明,IMOGA可以有效求解该问题,对初始解集的改进和基于贪婪的邻域搜索可以有效提高NSGA-Ⅱ的性能。

关键词: 带精英策略的非支配排序遗传算法, 车间调度, 贪婪算法, 多目标优化, 行走时间, 最大完工时间