CUT GENERATION BASED ALGORITHMS FOR UNRELATED PARALLEL MACHINE SCHEDULING PROBLEMS
Industrial Engineering, PhD Dissertation, 2015
Assoc. Prof. Dr. Kerem Bülbül (Dissertation Supervisor)
Assoc. Prof. Dr. Özgür Çetin
Prof. Dr. Ceyda Oğuz
Assoc. Prof. Dr. Z. Caner Taşkın
Prof. emer. Dr. Gündüz A. Ulusoy
Date & Time: 07 / 21 / 2015 – 14:40
Place: FENS 2008
Keywords: scheduling, unrelated parallel machines, Benders decomposition, exact, heuristics
Research on scheduling in the unrelated parallel machine environment is at best scarce. Moreover, almost all existing work in this area is focused on the minimization of completion time related performance measures and the solution approaches available in the literature suffer from scalability issues. In this dissertation, we leverage on the success of the mathematical programming based decomposition approaches and devise scalable, efficient, and effective cut generation based algorithms for one ordinary and three strongly NP-hard unrelated parallel machine scheduling problems.
In the first part, we develop a new preemptive relaxation for the total weighted tardiness and total weighted earliness/tardiness problems and devise a Benders decomposition algorithm for solving this preemptive relaxation formulated as a mixed integer linear program. We demonstrate the effectiveness of our approach with instances up to 5 machines and 200 jobs.
The second part deals with the problem of minimizing total weighted completion time and proves that the preemptive relaxation developed in part one is an exact formulation for this problem. By exploiting the structural properties of the performance measure, we attain an exact Benders decomposition algorithm which solves instances with up to 1000 jobs and 8 machines to optimality within a few seconds.
In the last part, we tackle the unrestricted common due date just-in-time scheduling problem and develop a logic based Benders decomposition algorithm. Aside from offering the best solution approach for this problem, we demonstrate that it is possible to devise scalable logic based algorithms for scheduling problems with irregular minsum objectives.