Two-stage cutting stock problems and scheduling extensions

Abstract

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ğrudankesilmesini engellediği durumlarda ortaya çıkmaktadır. Dolayısıyla, bitmiş rulolar üzerindekitalep, ilk aşamada üretilen ruloların sonrakine girdi olarak kullanıldığı ardışık ikikesme 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ışınada 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ırsetleri türeten satır-türeten altproblemden kaynaklanmaktadır. Sınırsız sırtçantası problemiolarak 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üretenaltproblem 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 çizelgelemeuzantı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.

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 rollsto demanded widths of finished rolls directly. Therefore, demands on finished rolls arefulfilled through two subsequent cutting processes, in which rolls produced in the formerare used as input for the latter, while the number of stock rolls used is minimized. Thepattern-based formulation of this problem, which typically has a large number of variablesand constraints, induces both a column-wise and a row-wise increase when solvedby column generation. An exact simultaneous column-and-row generation algorithm isdesigned to solve this formulation whose novel element is a row-generating subproblemthat generates a set of columns and rows. For this subproblem, which is modeled as anunbounded knapsack problem, three algorithms are proposed: implicit enumeration, columngeneration which renders the overall methodology nested column generation, and ahybrid algorithm. The latter two are integrated in a well-known knapsack algorithm whichforges a novel branch-and-price algorithm for the row-generating subproblem. Extensivecomputational experiments are conducted, and performances of the three algorithms arecompared. 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 thisproblem a heuristic approach based on optimization over a rolling horizon is proposed.