A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem

A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor19991195
Country: Netherlands
Volume: 96
Issue: 3
Start Page Number: 578
End Page Number: 590
Publication Date: Feb 1997
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: branch and bound
Abstract:

This paper considers an m-machine permutation flowshop scheduling problem of minimizing the makespan. This classical scheduling problem is still important in modern manufacturing systems, and is well known to be intractable (i.e., NP-hard). In fact branch-and-bound algorithms developed so far for this problem have not come to solve large scale problem instances with over a hundred jobs. In order to improve the performance of branch-and-bound algorithms this paper proposes a new dominance relation by which the search load could be reduced, and notices that it is based on a sufficient precondition. This suggests that the dominance relation holds with high possibility even if the precondition approximately holds, thus being more realistic. The branch-and-bound algorithm proposed here takes advantage of this possibility for obtaining an optimal solution as early as possible in the branch-and-bound search. For this purpose this paper utilizes membership functions in the context of the fuzzy inference. Extensive numerical experiments that were executed through Monte Carlo simulations and benchmark tests show that the developed branch-and-bound algorithm can solve 3-machine problem instances with up to 1000 jobs with probability of over 99%, and 4-machine ones with up to 900 jobs with over 97%.

Reviews

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