基于DICA的存储受限流水车间调度

Flow Shop Scheduling with Limited Intermediate Storage Based on Discrete Imperialist Algorithm

针对缓冲区空间和时间同时受限的流水车间调度问题,以最小化完工时间为优化目标建立了数学模型,并提出了求解方法。由于中间存储策略的限制,相对于普通流水车间调度问题,约束条件更加苛刻,且随着调度问题规模的增大,求解难度成倍增长,但却更加具有实用性和研究意义。帝国竞争算法具有求解精度高、收敛速度快的特点,在帝国竞争算法的基本框架上,提出了一种改进的离散帝国竞争算法。针对存储受限的流水车间调度问题,采用随机键编码的方式初始化种群;同化过程采取交叉替换的方式,并控制一定的同化概率,削弱帝国的势力,防止算法过早收敛;引入历史最优解机制,记录殖民的历史最优位置;革命过程中引入变异算子,以增强搜索能力;采用正交试验方法确定算法参数。在经典算例的基础上加入缓冲区约束并进行仿真实验,实验结果表明,离散帝国竞争算法求解质量高,收敛速度快。

Aiming at the problem of the flow shop scheduling subject to limited buffer space and time, this paper proposes a mathematical model of minimizing the makespan and further gives a resolving method. Compared with the conventional flow shop scheduling, the limited intermediate storage policy makes the constraint condition of the considered optimization problem much harsh and makes the solving procedure more difficult with the increasing of schedule scale, which also makes the present research more significant in practice and theory. The imperialist competitive algorithm （ICA） has high precision and fast convergence, based on which a discrete imperialist competitive algorithm （DICA） is proposed in this paper to solve the scheduling problems with limited intermediate storage. The random key coding method is used to initialize the population. The assimilation process is undergone with cross-reconstruction policy, in which the probability of assimilation is controlled appropriately to weaken the power of the empire country so as to avoid the premature problem. At the same time, the historical optimal solution mechanism is introduced and the best position of each country is recorded. In the revolution process, the mutation strategy is introduced to enhance the search capability of DICA. Orthogonal experiment method is used to determine the algorithm parameters. The simulation results via a set of classic scheduling examples combined with intermediate constraints demonstrate the effectiveness of proposed DICA in this paper.