协同进化交叉熵算法求解浇次不固定的炼钢连铸调度问题

浇次不固定的炼钢连铸调度问题（Cast uncertain steelmaking continuous casting scheduling problem，CU_SCCSP）广泛存在于钢铁生产行业中。该问题对应炼铁、精炼和连铸三个连续生产阶段，其中炼铁和精炼阶段为带运输时间的混合流水线调度子问题，连铸阶段为带独立设置时间的复杂并行机调度子问题，且两个子问题相互耦合。针对该问题，建立优化目标为最小化最大完工时间和平均等待时间加权和的排序模型，并提出一种协同进化交叉熵算法（Co-evolution cross-entropy optimization algorithm，CCOA）进行求解。设计前后子问题两段式编码和双向解码的策略，并采用启发式规则和随机方式初始化种群，以确保初始解的质量和分散性。在算法全局搜索阶段，采用分别对应前后子问题的双概率分布协同学习和积累优质解信息，并在采样概率分布生成新个体时引入考虑子问题耦合的模糊关系矩阵对概率分布取值进行适当调整，以增强算法较快到达优质解区域的能力，同时设计种群分裂机制来提高算法的引导性并扩大搜索范围。为提高算法的局部搜索能力，对分裂后的双种群中个体执行基于interchange和insert邻域操作的协同搜索，进而对当前历史最优解执行结合SWAP邻域快速评价的变邻域搜索，可增加算法在解空间中多个优质区域的搜索深度。仿真试验和算法比较验证了所提算法的有效性。

Co-evolution Cross-entropy Optimization Algorithm for Cast Uncertain Steelmaking-continuous Casting Scheduling

The cast uncertain steelmaking continuous casting scheduling problem (CU_SCCSP) widely exists in the steel industry. This problem corresponds to three continuous production stages, i.e., ironmaking stage, refining stage and continuous casting stage. The ironmaking and refining stages can be modeled as a hybrid flow shop scheduling subproblem with transportation times, and the continuous casting stage can be regarded as a complex parallel machine scheduling subproblem with independent setting times. These two sub-problems are coupled with each other. To solve CU_SCCSP, a permutation-based model is established, and a co-evolution cross-entropy optimization algorithm (CCOA) is proposed to minimize the objective of weighted sum of the maximum completion time and the average waiting time. A two-stage encoding strategy and a bidirectional decoding strategy for the subproblems are designed，and a heuristic rule and a random method are adopted to initialize the population to ensure the quality and dispersion of the initial solutions. In the global search phase of CCOA, two probability matrices corresponding to the former and the latter subproblems are used to collaboratively learn and accumulate the information of high-quality solutions or individuals. Moreover, before generating new individuals by sampling the probability matrices, a fuzzy relation matrix considering the coupling between two subproblems is proposed to adjust the values in the probability matrices appropriately to enhance the ability of CCOA to reach the high-quality solution regions quickly. Meanwhile, a population splitting mechanism is designed to enhance CCOA's guiding ability and expand its search range. In order to improve the local search ability of CCOA, a cooperative search based on interchange neighborhood operation and insert neighborhood operation is executed on each individual in two splitting populations, and then a variable neighborhood search (VNS) method combined with the speedup evaluation of the swap neighborhood is performed on the current historical optimal solution, which can increase the search depth of the algorithm in multiple high-quality regions in solution space. Simulation experiments and algorithm comparisons verify the effectiveness of the proposed CCOA.