Local search algorithms for flow shop scheduling with fuzzy due dates

This paper formulates a fuzzy flow shop scheduling problem where the due-date of each job is given as a fuzzy set. The membership function of the fuzzy due-date corresponds to the grade of satisfaction of a completion time. The objective function of the formulated problem is to maximize the minimum grade of satisfaction over given jobs. Several local search algorithms including multi-start descent, simulated annealing and taboo search algorithms are applied to the problem. The performance of each algorithm is compared with one another by computer simulations on randomly generated test problems. It is shown by simulation results that some algorithms do not work well for the fuzzy flow shop scheduling problem. Thus, a new approach is proposed by changing the objective function. The effectiveness of this approach is demonstrated by computer simulations.