Comparative Analysis of Variable Ordering Heuristics for Job-Shop Constraint Satisfaction Problem

Although a variety of variable ordering heuristics (VOH) have been proposed to improve the search efficiency for solving constraint satisfaction problems (CSP), little effort has been made to study the relationships between problem structure and algorithm performance. Focusing on the job-shop scheduling problem (JSSP) with non-relaxable time windows, a set of structure criteria are presented in the paper in order to quantify the problem features, including problem size, constraint tightness, connectivity of constraint graphs, deviation of variable constraint quantity and resource utilization. According to different criteria combinations, computational cases with practical backgrounds were designed. On the basis of empirical study, the correlation of VOH to the structure features of specific problem was identified, which can contribute to constructing more efficient search strategies.