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.