Logic based Benders decomposition algorithm for single machine scheduling problem with sequence dependent setup times and overtime
Doç. Dr. Hakan Gültekin
Industrial Engineering, TOBB ETU
Nov 24, Friday 13:40
EA-409
Abstract
We consider a real-world application in which a single machine produces multiple job types. Each job has a specific deadline, which must be satisfied. Job transitions on the machine requires sequence dependent setup times. Each production day includes a cetain regular time and an overtime period. Although the production cost on in an overtime period is higher than that of a regular time period, they may still be required to satisfy the job deadlines. The objective is to determine a production schedule that minimizes the total overtime. The available overtime periods are defined at the end of each day. For this problem we first developed a mixed integer programming formulation. However, the solution times increases rapdly with the problem size and it becomes intractable for real-world instances. Therefore, we developed a logic-based Benders decomposition algorithm, which decomposes the original problem to a daily assignment problem and a number of sequnecing subproblems based on the 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. We also developed a simulated annealing algorithm to obtain “good” feasible solutions for larger instances. The performances of the developed solution approaches are tested through experimental studies.
Brief bio of the speaker
Hakan Gultekin is an Associate Professor at the Department of Industrial Engineering at TOBB University of Economics and Technology in Ankara, Turkey. He received his BS, MS and PhD degrees in Industrial Engineering from Bilkent University in Turkey. Before joining TOBB ETU, he visited the University of Liege in Belgium for postdoctoral studies. His research interests include scheduling, optimization modeling, and exact and heuristic algorithm development, especially for problems arising in modern manufacturing systems, energy systems, and wireless sensor networks.
