Variable neighborhood based memetic algorithm for distributed assembly permutation flowshop

Bo Liu; Keyao Wang; Ran Zhang

doi:10.1109/CEC.2016.7743990

Variable neighborhood based memetic algorithm for distributed assembly permutation flowshop

Bo Liu
, Keyao Wang
, Ran Zhang

School of Astronautics

CAS - Academy of Mathematics and System Sciences
Beihang University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

17 Scopus citations

Abstract

The Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP) is a typical NP-hard optimization problem and represents an important area in multiple distributed production systems. This paper proposes a memetic algorithm based on Variable Neighborhood Search (VNS) for DAPFSP with the criterion to minimize the maximum completion time (i.e., makespan). Particularly, an efficient initialization based on the Nawaz-Enscore-Ham (NEH) heuristic is applied for sequencing the order of products. Then, several new neighborhoods (intra-product, inter-product) are proposed and incorporated into VNS for perturbation of the job assignment to factories, as well as the adjustment of job sequence in each factory. Simulation results and comparisons demonstrate that the Variable Neighborhood based Memetic Algorithm could yield satisfactory searching performances.

Original language	English
Title of host publication	2016 IEEE Congress on Evolutionary Computation, CEC 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1682-1686
Number of pages	5
ISBN (Electronic)	9781509006229
DOIs	https://doi.org/10.1109/CEC.2016.7743990
State	Published - 14 Nov 2016
Event	2016 IEEE Congress on Evolutionary Computation, CEC 2016 - Vancouver, Canada Duration: 24 Jul 2016 → 29 Jul 2016

Publication series

Name	2016 IEEE Congress on Evolutionary Computation, CEC 2016

Conference

Conference	2016 IEEE Congress on Evolutionary Computation, CEC 2016
Country/Territory	Canada
City	Vancouver
Period	24/07/16 → 29/07/16

Keywords

Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP)
Memetic Algorithm (MA)
Variable Neighborhood Search (VNS)

Access to Document

10.1109/CEC.2016.7743990

Cite this

Liu, B., Wang, K., & Zhang, R. (2016). Variable neighborhood based memetic algorithm for distributed assembly permutation flowshop. In 2016 IEEE Congress on Evolutionary Computation, CEC 2016 (pp. 1682-1686). Article 7743990 (2016 IEEE Congress on Evolutionary Computation, CEC 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CEC.2016.7743990

@inproceedings{276d1f66bc1a41268d4aaf065eae349b,

title = "Variable neighborhood based memetic algorithm for distributed assembly permutation flowshop",

abstract = "The Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP) is a typical NP-hard optimization problem and represents an important area in multiple distributed production systems. This paper proposes a memetic algorithm based on Variable Neighborhood Search (VNS) for DAPFSP with the criterion to minimize the maximum completion time (i.e., makespan). Particularly, an efficient initialization based on the Nawaz-Enscore-Ham (NEH) heuristic is applied for sequencing the order of products. Then, several new neighborhoods (intra-product, inter-product) are proposed and incorporated into VNS for perturbation of the job assignment to factories, as well as the adjustment of job sequence in each factory. Simulation results and comparisons demonstrate that the Variable Neighborhood based Memetic Algorithm could yield satisfactory searching performances.",

keywords = "Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP), Memetic Algorithm (MA), Variable Neighborhood Search (VNS)",

author = "Bo Liu and Keyao Wang and Ran Zhang",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 IEEE Congress on Evolutionary Computation, CEC 2016 ; Conference date: 24-07-2016 Through 29-07-2016",

year = "2016",

month = nov,

day = "14",

doi = "10.1109/CEC.2016.7743990",

language = "英语",

series = "2016 IEEE Congress on Evolutionary Computation, CEC 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1682--1686",

booktitle = "2016 IEEE Congress on Evolutionary Computation, CEC 2016",

address = "美国",

}

Liu, B, Wang, K & Zhang, R 2016, Variable neighborhood based memetic algorithm for distributed assembly permutation flowshop. in 2016 IEEE Congress on Evolutionary Computation, CEC 2016., 7743990, 2016 IEEE Congress on Evolutionary Computation, CEC 2016, Institute of Electrical and Electronics Engineers Inc., pp. 1682-1686, 2016 IEEE Congress on Evolutionary Computation, CEC 2016, Vancouver, Canada, 24/07/16. https://doi.org/10.1109/CEC.2016.7743990

Variable neighborhood based memetic algorithm for distributed assembly permutation flowshop. / Liu, Bo; Wang, Keyao; Zhang, Ran.
2016 IEEE Congress on Evolutionary Computation, CEC 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 1682-1686 7743990 (2016 IEEE Congress on Evolutionary Computation, CEC 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Variable neighborhood based memetic algorithm for distributed assembly permutation flowshop

AU - Liu, Bo

AU - Wang, Keyao

AU - Zhang, Ran

PY - 2016/11/14

Y1 - 2016/11/14

N2 - The Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP) is a typical NP-hard optimization problem and represents an important area in multiple distributed production systems. This paper proposes a memetic algorithm based on Variable Neighborhood Search (VNS) for DAPFSP with the criterion to minimize the maximum completion time (i.e., makespan). Particularly, an efficient initialization based on the Nawaz-Enscore-Ham (NEH) heuristic is applied for sequencing the order of products. Then, several new neighborhoods (intra-product, inter-product) are proposed and incorporated into VNS for perturbation of the job assignment to factories, as well as the adjustment of job sequence in each factory. Simulation results and comparisons demonstrate that the Variable Neighborhood based Memetic Algorithm could yield satisfactory searching performances.

AB - The Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP) is a typical NP-hard optimization problem and represents an important area in multiple distributed production systems. This paper proposes a memetic algorithm based on Variable Neighborhood Search (VNS) for DAPFSP with the criterion to minimize the maximum completion time (i.e., makespan). Particularly, an efficient initialization based on the Nawaz-Enscore-Ham (NEH) heuristic is applied for sequencing the order of products. Then, several new neighborhoods (intra-product, inter-product) are proposed and incorporated into VNS for perturbation of the job assignment to factories, as well as the adjustment of job sequence in each factory. Simulation results and comparisons demonstrate that the Variable Neighborhood based Memetic Algorithm could yield satisfactory searching performances.

KW - Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP)

KW - Memetic Algorithm (MA)

KW - Variable Neighborhood Search (VNS)

UR - https://www.scopus.com/pages/publications/85008257117

U2 - 10.1109/CEC.2016.7743990

DO - 10.1109/CEC.2016.7743990

M3 - 会议稿件

AN - SCOPUS:85008257117

T3 - 2016 IEEE Congress on Evolutionary Computation, CEC 2016

SP - 1682

EP - 1686

BT - 2016 IEEE Congress on Evolutionary Computation, CEC 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE Congress on Evolutionary Computation, CEC 2016

Y2 - 24 July 2016 through 29 July 2016

ER -

Variable neighborhood based memetic algorithm for distributed assembly permutation flowshop

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this