Analysis of the similarities and differences of job-based scheduling problems

摘要

Job-based scheduling problems as one type of combinational optimization problem have relevance in several aspects. However, the current studies on these scheduling problems are isolated and lack mutual references and general analysis. To address this issue, we propose several evaluation measures to explore the similarities and differences among different problems from the perspective of solution space features. The measures are the similarity, the keenness, the stationarity of amplitude changes, the periodicity and the average fitness. These measures can reflect the characteristics of the solution space in terms of the similarity degree, the acuteness degree, the shape feature, the period length and the average fitness. Based on their impact, these measures are divided into two groups: primary measures and auxiliary measures. Furthermore, we apply these measures to small-scale problems and large-scale problems to explore the problem features of each problem and the relevance among different problems. The results demonstrate that the solution spaces of job-based scheduling problems are similar in terms of the periodicity, the shape feature, and the change rule of average fitness but have certain differences in the change rule of the acuteness degree. The evaluation measures can reflect the similarities and differences of job-based scheduling problems. Our work can promote mutual learning among various job-based scheduling problems and provide guidance for algorithm selection, adjusting evolution process and parameters choice. In addition, it can establish a theoretical basis for a unify solution framework for job-based scheduling problems. (C) 2018 Elsevier B.V. All rights reserved.