A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion
Yükleniyor...
Dosyalar
Tarih
2019
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Mdpi
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
In this paper, we propose a variable block insertion heuristic (VBIH) algorithm to solve the permutation flow shop scheduling problem (PFSP). The VBIH algorithm removes a block of jobs from the current solution. It applies an insertion local search to the partial solution. Then, it inserts the block into all possible positions in the partial solution sequentially. It chooses the best one amongst those solutions from block insertion moves. Finally, again an insertion local search is applied to the complete solution. If the new solution obtained is better than the current solution, it replaces the current solution with the new one. As long as it improves, it retains the same block size. Otherwise, the block size is incremented by one and a simulated annealing-based acceptance criterion is employed to accept the new solution in order to escape from local minima. This process is repeated until the block size reaches its maximum size. To verify the computational results, mixed integer programming (MIP) and constraint programming (CP) models are developed and solved using very recent small VRF benchmark suite. Optimal solutions are found for 108 out of 240 instances. Extensive computational results on the VRF large benchmark suite show that the proposed algorithm outperforms two variants of the iterated greedy algorithm. 236 out of 240 instances of large VRF benchmark suite are further improved for the first time in this paper. Ultimately, we run Taillard's benchmark suite and compare the algorithms. In addition to the above, three instances of Taillard's benchmark suite are also further improved for the first time in this paper since 1993.
Açıklama
Anahtar Kelimeler
Heuristic Optimization, Block Insertion Heuristic, Flow Shop Scheduling, Iterated Greedy Algorithm, Constraint Programming, Mixed Integer Programming
Kaynak
Algorithms
WoS Q Değeri
N/A
Scopus Q Değeri
Q2
Cilt
12
Sayı
5
Künye
Kizilay, D., Tasgetiren, M. F., Pan, Q.-K., & Gao, L. (2019). A Variable Block Insertion Heuristic for Solving Permutation Flow Shop Scheduling Problem with Makespan Criterion. ALGORITHMS, 12(5). https://doi.org/10.3390/a12050100
