Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 809-825 |
Number of pages | 17 |
Journal | European Journal of Operational Research |
Volume | 270 |
Issue number | 3 |
DOIs | |
State | Published - Nov 1 2018 |
Bibliographical note
Funding Information:This research is supported by the National Natural Science Foundation of China under Grant Nos. 61671041 and 61101153 .
Publisher Copyright:
© 2018 Elsevier B.V.
Keywords
- Differences
- Evaluation measures
- Scheduling
- Similarities
- Solution space analysis
ASJC Scopus subject areas
- Computer Science (all)
- Modeling and Simulation
- Management Science and Operations Research
- Information Systems and Management
- Industrial and Manufacturing Engineering