Time-indexed mathematical models for order acceptance and scheduling problems
Sipariş kabul ve çizelgeleme problemleri için zaman endeksli matematiksel modeller
- Tez No: 397250
- Danışmanlar: PROF. DR. CEYDA OĞUZ
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 96
Özet
Uzun yıllardır üzerinde çalışılan bir konu olarak, çizelgeleme problemlerini tanımlayan, sınıflandıran ve çözen önemli sayıda çalışma yapılmıştır. Çizelgeleme problemlerinin büyük bir çoğunluğu, hesaplama karmaşıklığı yüksek olduğundan, zordur ve farklı problemlerle birleştirmek hesaplama karmaşıklığını daha çok arttırmaktadır. Bu tez, çizelgeleme problemini siparişleri kabul/red kararıyla birleştiren Sipariş Kabul ve Çizelgeleme Problemleri (SKÇ) üzerine odaklanmakta ve bu problem için ilk kez zaman endeksli Karışık Tam Sayılı Doğrusal Programlama (KTSDP) modelleri sunmaktadır. Sipariş kabul ve çizelgeleme problemi işlem süresi, serbest bırakılma tarihi, teslim tarihi ve son teslim tarihi parametreleriyle tanımlanabilir. Ayrıca, her siparişin maksimum gelir ve önem ağırlığı bulunmaktadır. Ek olarak, ardışık şekilde işlenen siparişler arasında hazırlama süresi bulunabilir. Bu tezde, yukarıdaki parametrelerle tanımlanan, genel sipariş kabul ve çizelgeleme problemi (SKÇ 2) ile serbest bırakılma tarihi ve hazırlama sürelerini dahil etmeyen özel hali (SKÇ 1) ele alınmıştır. Zaman endeksli KTSDP modeli SKÇ 1 ve SKÇ 2 için geliştirildikten sonra, bu modellerin yeterliliği ve etkinliği sayısal olarak test edilmiştir. SKÇ 1 modelinin yeterliliği ve etkinliğini arttırmak için, üç baskınlık özelliği önerilmiştir. Bu baskınlık özellikleri sonucunda hem eniyilik aralığının hem de çözüm zamanının azaldığı gözlemlenmiştir. Bu sayede büyük test örnekli problemler çözülebilmiştir. SKÇ 2, SKÇ'1 e kıyasla daha zor bir model olduğu için, zaman endeksli KTSDP modeli, problemi makul zaman çerçevesinde eniyi sonucu verecek şekilde çözememiştir. Bu sebeple, eniyi çözüme alt ve üst sınır bulabilmek amacıyla farklı yöntemler sunulmuştur. İyi bir üst sınır elde etmek amacıyla Lagrangian Gevşetmesi yanı sıra, üç adet yeni geçerli eşitsizlik içeren Doğrusal Programlama Gevşetmesi önerilmiştir. Yapılan testler sonucunda Lagrangian Gevşetmesi sadece gevşek üst sınırlar bulurken, geçerli eşitsizlik içeren Doğrusal Programlama Gevşetmesi yaklaşık olarak bütün üst sınırları tüm test örnekleri için geliştirmiştir. Alt sınır elde etmek için, basit bir sezgisel yöntem ve yeniden düzenlenmiş KTSDP formülü sunulmuş ve bu yöntemlerin sadece küçük test örnekli problemleri en iyi şekilde çözebildiği gösterilmiştir.
Özet (Çeviri)
Scheduling has been an active area of research for decades. A substantial amount of work has been done to define, classify, and solve scheduling problems. Most of these problems are computationally diffcult to solve, and incorporating other decisions into them increases the complexity of these problems. This thesis focuses on order acceptance and scheduling (OAS) problems, and proposes time-indexed mixed integer and linear programming (MILP) models for the fi rst time. An OAS problem can be defi ned with parameters of processing time, release date, due date, and deadline for each order. There are also a maximum revenue that will be brought by each order and an importance weight of each order. Furthermore, there could be a setup time between orders if they are processed consecutively. In the thesis, both the general OAS problem (OAS 2) that will be defi ned with all above parameters, and a special case (OAS 1) that will exclude the release dates and setup times are considered. After developing a time-indexed MILP for both OAS 1 and OAS 2, their efficiency and eff ectiveness were tested computationally. To enhance both the efficiency and the eff ectiveness of OAS 1, three dominance properties were suggested, and it was observed that while the optimality gap was decreased, the computational time was also reduced considerably so that large instances can be solved. Since OAS 2 is more challenging than OAS 1, the time-indexed MILP developed could not solve problem instances to optimality in a reasonable time. Hence, diff erent methods were proposed to find near optimal lower bounds and upper bounds for the problem. To obtain good upper bounds, a Lagrangian Relaxation method as well as a linear programming (LP) relaxation method with three new valid inequalities were proposed, and it is shown that Lagrangian Relaxation finds only loose upper bounds, but LP relaxation with valid inequalities improves almost all upper bounds for all sizes of instances. To obtain lower bounds, a simple heuristic method and a revised MILP formulation were presented, and then, it is shown that they are able to solve only small instances to optimality.
Benzer Tezler
- Mathematical models and heuristic algorithmsfor the order acceptance and schedulingproblems
Sipariş kabulü ve çizelgeleme problemleri için matematiksel modeller ve sezgisel algoritmalar
İSTENÇ TARHAN
Doktora
İngilizce
2020
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. CEYDA OĞUZ
- Yatırım fizibiliteleri üzerinde hedef programlamasının uygulanması
Linear goal programming applications on investment projects
E.ŞEBNEM SOYDAN
Yüksek Lisans
Türkçe
1993
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. MEHMET TANYAŞ
- Ulaştırma sistemlerinin bütünleşik analizi
Integrated analysis of transportation systems
TEVFİK BAŞAL
Yüksek Lisans
Türkçe
1998
Ulaşımİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. GÜNGÖR EVREN
- Enflasyonist ortamda hayat sigorta işletmelerinde yatırımlar ve kar payı hesaplanması
Başlık çevirisi yok
B. MÜGE BERKOL
Yüksek Lisans
Türkçe
1996
SigortacılıkMarmara ÜniversitesiSigortacılık Ana Bilim Dalı
YRD. DOÇ. DR. SAADET TANTAN
- Kanat profili üzerinde oluşan buzun iki boyutta matematiksel modellenmesi ve sayısal çözümü
Two dimensional mathematical modelling and numerical solution of accumulated ice on wing profiles
RAMAZAN DÖKME
Yüksek Lisans
Türkçe
2019
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET CİHAT BAYTAŞ