MINIMIZING VALUE-AT-RISK IN SINGLE MACHINE SCHEDULING PROBLEMS
Industrial Engineering, Master’s Thesis, 2012
Asst. Prof. Kerem Bülbül (Thesis Supervisor), Asst. Prof. Nilay Noyan Bülbül Bülbül (Thesis co-supervisor), Prof. Dr. Gündüz Ulusoy, Asst. Prof. Kemal Kılıç, Prof. Dr. Ali Rana Atılgan
Date &Time: August 6th, 2012 – 15:00
Place: FENS L056
Keywords: single-machine; stochastic processing times; stochastic scheduling; value-at-risk; probabilistic constraint; stochastic programming; scenario decomposition; cut-generation; dual stabilization; parallel programming
The vast majority of the machine scheduling literature focuses on deterministic problems in which all data is known with certainty a priori. This may be a reasonable assumption when the variability in the problem parameters is low. However, as variability in the parameters increases incorporating this uncertainty explicitly into a scheduling model is essential to mitigate the resulting adverse effects. In this thesis, we consider single-machine scheduling problems in the presence of uncertain problem parameters. We impose a probabilistic constraint on the random performance measure of interest (such as the total completion time, total weighted completion time, and total weighted tardiness), and introduce a generic risk-averse stochastic programming model. In particular, the objective of the proposed model is to find a non-preemptive static job processing sequence that minimizes the value-at-risk (VaR) of the random performance measure at a specified confidence level. In this study, we propose a Lagrangian relaxation based decomposition strategy to obtain tight lower and upper bounds. In order to solve the Lagrangian dual problem we provide a stabilized cut-generation algorithm. We also present an extensive computational study on three selected performance measures to demonstrate the effectiveness of our solution methods and the value of the proposed model.