A competitive evolution strategy memetic algorithm for unrelated parallel machine scheduling to minimize total weighted tardiness and flow time

• Main Authors: Chiuh-Cheng Chyu, Wei-Shung Chang
• Format: Conference Proceeding
• Language: English
• Subjects: Algorithm design and analysis; Decoding; Evolutionary computation; Job shop scheduling; memetic algorithms; Memetics; Multi-objective optimization; Parallel machines; unrelated parallel machine scheduling
• DOI: 10.1109/ICCIE.2010.5668388

This research proposes a competitive evolution strategy memetic algorithm (CESMA) to solve unrelated parallel machines scheduling problems with two minimization objectives subject to job sequence- and machine-dependent setup times. A memetic operation is regarded as a genetic operation following a local search-weighted bipartite matching algorithm (WBM). The competitive evolution strategy maintains one generational population (GP) and two external archives at each generation, one preserving efficient solutions and the other preserving inefficient solutions. At each generation, two procedures, EAMA (efficient archive memetic algorithm) and IAMA (inefficient archive memetic algorithm), are applied to compete for producing the next generation offspring. The fraction p of memetic operations assigned to EAMA varies at each generation and depends on the competition results of the last generation. An experiment is conducted to compare the performance of the CESMA against two well-known evolutionary algorithms (NSGA II and SPEA2) with WBM. The effects of incorporating the WBM into these algorithms are also investigated. In the experimental study, three instances of different problem parameters were generated using a method in the literature. The experimental results show that the CESMA excels the others in terms of several proximity measures.