Sipariş kabul etme ve çizelgeleme problemi için değişken komşuluklu arama

Order acceptance is one of the important decisions to make while dealing with satisfaction of customers, risk of delays and overloaded production in competitive environments. A company can increase its pro fit, satisfy demands of the customers and utilize its capacity at its best with a proper management of the incoming orders through making acceptance-rejection decisions on the orders and simultaneously scheduling the accepted orders. This problem is known as the order acceptance and scheduling (OAS) problem. In this study, we examine two diff erent 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 pro fit to the manufacturer. Late delivery of an order causes tardiness cost which decreases the profi t. 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 defi ned 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 solution approach, to solve this NP-hard problem. The VNS is developed by using two neighborhood structures with a local search in a compact form. We analyze the performance of the VNS for both of the problems by using a benchmark data set. We present the computational experiments in which the VNS is compared with the most competitive metaheuristic algorithms from the literature. We conclude with the insights gained regarding the strengths and weaknesses of the proposed algorithm and that of the algorithms from the literature.