A Heuristic Method for Multi-Product Variable Lot Streaming in a Flow Shop

在流程型生產系統中多產品變動轉運批模式之研究

劉書助(Shu-Chu Liu) ； 陳英彰(En-Chang Chen) ； 劉浩天(H. T. Liu)

《工業工程學刊》 23卷1期 (2006/01) Pp. 65-79

https://doi.org/10.29977/JCIIE.200601.0007

摘要

流程型生產系統下多產品變動轉運批問題主要決定產品處理順序、轉運站及批量以使總製造時問最短。本文將此問題分為三個子問題：決定產品處理順序、決定轉運站、決定批量範圍，在此三資訊確定後，建立一線性規劃數學模式決定其總製造時間。因搜尋所有可能的組合屬於NP問題，故提出一混合式探索解，經模擬驗證本研究所提之探索解優於其它現存的方法。

關鍵字

探索解 ； 多產品變動轉運批 ； NP問題 ； 混合式探索解 ； 禁忌搜尋法 ； 模擬退火法

並列摘要

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.

並列關鍵字

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

參考文獻

Aarts, E. H. L.,J. Korst(1989).Simulated Annealing and Boltzmann Machines, John Wiley & Sons Publishers.(Simulated Annealing and Boltzmann Machines, John Wiley & Sons Publishers).

Aldaihani, M. M. M. Dessouky(2003).Hybrid scheduling methods for paratransit operations.Computers and Industrial Engineering.(Computers and Industrial Engineering).

Baker, K. R.,D. Jia(1993).A comparative study of lot streaming procedure.Omega.(Omega).

EL-Najdawi, M. K.(1994).Job-splitting heuristic for lot-size scheduling in multi-product production processes.European Journal of Operational Research.75,365-377.

Glover, F.,M. Laguna(1997).Tabu Search.(Kluwer Academic Publishers).