Case study on statistically estimating minimum makespan for flow line scheduling problems
- Resource Type
- Article
- Authors
- Wilson, Amy D.; King, Russell E.; Wilson, James R.
- Source
- European Journal of Operational Research. Jun2004, Vol. 155 Issue 2, p439. 16p.
- Subject
- *HEURISTIC programming
*PRODUCTION scheduling
COMBINATORIAL optimization
LEAST squares
WEIBULL distribution
GOODNESS-of-fit tests
- Language
- ISSN
- 0377-2217
Lower bounds are typically used to evaluate the performance of heuristics for solving combinatorial minimization problems. In the absence of tight analytical lower bounds, optimal objective-function values may be estimated statistically. In this paper, extreme value theory is used to construct confidence-interval estimates of the minimum makespan achievable when scheduling nonsimilar groups of jobs on a two-stage flow line. Experimental results based on randomly sampled solutions to each of 180 randomly generated test problems revealed that (i) least-squares parameter estimators outperformed standard analytical estimators for the Weibull approximation to the distribution of the sample minimum makespan; (ii) to evaluate each Weibull fit reliably, both the Anderson–Darling and Kolmogorov–Smirnov goodness-of-fit tests should be used; and (iii) applying a local improvement procedure to a large sample of randomly generated initial solutions improved the probability that the resulting Weibull fit yielded a confidence interval covering the minimum makespan. [Copyright &y& Elsevier]