Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2014:2014:630280.
doi: 10.1155/2014/630280. Epub 2014 Aug 27.

Discrete bat algorithm for optimal problem of permutation flow shop scheduling

Qifang Luo  1 , Yongquan Zhou  1 , Jian Xie  1 , Mingzhi Ma  1 , Liangliang Li  1
Affiliations

Discrete bat algorithm for optimal problem of permutation flow shop scheduling

Qifang Luo et al. ScientificWorldJournal. 2014.

Abstract

A discrete bat algorithm (DBA) is proposed for optimal permutation flow shop scheduling problem (PFSP). Firstly, the discrete bat algorithm is constructed based on the idea of basic bat algorithm, which divide whole scheduling problem into many subscheduling problems and then NEH heuristic be introduced to solve subscheduling problem. Secondly, some subsequences are operated with certain probability in the pulse emission and loudness phases. An intensive virtual population neighborhood search is integrated into the discrete bat algorithm to further improve the performance. Finally, the experimental results show the suitability and efficiency of the present discrete bat algorithm for optimal permutation flow shop scheduling problem.

PubMed Disclaimer

Figures

Figure 1
Figure 1
Four neighborhood operations (swap, insert, inverse, and crossover).
Figure 2
Figure 2
Updating curve of pulse emission rate r i.
Figure 3
Figure 3
Box-and-whisker diagram of Car5.
Figure 4
Figure 4
Box-and-whisker diagram of Rec11.
Figure 5
Figure 5
The contribution of each strategy move to finding a new best solution.
Figure 6
Figure 6
Gantt chart of an optimal schedule for Car05, π ∗ = [5,4, 2,1, 3,8, 6,10,9, 7].
Figure 7
Figure 7
Gantt chart of an optimal schedule for Car06, π ∗ = [7,1, 5,6, 8,3, 4,2].
Figure 8
Figure 8
Gantt chart of an optimal schedule for Rec7, π ∗ = [17,13,18,12,9, 1,6, 3,8, 4,5, 2,7, 15,10,19,11,16,14,20].
Figure 9
Figure 9
Gantt chart of an optimal schedule for Rec11, π ∗ = [16,2, 14,9, 12,4, 20,13,10,19,8, 11,3, 5,15,17,1, 18,7, 6].
Figure 10
Figure 10
The convergence curves of Car5.
Figure 11
Figure 11
The convergence curves of Car6.
Figure 12
Figure 12
The convergence curves of Rec7.
Figure 13
Figure 13
The convergence curves of Rec11.
Algorithm 1
Algorithm 1
Basic bat algorithm (BA).
Algorithm 2
Algorithm 2
The pseudocode of NEH and NEH1.
Algorithm 3
Algorithm 3
The pseudocode of pulse emission rate local operation.
Algorithm 4
Algorithm 4
The pseudocode of loudness local operation.
Algorithm 5
Algorithm 5
The pseudocode of adjustment.
Algorithm 6
Algorithm 6
The DBA for PFSP.
See this image and copyright information in PMC

References

    1. Stadtler H. Supply chain management and advanced planning—basics, overview and challenges. European Journal of Operational Research. 2005;163(3):575–588.
    1. Rinnooy KA. Machine Scheduling Problems: Classification, Complexity, and Computations. The Hague, The Netherlands: Nijhoff; 1976.
    1. Della Croce F, Ghirardi M, Tadei R. An improved branch-and-bound algorithm for the two machine total completion time flow shop problem. European Journal of Operational Research. 2002;139(2):293–301.
    1. Stafford EF. On the development of a mixed integer linear programming model for the flowshop sequencing problem. Journal of the Operational Research Society. 1988;39:1163–1174.
    1. Wand L, Liu B. Particle Swarm Optimization and Scheduling Algorithms. Beijing, China: Tsinghua University Press; 2008.

Publication types