Kesme ve yükleme problemleri için lagrange fonksiyonları temelli çözüm yöntemleri
Lagrange function based solution methods for cutting and packing problems
Yazar: BANU İÇMEN ERDEM
Danışman: PROF. DR. REFAİL KASIMBEYLİ
Eskişehir Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Doktora, 2021
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Genetik algoritmalar = Genetic algorithms ; Global optimizasyon yöntemi = Global optimization method ; Lagrange fonksiyonları = Lagrange function ; Lagrange çarpanı = Lagrange multiplier ; Tavlama benzetimi = Simulated annealing

Özet:
Bu tez kapsamında bir ve iki boyutlu kesme problemleri çeşitli kısıtlar ile ele alınmış, bu problemler için kesin, sezgisel ve metasezgisel çözüm yöntemleri araştırılmıştır. Modifiye subgradiyent algoritması ile metasezgisel yöntemleri birleştiren melez bir çözüm yaklaşımı geliştirilmiştir. Uygun çözüm temelli modifiye subgradiyent algoritması olarak adlandırılan bu melez yaklaşım, birinci dereceden norm terimi ile genişletilmiş Lagrange fonksiyonu kullanılarak oluşturulmuş ikil problemin, Modifiye subgradiyent algoritması ile çözümü fikrine dayanmaktadır. İteratif bir yöntem olan bu yaklaşımda, her adımda söz konusu genişletilmiş Lagrange fonksiyonu kullanılarak oluşturulmuş alt problemin, farklı metasezgiseller kullanılarak uygun çözümleri elde edilir. En iyilik kriterleri kullanılarak incelenen uygun çözümler, en iyi değil ise Modifiye subgradiyent algoritması kullanılarak Lagrange çarpanları güncelleştirilerek, tekrar alt probleme dönülür. Bu yaklaşımda, oluşturulan alt problemlerin çözümünde, probleme uygun yerleştirme sezgiselleri içeren, genetik algoritma ve tavlama benzetimi kullanılmıştır. Önerilen melez çözüm yaklaşımı, literatürdeki test problemlerinin çözümüne uygulanmış ve performansı, detaylı bilgisayar hesaplamaları ile analiz edilmiştir. Bu melez yöntem dışında, iki boyutlu kesme problemleri için yeni iki aşamalı yöntemler öne sürülmüş ve çözüm performansları incelenmiştir.

Abstract:
Within the scope of this thesis, one- and two- dimensional cutting stock problems are studied with various assumptions and constraints, and exact, heuristic and metaheuristic solution methods for these problems are investigated. A hybrid solution approach has been developed that combines the Modified subgradient algorithm and metaheuristic methods. This approach, which is called feasible solution-based modified subgradient algorithm, is based on the idea of solving the dual problem created using the sharp augmented Lagrange function, with the Modified subgradient algorithm. In this iterative approach, feasible solutions of the aforementioned augmented Lagrangian function are obtained by using different metaheuristics at each step. Feasible solutions that been investigated by using optimality criteria are not optimal, by using Modified subgradient algorithm Lagrangian multipliers are updated and sub-problem is returned again. In this approach, genetic algorithm and simulated annealing, which includes suitable placement heuristics for the problem, are used to solve the sub-problems created. The proposed hybrid solution approach has been applied to the solution of test problems in the literature and its performance has been analyzed with detailed computer calculations. Apart from this hybrid method, a new two-stage methods have been proposed for two-dimensional cutting problems and their solution performances have been examined.