Sipariş kabul ve çizelgeleme problemleri için zaman endeksli matematiksel modeller

Scheduling has been an active area of research for decades. A substantial amount of work has been done to define, classify, and solve scheduling problems. Most of these problems are computationally di ffcult to solve, and incorporating other decisions into them increases the complexity of these problems. This thesis focuses on order acceptance and scheduling (OAS) problems, and proposes time-indexed mixed integer and linear programming (MILP) models for the fi rst time. An OAS problem can be defi ned with parameters of processing time, release date, due date, and deadline for each order. There are also a maximum revenue that will be brought by each order and an importance weight of each order. Furthermore, there could be a setup time between orders if they are processed consecutively. In the thesis, both the general OAS problem (OAS 2) that will be defi ned with all above parameters, and a special case (OAS 1) that will exclude the release dates and setup times are considered. After developing a time-indexed MILP for both OAS 1 and OAS 2, their efficiency and eff ectiveness were tested computationally. To enhance both the effi ciency and the eff ectiveness of OAS 1, three dominance properties were suggested, and it was observed that while the optimality gap was decreased, the computational time was also reduced considerably so that large instances can be solved. Since OAS 2 is more challenging than OAS 1, the time-indexed MILP developed could not solve problem instances to optimality in a reasonable time. Hence, diff erent methods were proposed to find near optimal lower bounds and upper bounds for the problem. To obtain good upper bounds, a Lagrangian Relaxation method as well as a linear programming (LP) relaxation method with three new valid inequalities were proposed, and it is shown that Lagrangian Relaxation finds only loose upper bounds, but LP relaxation with valid inequalities improves almost all upper bounds for all sizes of instances. To obtain lower bounds, a simple heuristic method and a revised MILP formulation were presented, and then, it is shown that they are able to solve only small instances to optimality.