A Hybrid Benders Decomposition Algorithm and New Models for the Distributed Permutation Flowshop Scheduling Problem

Authors : Hanifi İŞGÜDER, Alper HAMZADAYI

Pages : 126-148

Doi:10.31590/ejosat.814129

View : 16 | Download : 14

Publication Date : 2021-04-30

Article Type : Research Paper

Abstract :Dağıtılmış permütasyon akış tipi çizelgeleme problemi (DPATÇP), işleri işlemek için birkaç fabrikanın mevcut olduğu akış tipi çizelgeleme probleminin bir genellemesidir. Bu çalışmada, çoklu gezgin satıcı problemi (ÇGSP) için geliştirilen modellerden esinlenilerek iki yeni matematiksel model ve farklı matematiksel modellere dayalı olarak altı farklı saf Benders ayrıştırma algoritmaları geliştirilmiştir. Ayrıca, en iyi performansı sağlayan matematiksel model aracılığıyla hibrit bir Benders ayrıştırma algoritması geliştirilmiştir. Yeni geliştirilen dokuz kesin çözüm yöntemi, Naderi ve Ruiz (2010) tarafından önerilen en iyi matematiksel modeller ve otomatik Benders ayrıştırma algoritması ile literatürde mevcut olan 84 problem seti kullanılarak karşılaştırılmıştır. Tüm mevcut ve yeni kesin çözüm algoritmaların karşılaştırılması için gerçekleştirilen deneyin sonuçları, önerilen hibrit Benders ayrıştırma algoritmasının diğer yöntemlere kıyasla önemli ölçüde daha iyi performans gösterdiğini ortaya koymuştur. Bu makalede, DPATÇP için 4 yeni en iyi çözüm saptanmıştır.
Keywords : Dağıtılmış akış tipi problem, Karışık tamsayı doğrusal programlama, Benders ayrıştırma algoritması, LS3 yerel arama prosedürü