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.

Authors

Institutions

Publication Details

Journal
Mathematics
Published
2026-11-13
DOI
https://doi.org/10.3390/math14224167
Primary Topic
Scheduling and Optimization Algorithms
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

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

Han Zhang, Jing Liu, Zhaohong Jia, Shuling Xu et al.
Mathematics
Scheduling and Optimization Algorithms
article

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

Han Zhang, Jing Liu, Zhaohong Jia, Shuling Xu, Yan Wang
article en

Abstract

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.

MathematicsVol. 14(22)
Jiangnan University (CN), Fuyang Normal University (CN), Anhui University (CN), Hefei University of Technology (CN), Anhui Normal University (CN), Anhui Polytechnic University (CN)
National Natural Science Foundation of China, Fuyang Normal University, Natural Science Foundation of Anhui Province
Scheduling and Optimization Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon