A client/server-based parallel coevolutionary algorithm for parallel machines scheduling problem with penalties

A problem of n independent jobs with different ready times and due dates to be scheduled on m parallel machines which aims at minimizing the total tardiness penalty costs of all jobs is considered. The decomposition and combination characteristics of the problem are studied. Based on these two characteristics, a parallel coevolutionary algorithm (PCA) is proposed. The PCA is implemented in a client/server (C/S)-based parallel coevolutionary computation structure, in which the server is responsible for global evolution by task assignment and the client is responsible for local evolution by task ordering. According to this structure, a genetic algorithm and a virus evolutionary genetic algorithm are developed, which are executed on server and client, respectively. The simulated experiments are designed, the comparison results with adapted algorithms show that the proposed algorithm C/S-PCA has superior performances both in convergence speed and in searching optimality.