Sipariş kabul ve çizelgeleme problemi ve uzantılarına ilişkin yeni matematiksel modeller
New formulations for order acceptance and scheduling problem and its extentions
Yazar: PAPATYA SEVGİN BIÇAKCI
Danışman: PROF. DR. İMDAT KARA
Başkent Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Doktora, 2020
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Siparişe göre üretim yapan sistemlerde, siparişleri çizelgelerken her siparişin yapılması zorunluluğu bulunmamaktadır. Bu konu kaynaklarda sipariş kabul ve çizelgeleme problemi olarak ele alınmaktadır. Bu tez kapsamında, sipariş kabul ve çizelgeleme problemi ile ilgili kaynaklarda var olan matematiksel modellere erişilmiş ve modeller incelenip, irdelenmiştir. Sipariş kabul ve çizelgeleme probleminin en erken başlama zamanlarının, sıra-bağımlı hazırlık sürelerinin ve son teslim tarihlerinin olduğu özel bir durumu ele alınmıştır. Genel çizelgeleme kaynaklarında, hazırlık süresi ve en erken başlama zamanı arasındaki ilişkiler araştırılmış ve ortak bir yaklaşım olmadığı fark edilmiştir. Bu duruma bir çözüm olarak ortak ve yeni bir yaklaşım geliştirilmiştir. Söz konusu durumlara ilişkin O(n2) kısıt sayısı O(n2) karar değişkeni sayısı bulunan yeni modeller önerilmiştir. Yanı sıra, yukarıda belirtilen özel problemin özdeş paralel makineler durumu ele alınmış ve bu konuda da O(n2) kısıt sayısı O(n2) karar değişkeni sayısı bulunan yeni bir model önerilmiştir. Önerdiğimiz modellerin performansları kaynaklardan seçilen özgün ve güncel modellerle karşılaştırılmıştır. Sonuç olarak, önerdiğimiz modellerin belli bir süre kısıtı altında ulaşılan eniyi değer sayısı ve çözüm süresi açısından diğer modellere göre çok üstün olduğu anlaşılmıştır. Özdeş paralel makineler durumu için önerdiğimiz model ile büyük boyutlu problemler verilen sürede çözülemediğinden, bu problemleri yaklaşık olarak çözebilmek için değişken komşu arama tabanlı bir tavlama benzetimi algoritması geliştirilmiştir. Matematiksel model yardımıyla sezgisel algoritmanın etkililiği test edilmiş ve problem yapısı zorlaştıkça sezgisel algoritmanın çok daha kısa sürelerde daha iyi çözümler verdiği sonucuna varılmıştır.

Abstract:
In make-to-order production environment, when scheduling the orders, it is not an obligatory to process all the orders. This topic is treated order acceptance and scheduling problem in the literature. In the scope of this thesis, the mathematical formulations in the literature are determined, examined, and analyzed. The form of order accepted and scheduling problem with sequence-dependent setup times, release dates and deadlines is considered. The relationship between setup times and release dates are researched in the general scheduling literature and it is detected that there is not a common approach regarding this relationship. As a solution to this, a new and a common approach is proposed. New mathematical formulations with O(n2) the number of decision variables and O(n2) the number of constraints are presented. Besides, identical parallel machines form of above-mentioned problem is considered and a new mathematical formulation with O(n2) the number of decision variables and O(n2) the number of constraints is presented. The performances of the formulations are compared with the original and the recent ones from the literature. As a result, it is concluded that our proposed formulations are much superior to the existing ones regarding the number of optimal values obtained in a limited time and the run times. Since large-sized problems cannot be solved with mathematical formulation in a reasonable time, a variable neighborhood search based simulated annealing algorithm is developed to solve these problems approximately. The effectiveness of the heuristic algorithm is tested by means of the mathematical formulation. It is colcluded that the heuristic algorithm yields better solutions in quite shorter time as the problem structure gets harder.