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

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

10.29977/JCIIE.200601.0007

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

探索解 ； 多產品變動轉運批 ； NP問題 ； 混合式探索解 ； 禁忌搜尋法 ； 模擬退火法 ； heuristic method ； multi-product variable lot streaming MPVLS ； NP problem ； hybrid heuristic ； tabu search ； simulated annealing

工業工程學刊

23卷1期（2006 / 01 / 01）

65 - 79

英文

流程型生產系統下多產品變動轉運批問題主要決定產品處理順序、轉運站及批量以使總製造時問最短。本文將此問題分為三個子問題：決定產品處理順序、決定轉運站、決定批量範圍，在此三資訊確定後，建立一線性規劃數學模式決定其總製造時間。因搜尋所有可能的組合屬於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.

1. Liu, S. C.,T. S. Liu(2003).A model structure and solution procedures for variable sublots of a single product.Journal of Chinese Institute of Industrial Engineers,20,553-564.
   連結：
2. Aarts, E. H. L.,J. Korst(1989).Simulated Annealing and Boltzmann Machines, John Wiley & Sons Publishers
3. Aldaihani, M. M. M. Dessouky(2003).Hybrid scheduling methods for paratransit operations.Computers and Industrial Engineering
4. Baker, K. R.,D. Jia(1993).A comparative study of lot streaming procedure.Omega
5. 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.
6. Glover, F.(1977).A statistical approach to the TSP.Networks.
7. Glover, F.,M. Laguna(1997).Tabu Search.Kluwer Academic Publishers.
8. Greistorfer, P.(2003).A tabu scatter search metaheuristic for the arc routing problem.Computers and Industrial Engineering
9. Kalir, A. A.,S. C. Sarin(2000).Evaluation of the potential benefits of lot streaming in flow-shop systems.International Journal of Production Economics,66,31-142.
10. Kirkpatrick, S., C. D. Gelatt,,M. P. Vecchi(1983).Optimization by simulated annealing.Science
11. Kumar, S., T. P. Bagchi,C. Sriskandarajah(2000).Lot streaming and scheduling heuristics for rn-machine no wait flowshop.Computers and Industrial Engineering,38,49-172.
12. Liu, S. C.(2003).A heuristic method for discrete lot streaming with variable sublots in a flow shop.International Journal of Advanced Manufacturing Technology,22,662-668.
13. Liu, S. C.,E. C. Chen(2003).A variable lot streaming for multiple products.The 7th International Conference of Decision Sciences Institute,Shanghai, China:
14. Méndez, C. A., G P. Henning,J. Cerdá(2000).Optimal scheduling of batch plants satisfying multiple product orders with different due-dates.Computers and Chemical Engineering
15. Rajendran, C.(1995).Heuristics for scheduling in flow-shop with multiple objectives.European Journal of Operational Research,82,540-555.
16. Ramasesh, R. V., H. Fu, D. K. H. Fong,J. C. Hayya(2000).Lot streaming in multistage production sys tern.International Journal of Production Economics,66,199-211.
17. Reeves, C. R.(1995).Modern Heuristic Techniques for Combinatorial Problems, McGraw Hill.
18. Skiscim, C. C.,B. L. Golden(1983).Optimization by simulated annealing: a preliminary computational study for the TSP.Proceedings of the 1983 Winter Simulation Conference, Washington, D. C.
19. Sriskandarajah, C.,E. Wangeur(1999).Lot streaming and scheduling multiple products in two-machine no-wait flowshops.IIE Transactions.
20. Tian, P. M. J.,D. M. Zhang(1999).Application of the simulated annealing algorithm to the combinatorial optimization problem with permutation property: an investigation of generation mechanism.European Journal of Operational Research,118,81-94.
21. Trietsch, D.,K. R. Baker(1993).Basic techniques for lot streaming.Operations Research