A Shuffled Frog-Leaping Algorithm with Competition for Parallel Batch Processing Machines Scheduling in Fabric Dyeing Process

As a complicated optimization problem, parallel batch processing machines scheduling problem (PBPMSP) exists in many real-life manufacturing industries such as textiles and semiconductors. Machine eligibility means that at least one machine is not eligible for at least one job. PBPMSP and scheduling problems with machine eligibility are frequently considered; however, PBPMSP with machine eligibility is seldom explored. This study investigates PBPMSP with machine eligibility in fabric dyeing and presents a novel shuffled frog-leaping algorithm with competition (CSFLA) to minimize makespan. In CSFLA, the initial population is produced in a heuristic and random way, and the competitive search of memeplexes comprises two phases. Competition between any two memeplexes is done in the first phase, then iteration times are adjusted based on competition, and search strategies are adjusted adaptively based on the evolution quality of memeplexes in the second phase. An adaptive population shuffling is given. Computational experiments are conducted on 100 instances. The computational results showed that the new strategies of CSFLA are effective and that CSFLA has promising advantages in solving the considered PBPMSP.