臺灣博碩士論文加值系統

普通的流程型工廠當中，會有許多的暫存區，放置正在等待加工的工件，但許多實務環境中不存在這些暫存區，例如化學工廠由於工件加工完畢可能需要等待化學或物理變化結束才能繼續加工，因此當工件被機器加工完成時，若要進入下一台機器加工，會停留在機器上等待，直到下一台機器加工完成前一個工件或是機器閒置，才能繼續加工，因此衍生出無暫存區流程型工廠的排程問題。流程型工廠一直都是排程研究的重點，隨著近年來加工環境的改變，慢慢的從單一工廠轉變為多工廠的趨勢，因此，本研究針對流程型排程問題加入了多工廠的分派及無暫存區的限制，以求解最小化總完工時間(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.

摘　要 i
ABSTRACT ii
誌 謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究假設與限制 2
1.4 研究流程 3
第二章 文獻探討 5
2.1 分派式流程型工廠 5
2.2無暫存區流程型工廠之相關文獻 6
2.3和弦演算法 8
2.3.1 和弦演算法發展背景及基本原理 9
2.3.2和弦演算法之步驟與流程 11
2.3.3 和弦演算法之相關應用 16
第三章 研究方法 18
3.1數學符號之定義 18
3.2無暫存區分派式流程型工廠問題之MILP模式 19
3.3分派工件至各個工廠法則 21
3.4修正和弦演算法之設計 22
3.4.1初始排序之建構方法 24
3.4.2和弦演算法之編碼 24
3.4.3和弦演算法之新排序產生方法 25
第四章 實驗結果與分析 27
4.1 小型問題求解績效 27
4.2 中型問題求解績效 34
4.3 大型問題求解績效 39
第五章 結論與建議 46
5.1 結論 46
5.2 研究貢獻 46
5.3未來研究建議 47
參考文獻 48

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.
M. Nawaz, Enscore, Jr. E. E. and I. Ham, "A heuristic algorithm for the m machine, n job flowshop sequencing problem," Omega-International Journal of Management Science, vol. 11, no. 1, 1983, pp. 91-95.
J. M. Framinan, R. Leisten and C. Rajendran, "Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem,"International Journal of Production Research, vol. 41, no. 1, 2003, pp. 121-148.
X. Y. Dong, H. K. Huang and P. Chen, "An improved NEH-based heuristic for the permutation flowshop problem," Computers & Operations Research, vol. 35, no. 12, 2008, pp. 3962-3968.
S. F. Rad, R. Ruiz and N. Boroojerdian, "New high performing heuristics for minimizing makespan in permutation flowshops," Omega-International Journal of Management Science, vol. 37, no. 2, 2009, pp. 331-345.
P. J. Kalczynski and J. Kamburowski, "An empirical analysis of the optimality rate of flow shop heuristics," European Journal of Operational Research, vol. 198 , no. 1, 2009, pp. 93-101.
J. Grabowski and M. Wodecki, "A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion, " Computers & Operations Research, vol. 31, no. 11, 2004, pp. 1891-1909.
E. Nowicki and C. Smutnicki, "A fast tabu search algorithm for the permutation flow-shop problem," European Journal of Operational Research, vol. 91, No. 1, 1996, pp. 160-175.
C. R. Reeves, "A genetic algorithm for flowshop sequencing," Computers & Operations Research, vol. 22, no. 1, 1995, pp. 5-13.
R. Ruiz, C. Maroto and J. Alcaraz, "Two new robust genetic algorithms for the flowshop scheduling problem," Omega-International Journal of Management Science , vol. 34 , no. 5, 2006, pp. 461-476.
M. F. Tasgetiren, Y. C. Liang, M. Sevkli and G. Gencyilmaz, "A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem," European Journal of Operational Research, vol. 177, no. 3, 2007, pp. 1930-1947.
I. H. Osman and C. N. Potts, "Simulated annealing for permutation flowshop scheduling," Omega-International Journal of Management Science, vol. 17, no. 6, 1989, pp. 551-557.
C. Rajendran and H. Ziegler, "Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs," European Journal of Operational Research, vol. 155, no. 2, 2004, pp. 426-438.
E. Nowicki and C. Smutnicki, "Advanced Tabu Search Algorithm for the Job Shop Propblem,” Journal of Scheduling, vol. 8, no. 2, 2005, pp. 145-159.
R. Ruzi and T. Stu ?tzle, "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, vol. 177, no. 3, 2007, pp. 2033-2049.
E. Vallada and R. Ruzi, "Cooperative metaheuristics for the permutation flowshop scheduling problem," European Journal of Operational Research, vol. 193 , no. 2, 2009, pp. 367-376.
B. Wang, "Integrated product, process and enterprise design," 1st ed edition, Chapman & Hall, London, 1997.
K. B. Kahn, G. A. Castellion and A. Griffin, "The PDMA Handbook of New Product Development," Second edition, Wiley, New York, 2004.
H. Z. Jia, J. Y. H. Fuh, A. Y. C. Nee and Y. F. Zhang, "Web-based multi-functional scheduling system for a distributed manufacturing environment," Concurrent Engineering-Research and Applications, vol. 10, No. 1, 2002, pp. 27-39.
H. Z. Jia, A. Y. C. Nee, J. Y. H. Fuh and Y. F. Zhang, "A modified genetic algorithm for distributed scheduling problems," Journal of Intelligent Manufacturing, vol. 14, no. 3, 2003, pp. 351-362.
H. Z. Jia, J. Y. H. Fuh, A. Y. C. Nee and Y. F. Zhang, "Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems," Computers & Industrial Engineering, vol. 53, no. 2, 2007, pp. 313-320.
F. T. S. Chan, S. H. Chung and P. L. Y. Chan, "An adaptive genetic algorithm with dominated genes for distributed scheduling problems," Expert Systems with Applications, vol. 29, no. 2, 2005, pp. 364-371.
F. T. S. Chan, S. H. Chung, L. Y Chan, G. Finke and M. K. Tiwari, "Solving distributed FMS scheduling problems subject to maintenance: genetic algorithms approach," Robotics and Computer-Integrated Manufacturing vol. 22, no. 5-6, 2006, pp. 493-504.
L. Wang, W. Shen, "Process planning and scheduling for distributed manufacturing," London: Springer; 2007.
R. Storn and K. Price, "Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces," Journal of Global Optimization, vol. 11, 1997, pp. 341-359.
A. Allahverdi, C. T. Ng and T. C. E. Cheng, "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, vol. 187, 2008, pp. 985-1032.
S. T. McCormich, M. L. Pinedo, S. Shenker and B. Wolf, "Sequencing in an assembly line with blocking to minimize cycle time," Operations Research, vol. 37, 1989, pp. 925-936.
R. Leisten, "Flowshop sequencing problems with limited buffer storage,"
International Journal of Production Research, vol. 28, 2009, pp. 2085-2100.
D. P. Ronconi, "A note on constructive heuristics for the flowshop problem with blocking," International Journal of Production Economics, vol. 87, 2004, pp. 39-48.
I. N. K. Abadi, N. G. Hall and C. Sriskandarajh, "Minimizing cycle time in a blocking flowshop," Operations Research, vol. 48, 2000, pp. 177-180.
D. P. Ronconi and L. R. S Henriques, "Some heuristic algorithms for total tardiness minimization in a flowshop with blocking," Omega - International Journal of Management Science, vol. 37 , no. 2,2009, pp. 272-281.
V. Caraffa, S. lanes, T.P Bagchi and C. Sriskandarajah, "Minimizing makespan in a blocking flowshop using genetic algorithms," International Journal of Production Economics, vol. 70, 2001, pp. 102-115.
M. Nawaz, E. E. J. Enscore and I. Ham, "A heuristic algorithm for them-machine, n-job flow shop sequencing problem," International Journal of Management Science, vol. 11, 1983, pp. 91-95.
D. P. Ronconi, "A branch-and-bound algorithm to minimize the makespan in a flowshop problem with blocking," Annals of Operations Research, vol. 138, no. 1, 2005, pp. 53-65.
J. Grabowski and J. Pempera, "The permutation flow shop problem with blocking. A tabu search approach," Omega-International Journal of Management Science, vol. 35, 2007, pp. 302-311.
Z. W. Greem, J. H. Kim and G. V. Loganathan, "A new heuristic optimization algorithm: harmony search," Simulations, vol. 76, 2001, pp. 60-68.
L. Wang, L. Zhang and D. Z. Zheng, "An effective genetic algorithm for flow shop scheduling with limited buffers," Computers & Operations Research, vol. 33, 2001, pp. 2960-2971.
B. Liu, L. Wang and Y. H. Jin, "An effective PSO-based algorithm for flow shop scheduling," Computers & Operations Research, vol. 35, pp. 2791-2806.
I, Ribas, R, Companys and X. Tort-Martorell, "An iterated greedy algorithm for the flowshop scheduling problem with blocking," Omega-International Journal of Management Science, vol. 39, pp. 293-301.
Z. W. Geem, J. H. Kim and G.V. Loganathan, "A New Heuristic Optimization Algorithm: Harmony Search," Society for Modeling and Simulation Interational, vol. 76, no. 2, 2001, pp. 60-68.
S. Kirkpatrick, C. Gelatt, and M. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, no. 4598, 1983, pp. 671-680.
F. Glover and R. Marti, "Tabu Search," Operations Research/Computer Science Interfaces Series, vol. 36, no. 2, 2006, pp. 53-69.
R. Ruzi, C. Maroto, and J. Alcaraz, "Two new robust genetic algorithm for the flowshop scheduling problem," Omega-International Journal of Management Science, vol. 34, no. 5, 2006, pp. 461-476.
C. Rajendran and H. Ziegler, "Ant-colony algorithm for permutation flowshop scheduling to minimize makespan/total flowtime of jobs," European Journal of Operational Research, vol. 155, no. 2, 2004, pp. 426-438.
M. F. Tasgetiren, Y. C. Liang, M. Sevkli and G. Gencyilnaz," A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem," European Journal of Operational Research, vol. 177, no. 3, 2007, pp. 1930-1947.
Z. W. Geem, J. H. Kim, and G. V. Loganathan, "A new heuristic optimization algorithm: harmony search, " Simulation, vol. 76 , no. 2, 2001, pp. 60-68.
M. G. H. Omean and M. Mahdavi, "Global-best harmony search," Applied athematics and Computation, vol. 198, 2008, pp. 643-656.
Q. K. Pan, P. N. Suganthan, J. J. Liang and M. Faith Tasgetiren, "A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flowshop scheduling problem," Expert Systems with Applications, vol. 38, 2010, pp. 1-8.
K. Z. Gao, H. Li, Q. K. Pan, J. Q. Li and J. J. Liang, "Hybrid heuristic based on harmony search to minimize total flow time in no-wait flow shop," Control and Decision Conference, 2010, pp. 1184-1188.
B. Naderi and R. Ruiz, "The distributed permutation flowshop scheduling problem," Computers & Operations Research, vol. 37, no. 4, 2010, pp. 754-768.
Q. K. Pan and L. Wang, "Effective heuristics for the blocking flowshop scheduling problem with makespan minimization," Omega-International Journal of Management Science, vol. 37, no. 40, 2012, pp. 218-229.
L. Wang, Q. K. Pan and M. F. Tasgetiren, "Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithma," Expert systems with Applications, vol. 37, no. 12, 2010, pp. 7929-7936.