A BRANCH-AND-BOUND ALGORITHM WITH FUZZY INFERENCE FOR A PERMUTATION FLOWSHOP SCHEDULING PROBLEM

This paper considers an m-machine permutation flowshop scheduling prob lem of minimizing the makespan. This classical scheduling problem is s till important in modem manufacturing systems, and is well known to be intractable (i.e., NP-hard). In fact branch-and-bound algorithms deve loped so far for this problem have not come to solve large scale probl em instances with over a hundred jobs. In order to improve the perform ance of branch-and-bound algorithms this paper proposes a new dominanc e relation by which the search load could be reduced, and notices that it is based on a sufficient precondition. This suggests that the domi nance relation holds with high possibility even if the precondition ap proximately holds, thus being more realistic. The branch-and-bound alg orithm proposed here takes advantage of this possibility for obtaining an optimal solution as early as possible in the branch-and-bound sear ch. For this purpose this paper utilizes membership functions in the c ontext of the fuzzy inference. Extensive numerical experiments that we re executed through Monte Carlo simulations and benchmark tests show t hat the developed branch-and-bound algorithm can solve 3-machine probl em instances with up to 1000 jobs with probability of over 99%, and 4- machine ones with up to 900 jobs with over 97%.