Machine scheduling with sequence dependent setup time and over time

In this study we considered a single machine scheduling problem with sequence dependent setup times from a real-world application. Our goal is to determine the weekly production schedule that minimizes the overtime with respect to deadlines. Here the available overtime periods are defined at the end of each day and related costs are calculated based on overtime use. Therefore the amount of overtime used at each day is determined through detailed schedules. We developed a mixed integer programming model for the problem. However our experimental studies showed that this optimization problem is intractable for real-world instances. A decomposition algorithm is proposed in order to decrease solution time. We developed a logic-based Benders decomposition algorithm which decomposes the original problem to a daily assignment problem and scheduling problems based on these assignments for each day. In this approach the master assignment problem is solved with mixed integer programming while sub scheduling problems are solved with constraint programming. The algorithm proceeds as the feasibility and optimality cuts, defined by the solutions obtained from subproblems, are added to the master problem. In the scope of this study related cuts are added either iteratively or with branch-and-check approach. For the instances that the decomposition algorithm could not find the optimal solution in a reasonable time, simulated annealing algorithm is used to obtain feasible solutions. In this context initial solution is determined through the constructive heuristic developed while cooling schedule is defined through parameter analyses. The performances of these solution approaches are tested through experimental studies.