Case study on statistically estimating minimum makespan for flow line scheduling problems

Case study on statistically estimating minimum makespan for flow line scheduling problems

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics
Abstract:

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.

Reviews

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