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

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

European Journal of Operational Research, 2018, vol. 270, issue 3, 809-825

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.

Keywords: Scheduling; Similarities; Differences; Solution space analysis; Evaluation measures (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718300870
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:270:y:2018:i:3:p:809-825

DOI: 10.1016/j.ejor.2018.01.051

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().