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

Hui Lu, Jinhua Shi, Zongming Fei, Qianlin Zhou, Kefei Mao

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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 languageEnglish
Pages (from-to)809-825
Number of pages17
JournalEuropean Journal of Operational Research
Volume270
Issue number3
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Analysis of the similarities and differences of job-based scheduling problems'. Together they form a unique fingerprint.

Cite this