A Logistic Model for Solution Space of Job Shop Scheduling Problem
Lists
Only you see this
Abstract
Lots of researchers have been attracted to the mystery of the solution space of the scheduling problem. In this paper, we introduce the Logistic Model, a core theory in population ecology, into job shop scheduling problem, surprised to find that the cumulative distribution of makespan has a perfect match with the S-curve. And what’ more, this neglected distribution property can truly and stably reflect the structure of the Fitness Landscape, whether it is a static randomly generated space, or a dynamic algorithm search space. Finally, we use the inflexion point of the S-curve as the characteristic number to study the difficulty level of the Job Shop Scheduling Problem, the processing path, the distribution of processing time, and the shape of the problem respectively. Experimental results show that compared with the previous methods, the Logistic Model can well reflect the intrinsic properties, and nicely distinguish the difficulty level of the problem. So, this is a new simple and accurate way to describe the characteristics of the problem, and to guide the design and evaluation of algorithms.
BibTeX
@article{wen2011logistic,
author = {Feng Wen and Liang Gao and Xinyu Li},
title = {{A Logistic Model for Solution Space of Job Shop Scheduling Problem}},
journal = {International Journal of Advancements in Computing Technology},
year = {2011},
doi = {10.4156/ijact.vol3.issue9.29},
}Loading related content...