Abstract: Aiming at the simultaneous scheduling problem of scheduling jobs and automated guide vehicles (AGVs) in the flexible workshop system, consider building the objective function to minimize maximum processing machine duration, single AGV handling time, and total AGV handling time in the case of a finite number of AGVs and processing machines. Design an improved algorithm that combines NSGA-II (non-dominated sorting genetic algorithms) and clonal selection algorithm (CSA) to solve such problems. Firstly, the workpiece, the processing machine and the AGV are used for three-part coding. Secondly, the total score of non-dominated ranking and objective function value size sorting is introduced to stratify the population, so as to effectively retain excellent individuals. Thirdly, for the cloned population, different probabilities of variation are adopted for different levels of populations, and the genetic recombination of internal exchange and uniform cross-mixing exchange of chromosomes is carried out to effectively improve the diversity of the population and prevent it from falling into local optimum. Finally, three sets of comparative experiments verify that the algorithm has the advantages of short running time, high stability and good convergence when exploring the optimal solution.

Key words: NSGA-II, clonal selection algorithm, task scheduling, transportation scheduling, automated guide vehicle (AGV)

摘要： 针对在灵活车间系统中调度作业和自动引导车（automated guide vehicle，AGV）的同时调度问题，考虑在有限多个AGV和加工机台的情况下，以最小化最大完工时间、单个AGV搬运消耗时间及所有AGV搬运总消耗时间为目标函数，设计融合NSGA-II（non-dominated sorting genetic algorithms）和克隆选择（clonal selection algorithm，CSA）的改进算法INGCSA来解决此类问题。采用工件、加工机台和AGV三部分编码；引入非支配排序和目标函数值大小排序后总得分进行种群分层，从而有效地保留优秀个体；针对克隆后的种群，对不同等级的种群采取不同的变异概率，并对染色体进行内部交换与均匀交叉混合交换的基因重组，有效地提高了种群的多样性与防止陷入局部最优。通过三组对比实验，验证了该算法在探索最优解时，具有运行时间短、稳定性高和收敛性好等优点。

关键词: NSGA-II, 克隆选择算法, 任务调度, 运输调度, 自动引导车（AGV）