A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion

Basit Öğe Kaydı
dc.authoridMehmet Fatih Taşgetiren / 0000-0002-5716-575X
dc.authorscopusidMehmet Fatih Taşgetiren / 6505799356
dc.authorwosidMehmet Fatih Taşgetiren / CDL-1821-2022
dc.contributor.authorKızılay, Damla
dc.contributor.authorTaşgetiren, Mehmet Fatih
dc.contributor.authorPan, Quan-Ke
dc.contributor.authorGao, Liang
dc.date.accessioned2020-08-30T20:06:49Z
dc.date.available2020-08-30T20:06:49Z
dc.date.issued2019
dc.departmentİstinye Üniversitesi, Mühendislik ve Doğa Bilimleri Fakültesi, Endüstri Mühendisliği Bölümüen_US
dc.description.abstractIn 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.en_US
dc.description.sponsorshipNational Natural Science Foundation of ChinaNational Natural Science Foundation of China (NSFC) [51435009]en_US
dc.description.sponsorshipThis research is partially supported by the National Natural Science Foundation of China (Grant No. 51435009).en_US
dc.identifier.citationKizilay, 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/a12050100en_US
dc.identifier.doi10.3390/a12050100en_US
dc.identifier.issn1999-4893en_US
dc.identifier.issue5en_US
dc.identifier.scopus2-s2.0-85066617863en_US
dc.identifier.scopusqualityQ2en_US
dc.identifier.urihttps://doi.org/10.3390/a12050100
dc.identifier.urihttps://hdl.handle.net/20.500.12713/629
dc.identifier.volume12en_US
dc.identifier.wosWOS:000470960200013en_US
dc.identifier.wosqualityN/Aen_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.institutionauthorTaşgetiren, Mehmet Fatihen_US
dc.language.isoenen_US
dc.publisherMdpien_US
dc.relation.ispartofAlgorithmsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectHeuristic Optimizationen_US
dc.subjectBlock Insertion Heuristicen_US
dc.subjectFlow Shop Schedulingen_US
dc.subjectIterated Greedy Algorithmen_US
dc.subjectConstraint Programmingen_US
dc.subjectMixed Integer Programmingen_US
dc.titleA variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterionen_US
dc.typeArticleen_US

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim
İsim:
H31.pdf
Boyut:
804.98 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Tam Metin / Full Text
İndir

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Endüstri Mühendisliği Bölümü Makale Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu