A Hybrid Backtracking Search Algorithm for Permutation Flow-Shop Scheduling Problem Minimizing Makespan and Energy Consumption

With the advent of sustainable manufacturing, energy consumption becomes an essential consideration in the scheduling problem. However, traditional permutation flow-shop scheduling problem (PFSP) always only considers the production efficiency as its objective. In this paper, a hybrid backtracking search (HBSA) is proposed to minimize both the makespan and energy consumption for PFSP. In HBSA, the simulated annealing (SA) is hybrid with original backtracking search to update the population and then a local search algorithm is applied. Considering the effects of different operators on BSA, we analyze the effectiveness of initialization, crossover, and mutation and use the efficient strategy to improve its performance. Finally, the proposed HBSA is tested on the several benchmark problems to evaluate its performance, and the results are compared with genetic algorithm and branch and bound algorithm. The results validate its effective.