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ı: Belirtilmemiş.
Ö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İ
- Lojistik sistemlerin yapay sinir ağları ile modellenmesi, gerçeklenmesi ve kontrolü
Modeling, implementation and control of logistics systems using artificial neural networks
MURAT ERMİŞ
Doktora
Türkçe
2005
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF.DR. FÜSUN ÜLENGİL
- Robotik sıkıştırılmış kutuya toplama depo sistemlerinde toplama politikalarının yapay arı kolonisi algoritması ile belirlenmesi
Determination of picking policies in robotic compact bin picking storage systems with artificial bee colony algorithm
FURKAN YENER
Doktora
Türkçe
2023
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. HARUN REŞİT YAZĞAN
- Hücresel imalat sistemlerinde maliyet ve sinir ağları tabanlı iki evreli bir kümelendirme yaklaşımı
Artificial neurat network x operation costs based twostage GT clusterning procedure
AFFAN NOMAK
Yüksek Lisans
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. BÜLENT DURMUŞOĞLU
- 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