Abstract: To solve the flexible job shop scheduling problem (FJSP) with total energy consumption constraints and the objective of total tardiness,the problem was transformed into the bi-objective FJSP with objectives of total energy consumption and total tardiness to effectively deal with energy consumption constraints,and then a novel shuffled frog leaping algorithm was proposed to directly optimize the transformed FJSP. Some new methods were used to improve the solution qualities,which were the new strategies of memeplex construction and memeplex search,and the reinforced search of the best solution in memeplex. The computational experiments and the result analyses show that the novel algorithm has a strong search ability to solve the considered problems.

Key words: flexible job shop scheduling problem(FJSP), frog-leaping algorithm, total energy consumption constraint, memeplex

摘要： 针对具有总能耗约束且以总延迟时间为目标的柔性作业车间调度问题(job shop scheduling problem,FJSP)，首先将该问题转化为具有总能耗和总延迟时间的两目标问题，从而有效地处理能耗约束，然后提出了一种新型蛙跳算法直接优化转化后的两目标FJSP，该算法利用模因组构建和模因组搜索的新策略以及模因组内最好解的强化搜索以提高求解质量。计算实验和分析结果表明，新型蛙跳算法对所研究的FJSP具有较强的搜索能力和优势。

关键词: 柔性作业车间, 蛙跳算法, 总能耗约束, 模因组