Sipariş kabulü ve çizelgeleme problemleri için matematiksel modeller ve sezgisel algoritmalar

In make-to-order production systems, manufacturers often do not keep inventory of final goods beforehand which necessitates utilizing the production capacity more efficiently to be able to complete orders in more timely manner. Yet, it may not be possible to complete all orders on time when the order delivery time requirements of customers get more tight under a limited production capacity. In this case, manufacturers have to reject some orders and should simultaneously decide which orders to accept and how to schedule accepted orders since both decisions strictly depend on each other. The corresponding problem is called as the order acceptance and scheduling problem in the literature. In this thesis, we study the order acceptance and scheduling problem with release times and sequence dependent setup times that determines the set of accepted orders and their schedule so as to maximize the total revenue. In this thesis, a mixed integer and a constraint programming model, and a matheuristic algorithm along with a new relaxed time-indexed model formulation, a variable neighborhood and a tabu search algorithm to be used within are presented for the generalized order acceptance and scheduling problem. Computational results show that the proposed models achieve smaller optimality gaps than the existing models in the literature and the proposed matheuristic algorithm outperforms both the proposed models and the state-of-the-art algorithms for the order acceptance and scheduling problem in the literature. New optimal solutions are also identified by the proposed models and the matheuristic algorithm. Then, the order acceptance and scheduling problem is extended to include batch delivery of orders. In this extension, orders are not delivered individually (i.e., upon their completion) but rather are delivered in batches which is observed more often in real-life practices. Mathematical models developed for the original problem are adapted to this extension. To tackle large size problem instances in which these models do not perform well, we propose two different iterated local search (ILS) algorithms. The first ILS employs a variable neighborhood search algorithm with alternating objective functions and the second ILS utilizes a tabu search algorithm as its local search mechanism. Computational results show that the proposed models achieve small optimality gaps for the small size problems. However, their performances deteriorate significantly as problem size increases. For medium and large size instances, the first ILS algorithm using the proposed alternating objective functions achieves smaller optimality gaps than both the proposed models and the second ILS algorithm with tabu search.