臺灣博碩士論文加值系統

流程型生產排程問題(Permutation Flowshop Scheduling Problem; PFSP)為生產製造的重要問題，流程型工廠排程問題中，決策者為了達成提昇系統績效之目標，除了要使產出時間儘量降低之外，還必需同時考慮使在製品庫存水準儘量降低、機器稼動率以及準時達交。
本研究主要在探討n件工作m台機器之流程型生產問題，並使用二元整數作為混合整數線性規劃之整數變數。大多數的生產排程問題都在探討單一準則，然而排程問題常常有多方面的考量與分析之多準則分析。在本研究中，考慮n件工作m台機器之多準則流程型生產問題。其追求目標函數分別為：即最大完工時間(Makespan)、總完成時間(Total Complete Time)、總延遲時間(Total Tardiness Time)、最大延遲時間( )、總機器閒置時間(Total Machine Idle Time)以及總工作等待時間(Total Job Wait Time)。
本研究首先建構MPFSP的混合整數規劃(MILP)數學模型，然後以LINGO套裝軟體進行模型編碼，最後由LINGO套裝軟體求解。為驗證所提出之MILP模式的求解績效，本研究將以文獻提供的標準題庫進行測試，結果顯示本研究之所提出的MPFSP最佳化生產排程模式之求解績效十分良好，可供相關業者生產排程之參考，藉以提升企業的競爭力與獲利能力。

Permutation Flowshop Scheduling Problem (PFSP) is an important issue in manufacturing. To improve the system performance, the decision makers need to reduce process time and inventory level, enhance ratio of utilization, and delivery on time.
The problem of an n-job, m-machine Flowshop Scheduling Problem is discussed. A mixed-integer linear program (MILP) is formulated with considerably reduced number of integer binary variables.
Most of research in production scheduling is concerned with the minimization of a single criterion. However, scheduling problems often involve more than one aspect and therefore require multicriteria analysis. In this study, a multicriteria an n-job, m-machine flowshop scheduling problem is considered. The objective function of the problem is minimization of the makespan, total complete time, total tardiness time, maximum tardiness time, total machine idle time, and total job wait time.
This research first creates a mathematical MILP model of MPFSP, and then computes this model by LINGO. To validate the effectiveness of the proposed model, this research uses the earlier studies as benchmarks to compare with the result of this study. In the comparison result, it is appeared that the effectiveness of the proposed model is well, and it can be used as valuable reference for practitioners to improve their operational efficiency within a reasonable amount of computational effort.

目錄

摘　要 I
ABSTRACT II
致 謝 II
目錄 III
圖目錄 V
表目錄 VI
第一章　緒論 1
1.1 研究背景與動機 1
1.2 研究目的 1
1.3 研究範圍 2
1.4 問題描述及假設 2
1.5 研究方法與進行步驟 3
第二章　文獻探討 5
2.1流程型生產排程問題 5
2.2 多準則描述 9
2.3 混合整數規劃 10
第三章　研究方法 16
3.1數學符號之定義 16
3.2數學模型之定義 17
3.2.1工作在排列位置之二元整數限制式 17
3.2.2 工作指派在順序位置上的機器加工時間之限制式 17
3.2.3完成時間與加工時間之限制式 17
3.2.4機器閒置時間與工作等待時間之限制式 18
3.2.5工作到期日與工作延遲時間之限制式 19
3.2.6 八種目標函數 19
3.3八種目標函數之數學模型 20
第四章　結果分析 25
4.1 LINGO之B&B與SA對標準測試題庫運算比較 25
4.2 六種單準則函數之比較 26
4.3 二種不同權重的多準則函數之比較 28
4.4 機台數與工作數不同對於單準則與多準則之影響 31
第五章　結論與建議 39
5.1 結論 39
5.2 建議 40
參考文獻 42
附錄 46
附錄A：流程型生產排程問題之模擬退火法(SA)演算步驟 46
附錄B：符號彙編 47
附錄C：公式彙編 48
附錄D：LINGO編碼 49

[1]K. R. Baker and Wiley, "Introduction to Sequencing and Scheduling," New York, 1974.
[2]H. V. D. Parunak, "Characterizing the Manufacturing Scheduling Problem," Journal of Manufacturing Systems, Vol.. 10, No. 3, 1991, PP. 241–259.
[3]S. A. Brah and J. L. Hunsucker, "Branch and bound algorithm for the flow shop with multiple processors," European Journal Operational Research, Vol.. 51, No. 3, 1991, PP. 88–99.
[4]Z. A. Lomnicki, "A branch and bound algorithm for the exact solution of the three-machine scheduling problem," Operation Research Quarterly, Vol. 16, No.1, 1965, PP. 89–100.
[5]A. Allahverdi and F. S. Al-Anzi, "A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times," European Journal of Operational Research, Vol. 169, No. 3, 2006, PP. 767–780.
[6]R. Z. Ríos-Mercado and J. F. Bard, "Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups," Computers & Operations Research, Vol. 25, No. 5, 1998, PP. 351–366.R.
[7]Rajkumar and P. Shahabudeen., "Performance Evaluation of Simulated Annealing Algorithm for Flowshop Scheduling Problems," The International Journal of Applied Management and Technology, Vol. 5, No. 3, 2007, PP. 173–189.
[8]C. J. Liao, C. T. Tseng and P. Luarn, "A discrete version of particle swarm optimization for flowshop scheduling problems," Computers & Operations Research, Vol. 34, No. 10, 2007, PP. 3099–3111.
[9]O. Etiler, B. Toklu, M. Atak and J. Wilson, "A Genetic Algorithm for Flow Shop Scheduling Problems," The Journal of the Operational Research Society, Vol. 55, No. 8, 2004, PP. 830–835.
[10]C. R. Reeves, "A genetic algorithm for flowshop sequencing, " Computers & Operations Research, Vol. 22, No. 1, 1995, PP. 5–13.
[11]R. Ruiz and T. Stü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.
[12]T. P. Bagchia, J.N.D. Gupta and C. Sriskandarajah, "A review of TSP based approaches for flowshop scheduling," European Journal of Operational Research, Vol. 169, No. 3, 2006, PP. 816–854.
[13]B. Ekşioğlu, S. D. Ekşioğlu and P. Jain, "A tabu search algorithm for the flowshop scheduling problem with changing neighborhoods," Computers & Industrial Engineering , Vol. 54, No. 1, 2008, PP. 1–11.
[14]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.
[15]T. Eren and E. Güner, "A bicriteria scheduling with Setup Times," Applied Mathematics and Computation, Vol. 183, No. 2, 2006, PP. 1292–1300.
[16]T. Eren, "A multicriteria scheduling with Setup Times," Journal of Materials Processing Technology, Vol. 186, No. 1-3, 2007, PP. 60–65.
[17]B. Naderi, M. Zandieh, A. Khaleghi Ghoshe Balagh and V. Roshanaei, "An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness," Expert Systems with Applications, Vol. 36, No. 6, 2009, PP. 9625–9633.
[18]R. Ruiz and C. Maroto, "A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility," European Journal of Operational Research, Vol. 169, No. 3, 2006 , PP. 781–800.
[19]R. Ruiz and T. Stützle, "An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives," European Journal of Operational Research, Vol. 187, No. 3, 2008 , PP. 1143–1159.
[20]C. Rajendran and H. Ziegler, "A heuristic for scheduling to minimize the sum of weighted flow time of jobs in a flowshop with sequence-dependent setup times of jobs," Computers & Industrial Engineering, Vol. 33, No. 1-2, 1997 , PP. 281–284.
[21]R. Ruiz, C. Maroto and J. Alcaraz, "Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics," European Journal of Operational Research, Vol. 165, No. 1, 2005 , PP. 34–54.
[22]C. Rajendran and H. Ziegler, "Scheduling to minimize the sum of weighted flowtime and weighted tardiness of jobs in a flowshop with sequence-dependent setup times," European Journal of Operational Research, Vol. 149, No. 3, 2003 , PP. 513–522.
[23]A. Allahverdi and T. Aldowaisan, "No-wait and separate setup three-machine flowshop with total completion time criterion," International Transactions in Operational Research, Vol. 7, No. 3, 2000 , PP. 245–264.
[24]T. Aldowaisan and A. Allahverdi, "New heuristics for m-machine no-wait flowshop to minimize total completion time," Omega, Vol. 32, No. 5, 2004, PP. 345–352.
[25]J. L. Chang, D. W. Gong and X. P. Ma, "A Heuristic Genetic Algorithm for No-Wait Flowshop Scheduling Problem," Journal of China University of Mining and Technology, Vol. 17, No. 4, 2007, PP. 582–586.
[26]S. J. Shyu, B. M. T. Lin and P.Y. Yin, "Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time," Computers & Industrial Engineering, Vol. 47, No. 2-3, 2004, PP. 181–193.
[27]Q. K. Pan, M. F. Tasgetiren and Y. C. Liang, "A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem," Computers & Operations Research, Vol. 35, No. 9, 2008, PP. 2807–2839.
[28]T. Eren and E. Güner, "A bicriteria flowshop scheduling with a learning effect," Applied Mathematical Modelling, Vol. 32, No. 9, 2008, PP. 1719–1733.
[29]C. C. Wu and W. C. Lee, "A note on the total completion time problem in a permutation flowshop with a learning effect," European Journal of Operational Research, Vol. 192, No. 1, 2009, PP. 343–347.
[30]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.
[31]A. Nagar, J. Haddock and S. Heragu, "Multiple and bicriteria scheduling: a literature survey," European Journal of Operational Research, Vol.. 81, No. 1, 1995, PP. 88–104.
[32]V. T’kindt, and J. C. Billaut, "Multicriteria scheduling problem: a survey," RAIRO Operations Research, Vol. 35, No. 2, 2001, PP. 143–63.
[33]T. Eren and E. Güner, "A bicriteria scheduling with sequence-dependent Setup Times," Applied Mathematics and Computation, Vol. 179, No. 1, 2006, PP. 378–385.
[34]T. Eren, "A multicriteria scheduling with sequence-dependent Setup Times, " Applied Mathematical Sciences, Vol.. 1, No. 1, 2007, PP. 2883–2894.
[35]A. B. Keha, K. Khowala and J. W. Fowler, "Mixed integer programming formulations for single Machine scheduling problems," Computers & Industrial Engineering, 2009, Vol. 56, No. 1, PP. 357–367.
[36]F. S. Hillier and G. J. Lieberman, Introduction to operations research, McGraw-Hill, Inc, 2001, PP.61–109.
[37]潘昭賢、葉瑞徽，作業研究，台北市，滄海書局，2006，第11–1至11–73頁。
[38]楊國隆、熊高生，作業研究入門引導使用LINGO，松岡，2009，第11–1至11–24頁。
[39]J. Carlier, "Ordonnancements a contraintes disjonctives," R.A.I.R.O. Recherche operationelle/Operations Research, Vol. 12, 1978, 333-351.