Sipariş kabul etme ve çizelgeleme problemi için bir tabu arama algoritması

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.