テクノロジーと最適化のグローバル ジャーナル

Manipulation of Tabu List to Handle Machine Breakdowns in Job Shop Scheduling Problems

Abstract

Erna Budhiarti Nababan 1 , Opim Salim Sitompul2 , Salwani Abdullah3  

Machine breakdowns in a production schedule may occur on a random basis that make hard combinatorial problem of Job Shop Scheduling Problems (JSSP) becomes more complex. In this paper a new algorithm Fuzzy Tabu Priority List (FTPL) is proposed. Tabu search technique is applied to search optimal solution whereas FTPL is used to handle machine breakdowns. There are two tabu lists employed: one to keep moves during searching for optimal solution, another one is to keep broken machine if breakdown occurs. Period of how long the machine will be kept on the list is determined by fuzzy membership function. In order to avoid solution of being trapped into a local optimum Monte Carlo acceptance criterion is applied. Our techniques are tested to the benchmark data of JSSP available on the Operation Research library. From the experiment, we found that our algorithm is promising to help a decision maker to face the event of machine breakdowns.