中文摘要：

针对实际工业生产中广泛存在的带调整时间的并行机调度这一类NP难问题，研究并提出了一种改进的克隆选择算法（HSMCSA）．为了提高算法的求解效率，特别是对大规模问题的优化性能，提出了一种基于单机排序的均匀插入分割点的编码方法；在此基础中进一步研究了基于单机调度最优解与随机解混合启发式初始化策略，有效提高了初始解性能；最后详细对比和分析了克隆选择算法中4种变异操作的优化性能，实现了基于改进的克隆选择算法的带调整时间的并行机调度问题的优化求解．仿真实验结果表明：所提出的改进克隆选择算法具有更好的优化性能；与遗传算法相比，求解性能提高了18．5％，与基本克隆选择算法相比提高了7．2％．

英文摘要：

An improved clonal selection algorithm （HSMCSA） is proposed for the parallel machine scheduling problem with setup time, which is a type of NPhard problems and widely spreads in the real industrial production. A single machine scheduling based encoding method with inserting the di viding point uniformly is proposed to improve the efficiency and performance of the algorithm, espe cially for the large scale problems. Then, the initialization strategy of combining the single machine scheduling based optimal solutions and random solutions generated by heuristic method is investigated so as to enhance the performance of the initial solutions. Furthermore, the optimization performance of four mutation operators in the clonal selection algorithm are compared and analyzed in details, and the HSMCSA is successfully applied to the parallel machine scheduling problem with setup time. The simulation results indicate that the proposed algorithm exhibits great performance. Compared with the genetic algorithm and the basic clonal selection algorithm, the performance of the solution has been improved by 18.5 % and 7.2 %, respectively.