Mathematical models and heuristic algorithmsfor the order acceptance and schedulingproblems
Sipariş kabulü ve çizelgeleme problemleri için matematiksel modeller ve sezgisel algoritmalar
- Tez No: 611751
- Danışmanlar: PROF. DR. CEYDA OĞUZ
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- 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ı: 121
Özet
Sipariş üzerine çalışan üretim sistemlerinde, üreticiler genellikle nihai ürün için önceden envanter tutmazlar; bu da, tüm siparişleri zamanında tamamlayabilmek için üretim kapasitesinin verimli bir şekilde kullanılmasını gerektirir. Ancak müşterilerin, siparişlerin dağıtım süresi ile ilgili talepleri sıkılaştıkça, kapasitenin kısıtlı olmasından dolayı tüm siparişleri zamanında tamamlamak mümkün olmayabilir. Bu durumda, üreticiler bazı siparişleri reddetmek zorunda kalır ve hangi siparişlerin kabul edileceğine ve kabul edilen siparişlerin çizelgelemesine eşzamanlı olarak karar vermek gerekir. İlgili problem literatürde, sipariş kabulü ve çizelgeleme problemi olarak adlandırılmaktadır. Bu tezde, siparişlerin serbest kalma zamanlarını ve siparişler arasındaki sıraya bağlı hazırlama sürelerini de içeren ve kabul edilen siparişleri ve bunların çizelgelemesini belirleyerek geliri enbüyükleyen genelleştirilmiş sipariş kabulü ve çizelgeleme problemini çalıştık. Genelleştirilmiş sipariş kabulü ve çizelgeleme problemi için, karışık tamsayı programlama modeli, kısıt programlama modeli ve yeni bir gevşetilmiş zaman indeksli model formülasyonu, değişken komşu arama ve tabu arama algoritmalarını bünyesinde barındıran bir mat-sezgisel algoritma sunulmuştur. Sayısal deneyler önerilen modellerin literatürdeki modellerden daha az eniyilik boşluğu ile sonuçlandığını gösterirken, önerilen mat-sezgisel algoritmanın da önerilen modellerden ve literatürdeki en gelişkin algoritmalardan daha iyi sonuç verdiğine işaret ediyor. Tezin bir sonraki aşamasında, sipariş kabulü ve çizelgeleme problemi, ürünlerin öbekler halinde dağıtılmasını da dahil ederek genişletilmiştir. Bu genişletilmiş problemde, siparişler tek tek gönderilmek yerine, pratikte daha sıklıkla gözlenildiği gibi, öbekler halinde gönderilmektedir. Bu problemin çözümü için, ele alınan ilk problem için geliştirilen matematiksel modeller bu probleme de uyarlanmıştır. Modellerin başarısız olduğu büyük boyutlu problemlerin üstesinden gelebilmek için, iki farklı yinelemeli yerel arama algoritması önerilmiştir. Birinci algoritmada yerel arama algoritması olarak birbirini izleyen amaç fonksiyonlarını kullanan değişken arama algoritması uygulanırken, ikinci algoritmanın yerel arama mekanizması olarak tabu arama algoritması kullanılmıştır. Sayısal sonuçlar önerilen modellerin küçük boyutlu problemler için küçük eniyilik boşluğuna ulaştığını ancak büyük boyutlu problemlerde bu modellerin performansının önemli ölçüde düştüğünü göstermektedir. Orta ve büyük boyutlu problemlerde, birbirini izleyen amaç fonksiyonları yaklaşımını kullanan yinelemeli yerel arama algoritmasının hem önerilen modellerden hem tabu arama algoritmasını kullanan yinelemeli yerel arama algoritmasından daha küçük eniyilik boşluğuna ulaştığı görülmüştür.
Özet (Çeviri)
In make-to-order production systems, manufacturers often do not keep inventory of final goods beforehand which necessitates utilizing the production capacity more efficiently to be able to complete orders in more timely manner. Yet, it may not be possible to complete all orders on time when the order delivery time requirements of customers get more tight under a limited production capacity. In this case, manufacturers have to reject some orders and should simultaneously decide which orders to accept and how to schedule accepted orders since both decisions strictly depend on each other. The corresponding problem is called as the order acceptance and scheduling problem in the literature. In this thesis, we study the order acceptance and scheduling problem with release times and sequence dependent setup times that determines the set of accepted orders and their schedule so as to maximize the total revenue. In this thesis, a mixed integer and a constraint programming model, and a matheuristic algorithm along with a new relaxed time-indexed model formulation, a variable neighborhood and a tabu search algorithm to be used within are presented for the generalized order acceptance and scheduling problem. Computational results show that the proposed models achieve smaller optimality gaps than the existing models in the literature and the proposed matheuristic algorithm outperforms both the proposed models and the state-of-the-art algorithms for the order acceptance and scheduling problem in the literature. New optimal solutions are also identified by the proposed models and the matheuristic algorithm. Then, the order acceptance and scheduling problem is extended to include batch delivery of orders. In this extension, orders are not delivered individually (i.e., upon their completion) but rather are delivered in batches which is observed more often in real-life practices. Mathematical models developed for the original problem are adapted to this extension. To tackle large size problem instances in which these models do not perform well, we propose two different iterated local search (ILS) algorithms. The first ILS employs a variable neighborhood search algorithm with alternating objective functions and the second ILS utilizes a tabu search algorithm as its local search mechanism. Computational results show that the proposed models achieve small optimality gaps for the small size problems. However, their performances deteriorate significantly as problem size increases. For medium and large size instances, the first ILS algorithm using the proposed alternating objective functions achieves smaller optimality gaps than both the proposed models and the second ILS algorithm with tabu search.
Benzer Tezler
- Hücresel imalatın başlangıç aşamaları için uzman sistem yaklaşımı
An Expert systems approach to the early stages of cellular manufacturing systems design
UFUK CEBECİ
- Crew recovery optimization through disruption analysis and deep learning driven column generation
Aksaklık analizi ve derin öğrenme tabanlı sütun oluşturma ile ekip kurtarma optimizasyonu
AHMET HEREKOĞLU
Doktora
İngilizce
2024
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. ÖZGÜR KABAK
- Optimizasyon algoritmaları ile depolarda sipariş toplama süreçleri etkinliğinin artırılması
Optimization algorithms for improving the efficiency of order picking processes in warehouses
ESRA BOZ
Doktora
Türkçe
2022
Endüstri ve Endüstri MühendisliğiEskişehir Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. NİL ARAS
- The location-routing problem with inventory control considerations: Formulation, solution method and computational results
Stok kontrollü konum belirleme-rotalama problemi: Formüle edilmesi, çözüm metodu ve hesaplamalı sonuçlar
ZEYNEP ORMAN
Yüksek Lisans
İngilizce
2005
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. METİN TÜRKAY
Y.DOÇ.DR. SELÇUK SAVAŞ
- Özdeş parça üreten esnek işlemli akış tipi sistemlerde çıktı miktarının en büyüklenmesi
Throughput maximization in flowshops producing identical parts having flexible operations
FATMA İŞLER
Yüksek Lisans
Türkçe
2013
Endüstri ve Endüstri MühendisliğiTOBB Ekonomi ve Teknoloji ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. HAKAN GÜLTEKİN