具有总能耗约束的柔性作业车间调度问题研究

针对具有总能耗约束的柔性作业车间调度问题（Flexible job shop scheduling problem，FJSP），提出一种基于帝国竞争算法（Imperialist competitive algorithm，ICA）和变邻域搜索（Variable neighborhood search，VNS）的双阶段算法，该算法在总能耗不超过给定阈值的条件下最小化Makespan和总延迟时间.由于能耗约束不是总能满足且阈值往往难以事先给定，为此，第一阶段，首先，将原问题转化为具有Makespan、总延迟时间和总能耗的三目标FJSP，然后，利用初始帝国构建和帝国竞争的新策略设计一种ICA对问题求解，并根据ICA的结果确定总能耗阈值；第二阶段，应用解的比较新策略、非劣解集更新方法和当前解周期性更新，构建VNS对原问题求解.计算实验和结果分析表明，两阶段算法对于所研究的问题搜索能力强.

Research on Flexible Job Shop Scheduling Problem With Total Energy Consumption Constraint

A two-phase algorithm based on imperialist competitive algorithm (ICA) and variable neighborhood search (VNS) is proposed for the flexible job shop scheduling problem (FJSP) with total energy consumption constraint. The goal is to minimize the makespan and total tardiness under the condition that total energy consumption does not exceed a given threshold. Energy consumption constraint is not always met and a threshold is difficult to be decided in advance, so in the first phase, the original problem is converted into FJSP with makespan, total tardiness and total energy consumption, and an ICA is used to solve the converted problem based on some new strategies for initial empires and imperialist competition. An energy consumption threshold is obtained in terms of the results of ICA. In the second phase, a VNS is presented for the original FJSP by using new methods for comparing solutions and updating the non-dominated set and renewing current solution periodically. Computational experiments are conducted and the result shows that the two-phase algorithm has strong search ability for the considered FJSP.