Non-identical parallel machine batch scheduling of PCB drilling workshop via genetic algorithm with variable neighborhood search

The current research focuses on a practical scheduling problem originating from a printed circuit board (PCB) drilling workshop in China. Non-equivalent parallel drilling machines are placed in the workshop, and the different PCB orders may be processed in batches in order to improve production efficiency, if the special process requirements are satisfied. Sequence-dependent setup times are required during the drilling processes. It necessitates simultaneous consideration of spindle utilization rates and order batches across different machine types. Given the specificity and complexity of this problem, this study constructs a non-identical parallel machine batch scheduling model effectively tailored to the PCB drilling workshop environments, and designs a variable neighborhood search genetic algorithm (VNSGA) to solve this model. During the initial encoding phase, the algorithm generates and records order partitioning schemes. Subsequently, genetic operations mutate both the order partitioning and machine allocation schemes. The VNS mechanism effectively balances global and local search capabilities. Repeated experiments across diverse scenarios and multiple order-scale instances demonstrate the algorithm's stable and outstanding performance in batch scheduling for non-equivalent parallel machines in PCB drilling workshops. It achieves a significant reduction in makespan compared to its competitive heuristic algorithms, and significantly optimizes the workload balancing among parallel machines.