Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/3533
Title: Sıra bağımlı ayar zamanı ve fazla mesai ile makine çizelgeleme
Other Titles: Machine scheduling with sequence dependent setup time and over time
Authors: Gültekin, Hakan
Bülbül, Zeynep
Keywords: Makine çizelgeme
Sıra bağımlı ayar zamanı
Fazla mesai
Benders ayrıştırma algoritması
Kısıt programlama
Tavlama benzetimi
Machine scheduling
Sequence dependent setup time
Overtime
Benders decomposition algorithm
Constraint programming
Simulated annealing algorithm
Issue Date: 2017
Publisher: TOBB University of Economics and Technology,Graduate School of Engineering and Science
TOBB ETÜ Fen Bilimleri Enstitüsü
Source: Bülbül, Z. (2017).Sıra bağımlı ayar zamanı ve fazla mesai ile makine çizelgeleme. Ankara: TOBB ETÜ Fen Bilimleri Enstitüsü. [Yayınlanmamış yüksek lisans tezi]
Abstract: Bu çalışma kapsamında sıra bağımlı ayar zamanı ile tek makine çizelgeleme problemi ele alınmaktadır. Bir gerçek hayat uygulamasını temel alan problemin amacı, en küçük toplam fazla mesai değeri ile müşteri taleplerinin teslim tarihinden önce hazır olmasını sağlayan haftalık üretim çizelgesini belirlemektir. Fazla mesai ücretleri fazla mesai yapılan süreye bağlı olarak hesaplanmaktadır. Bu problem için günlük detayda çizelgeler oluşturulmaktadır. Problem için öncelikle karma tam sayılı matematiksel programlama modeli geliştirilmiştir. Bu optimizasyon problemi için yapılan testlerde gerçek hayat örnekleri için makul sürelerde çözüm bulunamadığı görüldüğünden çözüm zamanını azaltmak amacıyla bir ayrıştırma algoritması geliştirilmiştir. Mantıksal Benders ayrıştırma algoritması olarak adlandırılan bu yaklaşımla karmaşık esas problem, karma tam sayılı ana problem ve çeşitli sayıda kısıt programlama alt problemleri olarak, görece kolay çözülebilir problemlere ayrıştırılmaktadır. Ana problemde işlerin günlere atanmasına karar verilirken, alt problemlerde bu atamalara göre günlük çizelgeler belirlenmektedir. Algoritma alt problemlerin çözümüne göre tanımlanan olurluluk veya optimallik kesilerinin ana probleme eklenmesi ile devam etmektedir. Çalışma kapsamında algoritma, kesilerin eklenme şekline göre iteratif ve dallandırma ve kontrol olmak üzere iki farklı yaklaşımla uygulanmıştır. Ayrıştırma algoritması ile, makul süre içerisinde optimal çözümü belirlemenin zorlaştığı örnekler için, ayrıca bir tavlama benzetimi algoritması geliştirilmiştir. Tavlama benzetimi için başlangıç çözümü, geliştirilen çözüm kuran algoritmayla, soğuma şeması ise gerçekleştirilen parametre analizleriyle belirlenmiştir. Geliştirilen bütün çözüm yöntemlerinin performansı yapılan deneysel çalışmalarla analiz edilmiştir.
In this study we considered a single machine scheduling problem with sequence dependent setup times from a real-world application. Our goal is to determine the weekly production schedule that minimizes the overtime with respect to deadlines. Here the available overtime periods are defined at the end of each day and related costs are calculated based on overtime use. Therefore the amount of overtime used at each day is determined through detailed schedules. We developed a mixed integer programming model for the problem. However our experimental studies showed that this optimization problem is intractable for real-world instances. A decomposition algorithm is proposed in order to decrease solution time. We developed a logic-based Benders decomposition algorithm which decomposes the original problem to a daily assignment problem and scheduling problems based on these assignments for each day. In this approach the master assignment problem is solved with mixed integer programming while sub scheduling problems are solved with constraint programming. The algorithm proceeds as the feasibility and optimality cuts, defined by the solutions obtained from subproblems, are added to the master problem. In the scope of this study related cuts are added either iteratively or with branch-and-check approach. For the instances that the decomposition algorithm could not find the optimal solution in a reasonable time, simulated annealing algorithm is used to obtain feasible solutions. In this context initial solution is determined through the constructive heuristic developed while cooling schedule is defined through parameter analyses. The performances of these solution approaches are tested through experimental studies.
URI: https://tez.yok.gov.tr/UlusalTezMerkezi/tezSorguSonucYeni.jsp
https://hdl.handle.net/20.500.11851/3533
Appears in Collections:Endüstri Mühendisliği Yüksek Lisans Tezleri / Industrial Engineering Master Theses

Files in This Item:
File Description SizeFormat 
476683.pdfZeynep Bülbül_Tez2.19 MBAdobe PDFThumbnail
View/Open
Show full item record

CORE Recommender

Page view(s)

180
checked on Dec 26, 2022

Download(s)

38
checked on Dec 26, 2022

Google ScholarTM

Check


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.