(3.238.173.209) 您好!臺灣時間:2021/05/16 05:06
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:朱韋達
研究生(外文):Wei-Ta Chu
論文名稱:模糊多目標非相關平行機台排程交期滿意度最大化問題解算之研究
論文名稱(外文):Solving Fuzzy Bi-Objective Unrelated Parallel Machine Scheduling Problems with Flexible Constraints on Due Dates
指導教授:徐旭昇徐旭昇引用關係
學位類別:碩士
校院名稱:元智大學
系所名稱:工業工程與管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:中文
論文頁數:113
中文關鍵詞:非相關平行機台排程問題、多目標最佳化、模擬退火演算法、競制搜尋法、模糊理論、貪進隨機調整搜尋法GRASP
外文關鍵詞:unrelated parallel machine scheduling, multi-objective meta-heuristics, performance measures, Pareto optimality, fuzzy set theory
相關次數:
  • 被引用被引用:0
  • 點閱點閱:318
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
本研究以模糊理論為工具探討含不確定性參數之兩目標不相關平行機台排程問題。在實務上排程問題之工件處理時間、交期等往往參雜一些不確定性因素諸如人為因素、原料未能及時供應、機台故障、或資訊不足,而使得對工件處理時間難以精確估算(imprecision);同時在實際上,上下游廠商對預設交期延遲時常是有著某種程度之容忍,同時決策者考量訂單生產排程不只單一目標。若決策者偏好對這些目標的達成度以主觀性滿意度來衡量,模糊多目標最佳化模式便是解決決策者問題的較佳選擇方法。在本研究中,問題兩目標分別為最大化平均工件延遲時間滿意度與最大化不算延遲工件數之比例,所提演算法包括權重式多目標模擬退火法、權重式多目標禁制搜尋法、與柏拉圖式多目標禁制搜尋法。
研究測試題產生方式參考Lee and Pinedo (1997),以交期寬鬆因子與交期範圍因子為參數,依題目大小,各產生五題測試題。兩種測試題大小分別為:100(工件)x 5(機台)、200 x 10。演算法效果量測以generational distance (GD)、Pareto fronts distribution、以及Hypervolumn (HV)為之。實驗結果發現權重式多目標禁制搜尋法之求解效果較佳,但所花之求解時間也較長。
實驗使用兩種不同初始解進行比較,產生的方式分為最短處理時間法(SPT)及利用GRASP產生兩種不同的初始解,實驗結果發現利用最短處理時間法(SPT)之求解效果較佳。使用兩種工件滿意度的量測指標分為可能性測量 (possibility measure) 以及面積計算法 (area of intersection),經過實驗所產生之結果顯示,可能性測量所得到的數值較面積計算法高,但演算法所求得之結果趨勢相同


This thesis studies unrelated parallel machine scheduling problems (UPMSP) that consider uncertainty on job processing data and job due dates, and have two simultaneous maximization objectives – average satisfaction of job tardiness and average satisfaction of the number of tardy jobs. Both objectives are concerned with the manufacturer’s performance on customer delivery. When dealing with uncertainty, fuzzy set theory may provide an acceptable compromise between expressive and computational difficulties for modeling preference and uncertainty. In the study, two measures based on fuzzy set theory are used to assess the satisfaction level of both objectives: possibility measure (height) and area ratio.
Two archived meta-heuristics are applied to solve this bi-objective UPMSP: simulated annealing (SA) and tabu search (TS). In SA, random-weight direction (RWD) and fix-weight direction (FWD) are incorporated into the SA framework. In TS, other than RWD and FWD, a Pareto-based method adopting nadir distance (ND) to guide the TS iteration. The three TS search methods use shortest processing time rule (SPT) to construct an initial solution for each TS iteration step. In addition, greedy randomized adaptive search procedure (GRASP) is also applied to create an initial solution for TS.
An experiment was conducted using five test sets with two problem sizes, 100 (jobs) x 5 (machines) and 200 x 10, which were generated based on Lee and Pinedo (1997) and Saidi Mehrabad et al. (2009). Each test set is characterized by problem size and due date factors, and has five instances. The numerical results indicate the following: (1) TS with SPT-initial solution outperforms TS with GRASP-initial solution; (2) The satisfaction values calculated based on possibility measure are generally higher than those based on area ratio method, but their conclusions are consistent with each other; (3) TS-FWD and TS-RWD perform better in terms of hyper-volume and generational distance performance measures for problems with loose due dates; on the other hand, there is little difference among SA and TS with distinct weighting direction approaches; finally, TS-ND is inferior to the other algorithms in most instances.


目錄 vii
圖目錄 x
表目錄 xii
第一章、導論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與研究限制 3
1.3.1 研究範圍 3
1.3.2 研究限制 3
1.4 論文架構與研究流程 4
第二章、文獻探討 6
2.1 生產排程問題之型態與目標 7
2.1.2 生產排程之型態 7
2.1.2 生產排程目標 9
2.2 非相關平行機台問題 10
2.3 柏拉圖支配解概念 12
2.4 模糊集合應用於排程問題之相關文獻 13
2.5 相關模糊理論介紹 16
2.5.1 模糊理論應用於完工時間 16
2.5.2 模糊理論應用於交期限制 18
2.5.3 模糊理論應用於排程問題目標之計算 19
2.6 多目標模擬退火演算法 24
2.6.1 SMOSA 24
2.6.2 UMOSA 25
2.6.3 PSA (Pareto Simulated Annealing) 26
2.6.4 PDMOSA (Pareto-dominated-based acceptance criterion) 26
2.6.5 AMOSA (Archived MOSA) 27
2.7演算法效果評估方式 28
第三章、問題描述 32
3.1 數學符號 33
3.2 模式說明: 34
第四章、研究方法 35
4.1 權重給定方法 36
4.2 編碼與解碼 38
4.2.1 編碼方式 38
4.2.2 解碼方式 39
4.3 區域搜尋法 41
4.4 多目標模擬退火法演算機制 47
4.4.1多目標模擬退火法(MOSA)流程介紹 47
4.4.2 模擬退火法 初始溫度之設定 49
4.5禁制搜尋法演算機制 (Tabu) 49
第五章、實驗結果與分析 53
5.1 程式執行之實驗環境 53
5.2 測試題產生方式 53
5.3 演算法初始參數設定 55
5.3.1 參數設定 55
5.3.2 搜尋機制 57
5.4 演算法評估方法 57
5.5 實驗數據分析 58
5.5.1 測試題大小為100 x 5、利用SPT產生初始解之求解結果 58
5.5.2 測試題大小為100 x 5,SPT產生初始解之求解結果總結 63
5.5.3 測試題大小為200 x 10、利用SPT產生初始解之求解結果 64
5.5.4 測試題大小為200 x 10,SPT產生初始解之求解結果總結 69
5.5.5 測試題大小為100 x 5、利用GRASP產生初始解之求解結果 70
5.5.6 測試題大小為100 x 5,GRASP產生初始解之求解結果總結 75
5.5.7 測試題大小為200 x 10、利用GRASP產生初始解之求解結果 76
5.5.8測試題大小為200 x 10,GRASP產生初始解之求解結果總結 81
5.5.9可能性測量與面積測量法之求解差異 82
5.5.7可能性測量與面積測量法之求解結果 85
第六章、結論 86
6.1 結論 86
參考文獻 88
附錄一 94
附錄二 97



Allahverdi A, Ng CT, Ceng TCE, Kovalyov MY. (2008) A survey of scheduling problems with setup times or costs, European Journal of Operational Research 187:985-1032.
Azadeh A, Moghaddam M, Geranmayeh P, Naghavi A. (2010) A flexible artificial neural network-fuzzy simulation algorithm for scheduling a flow shop with multiple processors, International Journal of Advanced Manufacturing Technology 50:699-715.
Bandyopadhyay S, Saha S, Maulik U, Deb K. (2008) A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA, IEEE Transactions on Evolutionary Computation 12 (3): 269-283.
Bank J, Werner F. (2001) Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties, Mathematical and Computer Modelling 33:363–383.
Bruno LG, Coffman EG, Sethi R. (1974) Scheduling independent tasks to reduce mean finishing time, Communications of the ACM 17:382-387.
Chanas S, Kasperski A. (2003) On two single machine scheduling problems with fuzzy processing times and fuzzy due dates, European Journal of Operational Research 147:281-296.
Chanas S, Kasperski A. (2004) Possible and necessary optimality of solutions in the single machine scheduling problem with fuzzy parameters, Fuzzy Sets and Systems 142:359-371.
Chen JF. (2009) Scheduling on unrelated parallel machines with sequence- and machine-dependent setup times and due-date constraints, International Journal of Advanced Manufacturing Technology 44:1204-1212.
Chen B, Li K, Chen B. (2010) Scheduling a single batch-processing machine with non-identical job sizes in fuzzy environment using an improved ant colony optimization, Journal of Manufacturing Systems 29:29-34.
Cochran JK, Horng SM, Fowler JW. (2003) A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines, Computers and Operations Research, 30:1087-1102.
De Paula, M R, Mateus, GR, Ravetti, M G. (2010) A non-delay relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times, Computers and Operations Research 37:938-949.
Dubois D, Fargier H, Fortemps P. (2001), Scheduling under flexible constraints and uncertain data: The fuzzy approach, Lopez P, Roubellat F. (Eds), Production Scheduling, pp.301-322, John Wiley & Sons, Inc. Hoboken, USA.
Dubois D, Fargier H, Fortempts P. (2003) Fuzzy scheduling: modeling flexible constraints vs. coping with incomplete knowledge, European Journal of Operational Research 147:231-252.
Fayad C, Petrovic S, (2005) A fuzzy genetic algorithm for realworld job shop scheduling, Lecture notes in Artificial Intelligence 3533:524-533, Springer Berlin.
Fortemps P, Roubens M, (1996) Ranking and defuzzification methods based on area compensation, Fuzzy Sets and Systems 82:319-330.
French S, (1982) Sequencing and scheduling: an introduction to the mathematics of the job-shop, Chichester: Ellis Horwood.
Gao J. (2010) A novel artificial immune system for solving multiobjective scheduling problems subject to special process constraint, Computers and Industrial Engineering 58:602-609.
Guiffrida A, Nagi R. (1998) Fuzzy set theory applications in production management research: a literature survey, Journal of Intelligent Manufacturing 9:39-56.
Herroelen W, Leus R. (2005) Project scheduling under uncertainty: Survey and research potentials, European Journal of Operational Research 165:289-306.
Hoogeveen H. (2005) Multicriteria scheduling, European Journal of Operational Research 167:592-623.
Jing T, Tomohiro M. (2010) Mulit-objective flexible job shop scheduling with uncertain processing time and machine available constraint based on hybrid optimization approach, Proceedings of the 2010 IEEE, International Conference on Automation and Logistics, August 16-20, Hong Kong and Macau, pp.581-695.
Karwowski W, Evans GW. (1986). Fuzzy concepts in production management research: a review. International Journal of Production Research 24(1):129-147.
Kilic S. (2007). Scheduling a fuzzy flowshop problem with flexible due dates using ant colony optimization, Giacobini et al. (Eds), EvoWorkshops, Lecture Notes in Computer Science (LNCS) 4448, pp. 742-751.
Kim ES, Sung CS, Lee IS. (2009) Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints, Computers and Operations Research 36:698-710.
Kim DW, Kim KH, Jang W, Chen FF. (2002) Unrelated parallel machine scheduling with setup times using simulated annealing, Robotics and Computer Integrated Manufacturing 18(3–4):223–231.
Kim DW, Na DG, Chen FF. (2003) Unrelated parallel machine scheduling with setup times and total weighted tardiness objective, Robotics and Computer Integrated Manufacturing 19(1–2):173–181.
Klir GJ, Yuan B, (1995) Fuzzy sets and fuzzy logic: theory and applications, Prentice Hall, New Jersey.
Knowles JD, Corne DW. (2000) Approximating the nondominated front using the Pareto Archived Evolution Strategy, Evolutionary computation, 8(2):149-172.
Lei D. (2008) Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems, International Journal of Advanced Manufacturing Technology 37:157-165.
Lei D. (2010) Fuzzy job shop scheduling problem with availability constraints, Computers and Industrial Engineering 58:610-617.
Lei D. (2010) Scheduling fuzzy job shop with preventive maintenance through swarm-based neighborhood search, International Journal of Advanced Manufacturing Technology DOI 10.1007/s00170-010-2989-4.
Lei, D. (2010) Solving fuzzy job shop scheduling problems using random key generation algorithm, International Journal of Advanced Manufacturing Technology 49:253-262.
Li K, Yang SL. (2009) Non-identical parallel-machine scheduling research with minimizing total weighted completion time: models, relaxations and algorithms, Applied Mathematical Modelling, 33:2145-2158.
Li X, Chen Y, Sun Y. (2010) Minimizing job completion time variance for service stability on identical parallel machines, Computers and Industrial Engineering 58:729-738.
Li X, Yalaoui F, Amodeo L, Chehade H. (2010) Metaheuristics and exact methods to solve a mulitobjective parallel machines scheduling problem, Journal of Intelligent Manufacturing DOI 10.1007/s10845-010-0428-x
Logendran R, McDonell B, Smucker B. (2007) Scheduling unrelated parallel machines with sequence-dependent setups, Computers and Operations Research 34:3420-3438.
Luis FP, Ruiz R. (2011) Size-reduction heuristics for the unrelated parallel machines scheduling problem, Computers and Operations Research 38:301-309.
Moratori P, Petrovic S, Vazquez-Rodriguez JA. (2010) Fuzzy approaches for robust job shop rescheduling, IEEE world congress on computational Intelligence DOI: 10.1109/FUZZY.2010.5584722
Pereira Lopes, MJ., Valério de Carvalho JM. (2007) A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times, European Journal of Operational Research 176:1508-1527.
Piersma N, van Dijk W. (1996) A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search, Mathematical Computer Modelling 24(9):11-19.
Pinedo M. (2008) Scheduling Theory, Algorithms and Systems (2nd edition), Prentice-Hall, Inc., A Simon & Schuster Company Englewood Cliffs, New Jersey.
Saidi MM, Pahlavani A. (2009) A fuzzy multi-objective programming for scheduling of weighted jobs on a single machine, International Journal of Advanced Manufacturing Technology 45:122-139.
Serafini P, (1992) Simulated annealing for multiple objective optimization problems, Proceedings of the Tenth International Conference on Multiple Criteria Decision Making Taipei, 19-24 July 1, pp. 87-96.
Serafini P, (1985) Mathematics of Multiobjective Optimization, CISM Courses and Lectures, Springer-Verlag:Berlin, 289.
Siahkali H, Vakilian M. (2010) Fuzzy generation scheduling for a generation company (GenCo) with large scale farms. Energy Conversion and Management, 51:1947-1957.
Silva C, Magalhaes JM, (2006) Heuristic lot size scheduling on unrelated parallel machines with applications in the textile industry, Computers and Industrial Engineering, 50:76-89.
Slany W, (1996) Scheduling as a fuzzy mulitple criteria optimization problem, Fuzzy Sets and Systems, 78:197-222.
Su LH, Minimizing earliness and tardiness subject to total completion time in an identical parallel machine system, Computers and Operations Research, 36:461-471.
Suman B, Kumar P. (2006) A survey of simulated annealing as a tool for single and multiobjective optimization, Journal of the Operational Research Society 57:1143-1160.
Suman B. (2005) Self-stopping PDMOSA and performance measure in simulated annealing based multiobjective optimization algorithms, Computers & Chemical Engineering 29:1131-1147.
Suppapitnarm A, Seffen KA, Parks GT, Clarkson PJ. (2000) Simulated annealing: an alternative approach to true multiobjective optimization, Engineering Optimization 33:59.
T’kindt V, Billaut JC. (2006) Multicriteria Scheduling: Theory, Models and Algorithms, second edition, Springer, p.65.
T’kindt V, Billaut JC, Proust C. (2001) Solving a bicriteria scheduling problem on unrelated parallel machines occuring in the glass bottle industry, European Journal of Operational Research 135:42-49.
Ulungu LE, Teghem J, Ost C. (1998) Interactive simulated annealing in a multiobjective framework: application to an industrial problem. Journal of Operational Research Society 49:1044-1050.
Ulungu LE, Teghem J, Fortemps PH, Tuyttens D. (1999) MOSA Method: a tool for solving multiobjective combinatorial optimization problems. Journal of Multicriteria Decision Analysis 8:221-236.
Unlu Y, Mason SJ (2010) Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems, Computers and Industrial Engineering 58:785-800.
Weng MX, Lu J, Ren H, Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective, International Journal of Production Econcomics, 70:215-226.
Yalaoui F, Chu C. (2002) Parallel machine scheduling to minimize total tardiness, International Journal of Production Economics 76:265-279.
Yimer AD, Demirli K. (2009) Fuzzy scheduling of job orders in a two stage flow shop with batch-processing machines, International Journal of Approximate Reasoning 50:117-137.
Zammori FA, Braglia M, Frosolini M. (2009) A fuzzy mulit-criteria approach for critical path definition, International Journal of Project Management 27:278-291


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top