Two-stage cutting stock problems and scheduling extensions
İki-aşamalı stok kesme problemleri ve çizelgeleme uzantıları
- Tez No: 527543
- Danışmanlar: DOÇ. DR. İBRAHİM MUTER
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Bahçeşehir Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 93
Özet
Bu tezde tek boyutlu stok kesme probleminin iki-aşamalı uzantısı incelenmiştir. Bu problem, teknik şartların stok rulolarını talep edilen genişliklerdeki bitmiş rulolara doğrudan kesilmesini engellediği durumlarda ortaya çıkmaktadır. Dolayısıyla, bitmiş rulolar üzerindeki talep, ilk aşamada üretilen ruloların sonrakine girdi olarak kullanıldığı ardışık iki kesme işlemiyle karşılanmakta ve kullanılan stok rulosu sayısı en aza indirilmektedir. Problemin örüntü-tabanlı formülasyonu genellikle çok sayıda değişken ve kısıt içerdiğinden, çözüm için sütun türetme yöntemi kullanılması, sütun artışının yanısıra satır artışına da neden olmaktadır. Bu formülasyonun çözümü için kesin çözümlü bir eşzamanlı sütun-ve- satır türetme algoritması tasarlanmıştır. Bu algoritmanın özgünlüğü sütun ve satır setleri türeten satır-türeten altproblemden kaynaklanmaktadır. Sınırsız sırtçantası problemi olarak modellenen bu altproblemin çözümü için üç algoritma önerilmiştir: örtülü listeleme, içiçe sütun türetme yöntemini ortaya koyan sütun-türetme ve hibrit algoritma. Son iki algoritma çok iyi bilinen bir sırtçantası algoritmasına entegre edilerek satır-türeten altproblem için yeni bir dal-ve-fiyat algoritması oluşturulmuştur. Yürütülen kapsamlı hesaplamalı deneylerle üç algoritmanın performansları karşılaştırılmıştır. Ayrıca, iki aşamalı stok kesme probleminin sipariş termin sürelerini de göz önüne alan bir çizelgeleme uzantısı öbek büyüklüğü belirleme problemi olarak modellenmiştir. Bu problemin çözümü için, kayan ufuklu optimizasyon yaklaşımına dayalı sezgisel bir yöntem önerilmiştir.
Özet (Çeviri)
In this thesis, a two-stage extension of one-dimensional cutting stock problem is considered. This problem arises when technical requirements inhibit cutting large stock rolls to demanded widths of finished rolls directly. Therefore, demands on finished rolls are fulfilled through two subsequent cutting processes, in which rolls produced in the former are used as input for the latter, while the number of stock rolls used is minimized. The pattern-based formulation of this problem, which typically has a large number of variables and constraints, induces both a column-wise and a row-wise increase when solved by column generation. An exact simultaneous column-and-row generation algorithm is designed to solve this formulation whose novel element is a row-generating subproblem that generates a set of columns and rows. For this subproblem, which is modeled as an unbounded knapsack problem, three algorithms are proposed: implicit enumeration, column generation which renders the overall methodology nested column generation, and a hybrid algorithm. The latter two are integrated in a well-known knapsack algorithm which forges a novel branch-and-price algorithm for the row-generating subproblem. Extensive computational experiments are conducted, and performances of the three algorithms are compared. Furthermore, a scheduling extension of the two-stage cutting stock problem, which incorporates order due dates, is formulated as a lot-sizing problem. To solve this problem a heuristic approach based on optimization over a rolling horizon is proposed.
Benzer Tezler
- Parça yerleştirme algoritmalarının postal oluşturma problemine uygulanması
Başlık çevirisi yok
FİLİZ BUNYAK
Yüksek Lisans
Türkçe
1996
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. FÜSUN TUNALI (SEÇUK)
- Kesme ve yükleme problemleri için lagrange fonksiyonları temelli çözüm yöntemleri
Lagrange function based solution methods for cutting and packing problems
BANU İÇMEN ERDEM
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiEskişehir Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. REFAİL KASIMBEYLİ
- İki boyutlu kesme ve ana malzeme seçimi problemleri için matematiksel modeller ve çözüm yaklaşımları
Mathematical models and solution approaches for two dimensional cutting and assortment problems
BANU İÇMEN
Yüksek Lisans
Türkçe
2015
Endüstri ve Endüstri MühendisliğiAnadolu ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. REFAİL KASIMBEYLİ
- Bir pafta üzerine iki boyutlu parçaların minimum ıskarta ile bilgisayar destekli yerleştirilmesi
Başlık çevirisi yok
YUNUS EMRE TOKMAK
Yüksek Lisans
Türkçe
1994
Makine MühendisliğiYıldız Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERHAN ALTAN