HALİL ŞEN-PhD Dissertation
  • FENS
  • HALİL ŞEN-PhD Dissertation

You are here

CUT GENERATION BASED ALGORITHMS FOR UNRELATED PARALLEL MACHINE SCHEDULING PROBLEMS

 

 

HALİL ŞEN
Industrial Engineering, PhD Dissertation, 2015

 

Thesis Jury

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

 

Abstract

 

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.