Article ID: | iaor20051739 |
Country: | Netherlands |
Volume: | 155 |
Issue: | 2 |
Start Page Number: | 439 |
End Page Number: | 454 |
Publication Date: | Jun 2004 |
Journal: | European Journal of Operational Research |
Authors: | Wilson James R., King Russell E., Wilson Amy D. |
Keywords: | heuristics |
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 achieveable 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.