Abstract: To consider the economic and environmental factors at the same time, this paper dealt with the multi-objective permutation flow shop scheduling problems (MOPFSP) which minimized make-span and total carbon emissions. MOPFSP was proved to be a NP-hard problem for more than two machines. A HCS algorithm was proposed to solve the problems. Firstly, a largest-order-value rule was utilized to transform HCSs individuals from real vectors to job permutations so that HCS might be used to perform search in MOPFSPs solution spaces. Secondly, an adapive factor of step size was designed to control the search scopes in the evolution phases. Thirdly, a multi-neighborhood local search was presented to exploit the excellent subregions obtained by HCSs global search. Due to the hybridization of CS-based global search and multi-neighborhood local search, MOPFSP may be solved efficiently. Simulations and comparisons verify the efficiency of HCS to solve MOPFSP.

Key words: multi-objective permutation flow shop, hybrid cuckoo search(HCS) algorithm, carbon efficiency, green dispatch

摘要： 为协同考虑经济因素和环境因素，求解了优化目标为最小化最长完工时间和碳排放总量的多目标置换流水线车间调度问题（MOPFSP）。提出了一种混合布谷鸟算法（HCS）求解2台机器以上的MOPFSP问题。采用LOV规则将HCS算法中的个体从实数向量转换成工件排序，使其可在MOPFSP的解空间中进行搜索；设计了一种自适应步长控制因子，用于控制算法进化阶段的搜索范围；提出一种多邻域局部搜索，用于对HCS算法全局搜索发现的优质解区域进行细致搜索。由于融合了基于布谷鸟算法的全局搜索和多邻域局部搜索，故HCS算法可有效求解MOPFSP。仿真实验和算法对比验证了HCS算法求解MOPFSP的有效性。

关键词: 多目标置换流水线, 混合布谷鸟算法, 低碳, 绿色调度