A two-stage hybrid flow shop scheduling problem with reentrant and limited waiting time constraints was presented based on block painting operations. The first stage contained several identical batching machines which were able to process multiple jobs simultaneously, and the second stage contained several identical discrete machines. Minimization of the makespan was used as the optimization objective to build a mathematical model. A hybrid quantumbehaved particle swarm optimization algorithm combined with Metropolis rule and variable neighborhood search was proposed. The heuristic decoding strategy was developed to generate the scheduling scheme. Application and numerical analysis indicated that the proposed algorithm was an effective solution to the problem of block painting scheduling.