期刊
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
卷 47, 期 1, 页码 1-24出版社
TAYLOR & FRANCIS LTD
DOI: 10.1080/00207540701528750
关键词
Differential evolution; Flow shop scheduling; Limited buffers; Hybrid algorithm; Local search; Exploration and exploitation
资金
- NSFC [60574072]
- National 863 Hi-Tech R D Plan [2007AA04Z155, 2007AA04Z193]
- 973 Program [2002CB312200]
- SRF for ROCS
- SEM
The permutation flow-shop scheduling problem (PFSSP) is a typical combinational optimization problem, which is of wide engineering background and has been proved to be strongly NP-hard. In this paper, an effective hybrid algorithm based on differential evolution (DE), namely HDE, is proposed for permutation flow-shop scheduling with limited buffers between consecutive machines to minimize the maximum completion time (i.e. makespan). First, to make DE suitable for solving PFSSP, a largest-order-value (LOV) rule is presented to convert the continuous values of individuals in DE to job permutations. Second, after the DE-based exploration, an efficient local search, which is designed according to the landscape of PFSSP and the generalization of the block elimination properties, is applied to emphasize exploitation. Thus, not only does the HDE apply the parallel evolution mechanism of DE to perform effective exploration (global search), but it also adopts problem-dependent local search to perform exploitation well (local search). Furthermore, the convergence property of HDE is analyzed based on the theory of finite Markov chain. Simulations and comparisons based on benchmarks demonstrate the effectiveness and robustness of the proposed HDE, and the effect of one key parameter on the performance of HDE is investigated as well.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据