Dergiler / Yüzüncü Yıl Üniversitesi Fen Bilimleri Enstitüsü Dergisi / 2022 / Cilt: 27 - Sayı: 2
Tip-II Basit Montaj Hattı Dengeleme Probleminin Bölge Kısıtlamaları ile Çözümüne Yönelik Benders Ayrıştırma Algoritması
- Sayfa
- 400–415
- DOI
- —
Özet
Bu makale, işler ve istasyonlar arasındaki uyumluluğu (veya başka türlü) dikkate alarak ve istasyonlar arasındaki öncelik ilişkilerini gözlemleyerek belirli bir iş istasyonu kümesine bir dizi iş atamaktan oluşan, bölgeleme kısıtlamaları ile tip II montaj hattı dengeleme problemi ile ilgilidir. Amaç, herhangi bir istasyondaki en son tamamlanma süresini en aza indirmektir. Bu makale, Benders ayrıştırmasının yapısına uygun olarak bir dizi kısıtlamayı yinelemeli olarak ortaya koyan bir problem formasyonuna dayanan kesin bir algoritmayı açıklamaktadır. Algoritma, üst sınırlar oluşturmak için karar değişkenleri, kombinatoryel kesimler ve referanslı bir yerel arama üzerinde bir dizi sınırlayıcı kısıtlama içerir. Algoritmanın problem için en gelişmiş yaklaşımlardan daha üstün olduğu kıyaslamalı örnekler üzerinde kapsamlı hesaplama deneyleri ile gösterilmiştir.
Abstract
This paper considers the type-II assembly line balancing problem under zoning constraints, where a number of tasks must be assigned to a number of workstations while respecting compatibility (or otherwise) between tasks and stations, and by observing the precedence relationships between tasks. The objective is to minimize the latest completion time at any station. The paper proposes an exact algorithm that takes into account an exact formulation of the problem as well as iteratively introduces a set of constraints in the spirit of Benders decomposition. In addition to boundary constraints on the decision variables, the algorithm makes use of combinatorial cuts and a referenced local search in order to generate upper bounds. The algorithm is extensively evaluated on benchmark instances, which indicates that it outperforms the state-of-the-art approaches to the problem.