A HEURISTIC METHOD FOR MULTI-PRODUCT VARIABLE LOT STREAMING IN A FLOW SHOP

ABSTRACT

The multi-product variable lot streaming (MPVLS) in a flow shop is to determine product sequence, to determine the machines to reallocate lot streaming for each product in the sequence, and to determine lot streaming for each machine, in order to minimize makespan for producing all products. In this paper, MPVLS is decomposed into three sub-problems: product sequence determination, lot streaming reallocation machine determination, and lot streaming range determination. After the combination of product sequence, lot streaming reallocation machines, and lot streaming ranges is determined, a mathematical formulation (Linear Programming, LP) for MPVLS with the specific combination information is developed and solved by LINDO. Since the search for all possible combinations is an NP problem, a heuristic method is proposed to solve the problem. First of all, an initial solution for MPVLS with a specific combination is determined. Then a hybrid heuristic combining tabu search (TS) with simulated annealing (SA) is used to improve the initial solution by searching for better combinations. The proposed heuristic method is tested and evaluated via simulation. The results show the proposed heuristic method is better than those existing methods in terms of average makespan deviation.

Keywords:

• heuristic method
• multi-product variable lot streaming (MPVLS)
• NP problem
• hybrid heuristic
• tabu search
• simulated annealing