New formulations for order acceptance and scheduling problem and its extentions

In make-to-order production environment, when scheduling the orders, it is not an obligatory to process all the orders. This topic is treated order acceptance and scheduling problem in the literature. In the scope of this thesis, the mathematical formulations in the literature are determined, examined, and analyzed. The form of order accepted and scheduling problem with sequence-dependent setup times, release dates and deadlines is considered. The relationship between setup times and release dates are researched in the general scheduling literature and it is detected that there is not a common approach regarding this relationship. As a solution to this, a new and a common approach is proposed. New mathematical formulations with O(n2) the number of decision variables and O(n2) the number of constraints are presented. Besides, identical parallel machines form of above-mentioned problem is considered and a new mathematical formulation with O(n2) the number of decision variables and O(n2) the number of constraints is presented. The performances of the formulations are compared with the original and the recent ones from the literature. As a result, it is concluded that our proposed formulations are much superior to the existing ones regarding the number of optimal values obtained in a limited time and the run times. Since large-sized problems cannot be solved with mathematical formulation in a reasonable time, a variable neighborhood search based simulated annealing algorithm is developed to solve these problems approximately. The effectiveness of the heuristic algorithm is tested by means of the mathematical formulation. It is colcluded that the heuristic algorithm yields better solutions in quite shorter time as the problem structure gets harder.