A computational study with a new algorithm for the three-machine permutation flow-shop problem with release times

A computational study with a new algorithm for the three-machine permutation flow-shop problem with release times

0.00 Avg rating0 Votes
Article ID: iaor20013914
Country: Netherlands
Volume: 130
Issue: 3
Start Page Number: 559
End Page Number: 575
Publication Date: May 2001
Journal: European Journal of Operational Research
Authors: , ,
Keywords: computational analysis
Abstract:

We consider the three-machine permutation flow-shop scheduling problem with release times where the objective is to minimize the maximum completion time. A special solvable case is found for the F2/rj/Cmax problem, which sharpens the boundary between easy and hard cases and can be used to compute a tight lower bound for our problem. Two dominance rules are generalized and applied to generating initial schedules, directing the search strategy and decomposing the problem into smaller ones. The branch and bound algorithm proposed here combines an adaptive branching rule with a fuzzy search strategy to narrow the search tree and lead the search to an optimal solution as early as possible. Our extensive numerical experiments have led to a classification of ‘easy’ vs. ‘hard’ problems, dependent only on the relative size of the release times. The algorithm has quickly solved approximately 90% of the hardest test problem instances with up to 200 jobs and 100% of the large problems classified as easy.

Reviews

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