無暫存區分派式流程型工廠排程

Distributed Flowshop Scheduling Problems with Blocking Constrain

吳建樺(Chien-Hua Wu)

指導教授 ： 應國卿

國立臺北科技大學/管理學院/工業工程與管理系碩士班/碩士(2013年)

摘要

普通的流程型工廠當中，會有許多的暫存區，放置正在等待加工的工件，但許多實務環境中不存在這些暫存區，例如化學工廠由於工件加工完畢可能需要等待化學或物理變化結束才能繼續加工，因此當工件被機器加工完成時，若要進入下一台機器加工，會停留在機器上等待，直到下一台機器加工完成前一個工件或是機器閒置，才能繼續加工，因此衍生出無暫存區流程型工廠的排程問題。流程型工廠一直都是排程研究的重點，隨著近年來加工環境的改變，慢慢的從單一工廠轉變為多工廠的趨勢，因此，本研究針對流程型排程問題加入了多工廠的分派及無暫存區的限制，以求解最小化總完工時間(makespan)為目標函數，並且結合NEH1演算法和和弦演算法(Harmony Search, HS)進行求解，經由標準測試題庫的模擬實驗結果證實，本研究提出的改良式和弦演算法之求解績效十分優異。

關鍵字

排程 ； 無暫存區 ； 分派式流程型工廠 ； 和弦演算法

並列摘要

Among the ordinary flow shop, there are many temporary storage area, place the workpiece is waiting, but many of these do not exist in practice environments temporary area. Therefore derive blocking flowshop scheduling problem.
Flowshop scheduling research has been focused, with the recent changes in the processing environment, from a single factory slowly transformed into the trend of many factories, therefore, this study assigned for the process factory to join the factors and blocking constrain. The optimization criterion is the minimization of the maximum completion time, and use the harmony search algorithm (HS) as a solution based on adding NEH1 algorithm concepr to slove it. The computational result show that the study proposes a modified harmony search algorithm very excellent performance of the proposed.

並列關鍵字

Scheduling ； Blocking ； Distributed flowshop ； Harmony search

參考文獻

R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, "Optimization and approximation in deterministic sequencing and scheduling: a survey," Annals of Discrete Mathematics, 1979, pp. 287-325.

S. M. Johnson, "Optimal two and three-stage production schedules with setup times included, " Naval Research Logistics Quarterly, vol. 1, no. 1, 1954, pp. 61-68.

D. S. Palmer, "Sequencing jobs through a multi-stage process in the minimum total time: a quick method of obtaining a near optimum," Operational Research Quarterly, vol. 16, no. 1, 1965, pp. 101-107.

H. G. Campbell, R. A. Dudek and M. L. Smith, "Heuristic algorithm for N-job, M-machine sequencing problem," Management Science Series Application, vol. 16, no. 10, 1970, pp. 630-637.

R. Ruiz and C. Maroto, "A comprehensive review and evaluation of permutation flowshop heuristics," European Journal of Operational Research, vol. 165, no. 2, 2005, pp. 479-494.