IE-OPIM Joint Seminar 19 November 2014 at 13.40 at FENS G035
A Strong Formulation for Minsum Scheduling Problems on Unrelated Parallel Machines
Kerem Bülbül, Sabanci University
Joint work with Halil Şen
Research on minsum scheduling problems -- with due date oriented objectives in particular -- is at best scarce compared to objectives such as minimizing the makespan. Moreover, almost all existing work in this area is focused on the identical parallel machine environment, and the vast majority of the exact solution approaches have a dismal computational performance due to the difficulty of devising tight lower bounds. In the first part of this research, we leverage on our previous work on the single machine total weighted tardiness (TWT) and total weighted earliness/tardiness (TWET) problems and develop a new preemptive relaxation for the TWT and TWET problems on a bank of unrelated parallel machines. Our key contribution is devising a computationally effective Benders decomposition algorithm for solving the preemptive relaxation formulated as a mixed integer linear program. The optimal solution of the preemptive relaxation provides a tight lower bound. Moreover, it offers a near-optimal partition of the jobs to the machines, and then we exploit recent advances in solving the non-preemptive single machine TWT and TWET problems for constructing non-preemptive solutions of high quality to the original problem. We demonstrate the effectiveness of our approach with instances up to 5 machines and 200 jobs.
In the second part, we recognize and prove that the same preemptive relaxation gives rise to an exact formulation for minimizing the total weighted completion time (TWCT) on unrelated parallel machines. Furthermore, we exploit the structural properties of TWCT and attain major speedups in the Benders decomposition algorithm. Computationally, this approach holds great promise and may even be embedded into iterative algorithms for more complex shop scheduling problems as instances with up to 1000 jobs and 8 machines are solved to optimality within a few seconds.
Kerem Bülbül is an Associate Professor at the Manufacturing Systems and Industrial Engineering program at Sabancı University, Istanbul-Turkey. He received his BS degree in Industrial Engineering from Boğaziçi University, Istanbul, in 1996, and then his MS and PhD degrees in Industrial Engineering & Operations Research from the University of California at Berkeley in 1997 and 2002, respectively. He worked for a year as a client consultant at Rapt Inc. who used to develop decision support systems for pricing highly configurable products before joining Sabanci University in September 2003. His current research interests include deterministic and stochastic machine scheduling problems, mathematical programming with an emphasis on the computational aspects, and airline crew scheduling.