Multi-colony diploid immune algorithm (MCDIA) for better job-shop scheduling

Aim. Existing immune algorithms (IAs) for job-shop scheduling suffer, in our opinion, from two shortcomings: prematurity and stagnation. In order to suppress these two shortcomings, we propose MCDIA. The colonies hybridize some iterations through hybridization operators, but, after some time, the MCDIA can break the balance state of IA and enter higher balance state through exchanging available information carried by the excellent anti-bodies. Furthermore, the MCDIA distributes the most excellent anti-bodies to each colony through the pass excellence operator, helping to implement the parallel operation among the colonies and quicken evolution speed and suppress prematurity. To find the gene segments of optimal solution, we introduce the concept of diploidy to separate anti-body into implicit and explicit parts and introduce the explicit immunity operator and implicit-explicit reset operator to prolong the life-cycle of usable gene segments and to keep the diversity of the colonies as a whole. Finally we use three algorithms, including MCDIA, to simulate the typical job-shop scheduling benchmark problem LA03. The simulation results presented in Table 2 in the full paper show preliminarily that our MCDIA has the following two merits compared with the other two algorithms: the average windage probability of the optimal value is the smallest; the probability of obtaining globally optimal value is 70%, much higher than the 0% and 20% for the other two algorithms respectively.