Dağıtılmış Permütasyon Akış Tipi Atölye Çizelgeleme Problemi için Hibrit Benders Ayrıştırma Algoritması ve Yeni Modeller

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.