A multi-agent ant colony optimization algorithm for earliness/tardiness scheduling with different due window on non-uniform parallel machines

Earliness/tardiness job-shop scheduling problems, which play very important roles in the field of job-shop scheduling, are NP (non-polynomial) hard typically, and classical methods for solving them usually result in exponential computational complexities. On the other hand, most of former scholars paid more attention to earliness/tardiness problems with common due window on single machine. More generally, to solve the earliness/tardiness job-shop scheduling problems with distinct due window on Non-uniform machines, a novel algorithm named MAACO (multi-agent ant colony optimization), which is more efficient and effective than classical methods, is presented in this paper, and a detailed mathematical model for the problem above is proposed. The presented algorithm introduces competition-cooperation and self-study mechanism into behaviours of agent ants, which improves the convergence rate and optimization precision of ant colony optimization (ACO) greatly. Simulation experiments of the problem are made at different scales. The results show that MAACO is very efficient and effective in obtaining near-optimal solutions to the earliness/tardiness job-shop scheduling problems, especially when the scale of problems is very large.