Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound

Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound

0.00 Avg rating0 Votes
Article ID: iaor20002752
Country: Netherlands
Volume: 117
Issue: 2
Start Page Number: 396
End Page Number: 413
Publication Date: Sep 1999
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: probabilistic, programming: branch and bound
Abstract:

A stochastic branch-and-bound technique for the solution of stochastic single-machine-tardiness problems with job weights is presented. The technique relies on partitioning the solution space and estimating lower and upper bounds by sampling. For the lower bound estimation, two different types of sampling (‘within’ and ‘without’ the minimization) are combined. Convergence to the optimal solution (with probability one) can be demonstrated. The approach is generalizable to other discrete stochastic optimization problems. In computational experiments with the single-machine-tardiness problem, the technique worked well for problem instances with a relatively small number of jobs; due to the enormous complexity of the problem, only approximate solutions can be expected for a larger number of jobs. Furthermore, a general precedence rule for the single-machine scheduling of jobs with uncertain processing times has been derived, essentially saying that ‘safe’ jobs are to be scheduled before ‘unsafe’ jobs.

Reviews

Required fields are marked *. Your email address will not be published.