The aircraft industry requires heat treatment for most parts formed from metal sheets to meet quality specifications. The aircraft parts have different routing of heat treatment operations and process requirements. Operation scheduling at the heat treatment workstation is a complex problem due to the large number of available combinations of parts to be grouped based on similar characteristics, followed by allocating their operations to available facilities and determining a sequence to minimize total completion time. This paper proposed a variable neighborhood search (VNS) algorithm approach to solve heat treatment operation scheduling. Three neighborhood structures of the VNS were applied: swapping the order of part groups, changing machine allocation, and combining both. A full factorial experimental design is applied to find the best combination of VNS parameters. A numerical experiment shows that the VNS scheduling algorithm has an average difference of 4.63% in total production time with the analytical method.