Variable neighborhood search for order acceptance and scheduling problem

Abstract

Günümüz rekabet ortamında, bir firma için sipariş kabul etme ya da reddetme kararıoldukça önem kazanmıştır. Bu problemin ortaya çıkmasının asıl nedeni, bir taraftan herfirmann belirli bir üretim kapasitesinin ve kıt kaynaklarnn olması diğer taraftan da sipariş veren her müşterinin ilgili firmadan belirli bir beklentisinin olmasıdır. Bu nedenlerle, firma özellikle çok fazla sipariş aldığı zamanlarda, gelen siparislerin bir kısmını reddetmek durumunda kalabilir. Bu noktada firmann hangi siparişi kabul edeceğine ve kabul ettiği siparişleri nasıl cizelgeleyeceğine dair önemli bir karar vermesi gerekmektedir. Bu problem yazında sipariş kabul etme ve çizelgeleme problemi (SKEÇ) olarak bilinir.Bu tezde, tek makine uzerinde iki farklı SKEÇ problemi ele alınmıştır. İlk problemdeher siparişin teslim tarihi, işlem süresi ve getirisi vardr. Kabul edilen ve teslim zamanından önce tamamlanıp, müşteriye teslim edilen her sipariş üreticiye en büyük kazanç sağlar. Geç teslim edilen siparişler kazançta bir düşüş yaratır. Herhangi bir siparişin reddedilmesi mümkündür ve hiçbir ek maliyet getirmez. Bazen muşteriler siparişleri için son teslim tarihi belirleyebilirler. Son teslim tarihi bir siparişin kabul edilebilmesi icin müşteri tarafından üreticiye verilen en son zamandır. Eger bir sipariş son teslim tarihinden sonra müşteriye ulaştırılırsa, müşteri siparişi reddeder ve satın almaz. Ek olarak, baz siparişler işlenmeye başlamaya hazır olmak icin serbest bırakılma zamanlarına ihtiyaç duyabilirler. İlk incelenen problem bir siparişin son teslim tarihini, serbest brakılma zamanın ve siparişler arasında sıraya bağlı hazırlık sürelerini yok sayarak problemi ele alırken bu özellikler ikinci problemdekapsanmıştır. Her iki problemin amaç fonksiyonu elde edilen kazancı en büyuklemektir.Bu tezde, incelenen problemler için degişken komşuluklu arama (DKA) algoritmasıönerilmiştir. DKA algoritması etkili yerel arama yöntemi ile iki komşuluk yapısının kullanılması yoluyla geliştirilmiştir. Önerilen algoritmanın performansı, yaznda bulunan sezgiselyöntemlerle kıyaslanmıştır. SKEÇ problemine uygulanan DKA algoritmasının yazında bulunansezgisel yöntemlere göre güçlü ve zayıf yönleri verilmiştir.

Order acceptance is one of the important decisions to make while dealing with satisfactionof customers, risk of delays and overloaded production in competitive environments. Acompany can increase its profit, satisfy demands of the customers and utilize its capacityat its best with a proper management of the incoming orders through making acceptance-rejection decisions on the orders and simultaneously scheduling the accepted orders. Thisproblem is known as the order acceptance and scheduling (OAS) problem.In this study, we examine two different OAS problems on a single machine environment.In the first problem, each order is characterized with a processing time, a due date, a weight and a revenue. Each accepted order which is delivered to the customer before its due date brings maximum profit to the manufacturer. Late delivery of an order causes tardiness cost which decreases the profit. The manufacturer can reject the order without a penalty cost. Sometimes customers may specify deadlines for their orders. Deadlines are the preferred latest time for the customers to accept the orders. If the completion time of an order exceeds the deadline, the customer refuses the order and does not pay for it. Moreover, some orders coming from the customers may be defined with release dates to be ready for the processing.In the firrst problem, we ignore sequence dependent setup times (preparation time necessary between two successive orders), deadlines and release dates. The second problem includes these properties. The objective function for both of the problems is to maximize total profit that is a function of total revenue and total tardiness.We propose a Variable Neighborhood Search (VNS), which is a metaheuristic solutionapproach, to solve this NP-hard problem. The VNS is developed by using two neighborhoodstructures with a local search in a compact form. We analyze the performance of the VNSfor both of the problems by using a benchmark data set. We present the computationalexperiments in which the VNS is compared with the most competitive metaheuristic algorithmsfrom the literature. We conclude with the insights gained regarding the strengthsand weaknesses of the proposed algorithm and that of the algorithms from the literature.