A Hybrid Metaheuristic to Minimize Total Completion Time on Parallel Batch Machines with Unequal Capacities and Speeds

This paper investigates the intelligent scheduling of semiconductor burn-in tests on heterogeneous automated testing equipment, modeled as non-identical parallel batch processing machines with different capacities and processing speeds. Jobs are characterized by release times, sizes, and processing times, and the objective is to minimize the total completion time. A mixed-integer programming (MIP) formulation is first developed to mathematically describe the problem. To efficiently solve large-scale instances, an evolutionary ant colony optimization with problem-specific local search (EACOL) is proposed. In EACOL, each ant uses a chromosome for job–machine assignment, while pheromone-guided decoding constructs batches and their processing order. A tailored local search operator is then applied to refine the constructed solutions, and evolutionary operators, including crossover and mutation, are employed to further improve the population. Pheromone trails are updated using the best retained schedule, enabling cooperative search at both the machine and job levels and reducing the risk of premature convergence. Experiments in two processing environments compare EACOL with RKGA, SA, IG, and MEASL. EACOL obtains a lower mean total completion time than MEASL on all 200 test instances.