A tabu search algorithm for order acceptance and scheduling problem

Abstract

Bu tezde, sipariş teslim zamanlarının ve kısıtlı üretim kapasitesinin gelen siparişlerin seçilerek kabul edilmesini gerektirdiği, bir siparişe dayalı üretim sistemi ele alınmıştır. Ele alınan sistemde, kabul edilen ve teslim zamanından önce tamamlanıp, müşteriye teslim edilen her sipariş üreticiye kazanç sağlar. Geç teslim edilen siparişler teslim gecikmesi ile orantılı olarak kazançta bir düşüş yaratırken, termin zamanından önce tamamlanamayan işler kazanç getirmez. Herhangi bir siparişin reddedilmesi mümkündür ve hiçbir ek maliyet getirmez. Kabul edilen siparişler tek makine üzerinde, serbest bırakılma zamanlarından sonra olacak şekilde çizelgelenebilirler ve siparişler arasında sıraya bağlı hazırlık süreleri vardır. Kabul edilen siparişin kazancı, o siparişin tamamlanma zamanının birfonksiyonu olduğu ve bir siparişin işlenmesi sonraki siparişlerin gecikmesine neden olabileceği için sipariş kabul etme ve çizelgeleme kararları birlikte ele alınmalıdır. Elde edilen kazancı enbüyüklemek için, üretici hangi siparişleri kabul edeceğini ve bu siparişleri hangi sırada işleyeceğini belirlemelidir. Bu NP-zor eniyileme problemi için, etkili olasılıksal yerel arama ve çeşitlendirme mekanizmaları ile desteklenmiş bir tabu arama algoritması önerdik. Önerilen algoritmanın performansı, çeşitli parametre değerleri ile rassal olarak oluşturulmuş, çok sayıda örnek problem ile çözülerek incelenmiştir. Ayrıca bu algoritma, literatürde var olan iki ayrı sezgisel yöntem ile kıyaslanmıştır. Karşılaştırmalarda performans ölçütü olarak çözümlerin kazançlarının en yüksek kazançtan ne kadar uzak olduğu ele alınmıştır. Karışık tamsayılı programlama kullanılarak en yüksek kazanç için bir üst sınır elde edilmişve bu üst sınıra dayanarak hesaplanmış ortalama optimalite aralığı verilmiştir. Yaptığımız hesaplamalı deneylerin sonuçlarına göre, tabu arama algortiması amaç fonksiyonu açısından test edilen örneklerde kıyasladığımız diğer iki sezgisel yöntemden çok daha iyi sonuçlar vermiştir. Buna karşın, tabu arama algortimasının çalışma zamanı 100 adet sipariş verildiği örnekler için bile oldukça kısadır. Önerilen sezgisel yöntemin başarısı, büyük ölçüde, arama sürecine sipariş kabul etme ve çizelgeleme kararlarını birlikte dahil edebilmesine ve etkili çeşitlendirme mekanizmaları kullanmasına bağlıdır.

In this thesis, we consider a make-to-order production system, where limited production capacity and order delivery requirements necessitate selective acceptance among incoming orders. In the considered system, each accepted order that is completed and delivered to the customer before its quoted due date brings a revenue to the manufacturer. Late delivery of an order incurs tardiness costs and therefore causes a decrease in the revenue that is proportional to its tardiness. If an order cannot be completed before its deadline, then it brings no revenue. It is possible to reject an order and this incurs no additional penalty cost. Accepted orders should be scheduled after their corresponding release times on a single machine. A sequence-dependent setup time elapses between the processing of each order. Since revenue from an accepted order is a function of its completion time and processing of an order may delay the subsequent orders beyond their due dates, order acceptance and scheduling decisions should be taken jointly. In order to maximize the total revenue, the manufacturer has to determine which orders to accept and how to schedule them. For this NP-hard combinatorial optimization problem, we propose a new heuristic solution approach. Namely, we develop a tabu search algorithm which is supported with an effective probabilistic local search and diversification mechanism. We analyze the performance of the tabu search algorithm on an extensive set of test instances with up to 100 orders and compare it with two heuristics from the literature. In the comparison, we report optimality gaps which are calculated with respect to upper bounds generated from a mixed integer programming formulation. The results of our computational study show that the tabu search algorithm gives near optimal solutions that are significantly better compared to the solutions given by the two heuristics. Furthermore, the run time of the tabu search algorithm is very small, even for 100 orders. The success of the proposed heuristic largely depends on its capability to incorporate in its search the acceptance and scheduling decisions simultaneously, and to provide effective diversification mechanisms.