A Computational Study of Shifting Bottleneck Procedures for Shop Scheduling Problems

A Computational Study of Shifting Bottleneck Procedures for Shop Scheduling Problems

0.00 Avg rating0 Votes
Article ID: iaor20118423
Volume: 3
Issue: 2
Start Page Number: 111
End Page Number: 137
Publication Date: Nov 1997
Journal: Journal of Heuristics
Authors: , ,
Keywords: heuristics
Abstract:

We examine the performance of Shifting Bottleneck (SB) heuristics for shop scheduling problems where the performance measure to be minimized is makespan (C max) or maximum lateness (L max). Extensive computational experiments are conducted on benchmark problems from the literature as well as several thousand randomly generated test problems with three different routing structures and up to 1000 operations. Several different versions of SB are examined to determine the effect on solution quality and time of different subproblem solution procedures, reoptimization procedures and bottleneck selection criteria. Results show that the performance of SB is significantly affected by job routings, and that SB with optimal subproblem solutions and full reoptimization at each iteration consistently outperforms dispatching rules, but requires high computation times for large problems. High quality subproblem solutions and reoptimization procedures are essential to obtaining good solutions. We also show that schedules developed by SB to minimize L max perform well with respect to several other performance measures, rendering them more attractive for practical use.

Reviews

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