跳到主要內容

臺灣博碩士論文加值系統

(44.222.218.145) 您好!臺灣時間:2024/03/02 10:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:余舜基
研究生(外文):Yu Shun Chi
論文名稱:考量時窗限制之排程研究-以流程式及零工式為例
論文名稱(外文):Production Scheduling with Due Windows- Flow Shop and Job Shop Cases
指導教授:黃榮華黃榮華引用關係
指導教授(外文):Huang Rong Hwa
口試委員:曾勝滄應國卿楊長林李緒東
口試委員(外文):Tseng Sheng TsaingYing Kuo ChingYang Chang LinLee Hsu Tung
口試日期:2014-07-21
學位類別:博士
校院名稱:輔仁大學
系所名稱:商學研究所博士班
學門:商業及管理學門
學類:一般商業學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:123
中文關鍵詞:迴流式排程平行機流程式排程零工式排程蟻群演算法粒子群演算法時窗遠端粒子群演算法有效率蟻群演算法智慧選擇蟻群演算法
外文關鍵詞:reentrantmultiprocessor flow shopant colony optimizationparticle swarm optimizationdue windowsfarness particle swarm optimizationeffective ant colony optimizationwise select ant colony optimization
相關次數:
  • 被引用被引用:2
  • 點閱點閱:406
  • 評分評分:
  • 下載下載:88
  • 收藏至我的研究室書目清單書目收藏:0
本研究探討生產排程問題,考慮時窗限制下之流程式和零工式生產作業情況。在實務中,為了促進相關行業的利益,時窗的限制成為即時生產的一個重要問題。迴流式流程式排程、兩階段彈性流程式排程及零工式排程問題為現實世界中最常見的生產活動。因此,藉由時窗的限制,本研究基於即時生產的概念,試圖以減少加權提早,延遲成本來進行研究。為了解決具時窗限制的排程問題,本研究發展三種有效方法,以防止生產過程中意外的延遲和相關的巨額損失。
隨著相關研究展現蟻群演算法 (ACO) 和粒子群算法 (PSO)是有效和高效率地解決排程問題的優點。本研究,開發了遠端粒子群演算法 (FPSO),以解決兩階段迴流式流程式排程問題,為了盡量減少兩階段迴流式平行機流程式排程的提早及延遲時間,一個新的有效率蟻群演算法 (EACO) 來求解兩階段彈性流程式排程問題,從而減少提早,延遲和最大完工時間,以及一個智慧選擇蟻群演算法 (WSACO)具有時窗考量和順序相依的設置時間限制,並解決了在現實世界中的零工式排程問題。
計算結果指出,不管小規模或大規模的問題,FPSO演算法、 EACO演算法及WSACO算法優於原有的粒子群演算法和蟻群演算法方面的有效性和健全性。重要的是,這項研究顯示FPSO演算法可以有效率地解決這樣一個複雜的迴流式流程式排程問題、EACO演算法可以有效率地解決兩階段彈性流程式排程問題,以及WSACO演算法可以有效率地解決零工式排程問題。
本研究提供了一個令人滿意的時間內之最佳解決方案的整數規劃最佳解 (IP solutions) 和提出了在短時間內可快速反應市場的三個有效解決演算方法。計算結果證明,這三個建議的演算法比普通蟻群演算法和粒子群演算法具有較高效率的求解能力。所提出的方法減少等待和延遲成本,同時幫助企業能縮短最大完工時間,以增加利潤、並降低管理成本,而本研究的成果也可以作為相關的企業管理問題之深入研究的參考依據。
This study investigates production scheduling problems with due windows using flow shop and job shop cases. In practice, due windows have become an important issue for real time production in order to facilitate the interests of related industries. Reentrant flow shop scheduling, two-stage flexible flow shop, and job shop scheduling problems are the most common production activities in the real world. Therefore, by applying the due windows constraint, this study attempts to minimize weighted early and tardy costs, based on the just-in-time concept. For solving scheduling problems with time windows, this study develops three effective methods that prevent unexpected delays and associated large losses during production.
With related studies demonstrating that ant colony optimization algorithm (ACO), and particle swarm algorithm (PSO) are both effective and efficient means of solving scheduling problems, this study; develops a farness particle swarm optimization algorithm (FPSO) to solve reentrant two-stage multiprocessor flow shop scheduling problems in order to minimize earliness and tardiness, a novel effective ant colony optimization (EACO) algorithm to solve two-stage flexible flow shop scheduling problems and thereby minimize earliness, tardiness and makespan, and a wise select ant colony optimization (WSACO) utilizing due window and sequence dependent setup time for constraints, and solves the job shop scheduling problem in real world.
Computational results indicate that either small or large scale problems are involved in which FPSO algorithm, EACO algorithm, and WSACO algorithm outperform original PSO algorithm and ACO algorithm with respect to effectiveness and robustness. Importantly, this study demonstrates that FPSO algorithm can solve such a complex reentrant flow shop scheduling, EACO algorithm can solve the two-stage flexible flow shop, and WSACO algorithm can solve the job shop scheduling problems with due window and sequence dependent setup time for constraints efficiently. This study offers IP solutions for the best solutions within a satisfactory time and the three proposed algorithms provides solutions for quick response to market within a short time. Computational results prove that the three proposed algorithms have a higher solving capacity than the common ACO and PSO algorithms. The proposed methods reduce waiting and tardiness costs, helping enterprises simultaneously shorten makespan, increasing profits, and lower overhead costs, and the results of this study can also be used as the basis for further study about other management issues of related companies.

Chapter 1. Introduction 1
1.1 Research background 1
1.2 Objectives and Scope 4
1.3 Research restrictions 6
1.4 Organization of dissertation 7
Chapter 2. Literature review 9
2.1 Multiobjective scheduling problems 9
2.2 Due windows 12
2.3 Reentrant flow shop scheduling problems 15
2.4 Flexible flow shop scheduling problem 18
2.5 Job shop scheduling problem 21
Chapter 3. Problem statements and algorithms 24
3.1 Notations 24
3.2 Problem statements 26
3.3 Algorithms 35
3.4 Performance measure 41
Chapter 4. Computational results 43
4.1 Reentrant two-stage flexible flow shop scheduling with due windows 43
4.2 Flexible flow shop scheduling problem with due windows 63
4.3 Job shop scheduling with due windows 85
Chapter 5. Conclusions and suggestions 111
5.1 Conclusion 111
5.2 Suggestions for further studies 113
References 114


1.Adibi, M. A., Zandieh, M., & Amiri, M. (2010). Multi-objective scheduling of dynamic job shop using variable neighborhood search. Expert Systems with Applications, 37, 282-287.
2.Arroyo, J. E. C., & Armentano, V. A. (2005). Genetic local search for multi-objective flowshop scheduling problems. European Journal of Operational Research, 167, 717-738.
3.Belle, J. V., Valckenaers, P., Berghe, G. V., & Cattrysse, D. (2013). A tabu search approach to the truck scheduling problem with multiple docks and time windows. Computers & Industrial Engineering, 66(4), 818-826.
4.Bank, M., Fatemi Ghomi, S.M.T., Jolai, F., & Behnamian, J. (2012). Application of particle swarm optimization and simulated annealing algorithms in flow shop scheduling problem under linear deterioration. Advances in Engineering Software, 47, 1-6.
5.Carlier, J., & Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 5, pp. 146-176.
6.Chen, J. S. (2006). A branch and bound procedure for the reentrant permutation flow-shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 29(11-12), 1186-1193.
7.Chen, J. S., Pan, J. C. H., & Wu, C. K. (2007). Minimizing makespan in reentrant flow-shops using hybid tabu search. The International Journal of Advanced Manufacturing Technology, 34(3-4), 353-361.
8.Cheng, B., Yang, S. L., & Ma, Y. (2011). Minimising makespan for two batch-processing machines with non-identical job sizes in job shop. International Journal of Systems Science, 43(12), 2185-2192.
9.Cheng, B. S., Yang, L., & Ma, Y. (2012). Minimising makespan for two batch-processing machines with non-identical job sizes in job shop. International Journal of Systems Science, 43(12), 2185–2192.
10.Cheng, T. C. E., Wu, C. C., Chen, J. C. Wu, W. H., & Cheng, S. R. (2013). Two-machine flowshop scheduling with a truncated learning function to minimize the makespan. International Journal of Production Economics, 141(1), 79-86.
11.Cheng, M. B., Tadikamalla, P. R., Shang, J., & Zhang, S. (2014). Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs. European Journal of Operational Research, 234(3), 650-657.
12.Chiu, C. H., Choi, T. M., Yeung, H. T., & Zhao, Y. (2012). Sales Rebate Contracts in Fashion Supply Chains. Mathematical Problems in Engineering, 2012, Article ID 908408, 19 pages, doi:10.1155/2012/908408.
13.Cho, H. M., Bae, S. J., Kim, J. W., & Jeong, I. J. (2011). Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm. Computers & Industrial Engineering, 61(3), 529-541.
14.Choi, H. S., Kim, H. W., Lee, D. H., Yoon, J., Yun, C. Y., & Chae, K. B. (2009). Scheduling algorithms for two-stage reentrant hybrid flow shop: minimizing makespan under the maximum allowable due dates. The International Journal of Advanced Manufacturing Technology, 42(9-10), 963-973.
15.Choi, T. M. (2013). Optimal return service charging policy for fashion mass customization program. Service Science, 5(5), 56-58.
16.Choi, T. M., Yeung, W. K., & Cheng, T. C. E. (2012). Scheduling and Coordination of Multi-suppliers Single-warehouse-operator Single-manufacturer Supply Chains with Variable Production Rates and Storage Costs. International Journal of Production Research, 51(9), 2593-2601.
17.Choong, F., Phon-Amnuaisuk, S., & Alias, M. Y. (2011). Metaheuristic methods in hybrid flow shop scheduling problem. Expert System with Application, 38 (9), 10787~10793.
18.Costantini, S., Gasperis, G. D., Provetti, A., & Tsintza, P. (2013). A Heuristic Approach to Proposal-Based Negotiation: With Applications in Fashion Supply Chain Management. Mathematical Problems in Engineering, 2013, Article ID 896312, 15 pages, http://dx.doi.org/10.1155/2013/896312.
19.Demir, Y., & Kürşat İşleyen, S. (2013). Evaluation of mathematical models for flexible job-shop scheduling problems. Applied Mathematical Modelling, 37(3), 977-988.
20.Demirkol, E., & Uzsoy, R. (2000). Decomposition methods for reentrant flow shops with sequence-dependent setup times. Journal of Scheduling, 3(3), 155-177.
21.Dorigo, C. A., Dorigo, M., Manjezzo, V., & Trubian, M. (1994). Ant system for job-shop scheduling. Belgian Journal of Operations Research, 34, 39-53.
22.Dubois-Lacoste, J., López-Ibáñez, M., & Stützle, T. (2011). A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems. Computers & Operations Research, 38(8), 1219–1236.
23.Dugardin, F., Yalaouia, F., & Amodeoa, L. (2010). New multi-objective method to solve reentrant hybrid flow shop scheduling problem. European Journal of Operational Research, 203(1), 22-31.
24.Ehrgott, M., & Gandibleux, X. (2003). Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. New York: Kluwer Academic Publishers.
25.Emmons, H., & Vairaktarakis, G. (2013). Flow shop scheduling: Theoretical Results, Algorithms, and Applications. International Series in Operations Research & Management Science, Springer New York Heidelberg Dordrecht London.
26.García-Nieto, J., Alba, E., & Carolina Olivera, A. (2012). Swarm intelligence for traffic light scheduling: Application to real urban areas. Engineering Applications of Artificial Intelligence, 25(2), 274-283.
27.Golmakani, H. R., & Namazi, A. (2012). An artificial immune algorithm for multiple-route job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 63(1-4), 77-86.
28.Gupta, J. N. D., Neppalli, V. R., & Werner F. (2001). Minimizing Total Flowtime in a Two-Machine Flowshop Problem with Minimum Makespan. International Journal of Production Economics, 69(3), 323-338.
29.Hu, Z. H., Zhao, Y. X., & Choi, T. M. (2013). Vehicle routing problem for fashion supply chains with cross-docking. Mathematical Problems in Engineering, Volume 2013 (2013), Article ID 362980, 10 pages, http://dx.doi.org/10.1155/2013/362980.
30.Huang, R. H., & Yang, C. L. (2008). Ant colony system for job shop scheduling with time windows. International Journal of Advanced Manufacturing Technology, 39, 151-157.
31.Huang, R. H., & Yang, C. L. (2009). Solving a multi-objective overlapping flow-shop scheduling. International Journal of Advanced Manufacturing Technology, 42(9-10), 955-962.
32.Huang, R. H., Yang, C. L., & Huang, H. T. (2010). Parallel machine scheduling with common due window. Journal of the Operational Research Society, 61, 640-646.
33.Huang, R. H., Yang, C. L., & Huang, Y. C. (2009). No-wait two-stage multiprocessor flow shop scheduling with unit setup. International Journal of Advanced Manufacturing Technology, 44, 921-927.
34.Huang, M., Wang, X., Lu, F., & Hualing, B. I. (2013). A Coordination of Risk Management for Supply Chains Organized as Virtual Enterprises. Mathematical Problems in Engineering, Volume 2013 (2013), Article ID 931690, 11 pages, http://dx.doi.org/10.1155/2013/931690.
35.Kang, Y. H., Kim, S. S., & Shin, H. J. (2006). A scheduling algorithm for the reentrant shop: an application in semiconductor manufacture. International Journal of Advanced Manufacturing Technology, 35(5-6), 566-574.
36.Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In IEEE International Conference on Neural Network, 4(11-12), 1942-1948.
37.Kennedy, J., & Eberhart, R. (1997). A discrete binary version of the particle swarm algorithm. In IEEE International Conference on Systems, 5, 4104-4108.
38.Kennedy, J., Eberhart, R. C., & Shi, Y. (2001). Swarm intelligence. San Francisco, Morgan Kaufmann Publishers.
39.Lee, G. C., & Kim, Y. D. (2004). A branch-and-bound algorithm for a two stage hybrid flow shop scheduling problem minimizing total tardiness. International Journal of Production Research, 42(22), 4731-4743.
40.Lian, Z.G. (2010). A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan, Discrete Dynamics in Nature and Society, Volume: 2010, page Article ID 838596, 11 p.-Article ID 838596, 11 p. ISSN: 1026-0226.
41.Lin, S. W., & Yu, V. F. (2012). A simulated annealing heuristic for the team orienteering problem with timewindows. European Journal of Operational Research, 217, 94-107.
42.Liou, C. D., Hsieh, Y. C., & Chen, Y. Y. (2013). A new encoding scheme-based hybrid algorithm for minimising two-machine flow-shop group scheduling problem. International Journal of System Science, 44(1), 77-93.
43.Liu, H. C., Gao, L., & Pan, Q. (2011). A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem. Expert Systems with Applications, 38(4), 4348–4360.
44.Mirabi, M. (2011). Ant colony optimization technique for the sequence-dependent flowshop scheduling problem. The International Journal of Advanced Manufacturing Technology, 55(1-4), 317-326.
45.Nossack, J., and Pesch, E. (2013). A truck scheduling problem arising in intermodal container transportation, European Journal of Operation Research, 230(3), 666-680.
46.Pan, Q. K., Tasgetiren, M. F., Suganthan, P. N., & Chuad, T. J. (2011a). A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Information Sciences, 181(12), 2455–2468.
47.Pan, Q. K., Suganthan, P. N., Liang, J. J., & Tasgetiren, M. F. (2011b). A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem. Expert Systems with Applications, 38(4), 3252–3259.
48.Park, Y. S., Kim, S. Y., & Jun, C. H. (2000). Performance analysis of re-entrant flow shop with single-job and batch machines using mean value analysis. Production Planning & Control, 11(6), 537-546.
49.Peng, H. J., & Zhou, M. H. (2012). Quantity discount supply chain models with fashion products and uncertain yield. Mathematical Problems in Engineering, Volume 2013 (2013), Article ID 895784, 11 pages, http://dx.doi.org/10.1155/2013/895784.
50.Rossi, A., Singh, A., & Sevaux, M. (2010). A metaheuristic for the fixed job scheduling problem under spread time constraints. Computers and Operations Research, 37, 1045–1054.
51.Scriven, I., Lu, J., & Lewis, A. (2012). Electronic enclosure design using distributed particle swarm optimization. Engineering Optimization, 45(2), 167-183.
52.Shen, B., Choi, T. M., Wang, Y., & Lo, C. K. Y. (2013). The Coordination of Fashion Supply Chains with a Risk Averse Supplier under the Markdown Money Policy. IEEE Transactions on Systems, Man, and Cybernetics - Systems, 43(2), 266-276.
53.Sivrikaya-Serifoğlu, F. & Ulusoy, G. (1999). Parallel machine scheduling with earliness and tardiness penalties. Computers and Operations Research, 26, 773-787.
54.Solomon, M. M., & Desrosiers, J. (1988). Time windows constrained routing and scheduling problem. Transportation Science, 22(1), 1–13.
55.Subramaniam, V., Lee, G. K., Hong, G. S., Wong, Y. S., & Ramesh, T. (2000). Dynamic selection of dispatching rules for job shop scheduling. Production Planning & Control, 11, 73-81.
56.Sayin, S., & Karabati, S. (1999). A bicriteria approach to the two-machine flow shop scheduling problem. European Journal of Operational Research, 113, 435-449.
57.Tan, Y. W., Guan, J. B., & Karimi, H. R. (2013). The Impact of Subsidy Policy on Total Factor Productivity: an Empirical Analysis for China’s Cotton Production. Mathematical Problems in Engineering, Volume 2013 (2013), Article ID 248537, 8 pages, http://dx.doi.org/10.1155/2013/248537.
58.Tavares Neto, R. F., & Godinho Filho, M. (2011). An ant colony optimization approach to a permutational flowshop scheduling problem with outsourcing allowed. Computers & Operations Research, 38(9), 1286-1293.
59.Teixeira, C., Covas, J. A., Stützle, T., & Gaspar-Cunha, A. (2012). Multi-objective ant colony optimization for the twin-screw configuration problem. Engineering Optimization, 44, 351-371.
60.T’kindt, V., Monmarché, N., Tercinet, F., & Laügt, D. (2002). An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. European Journal of Operational Research, 142, 250-257.
61.Tzeng, Y. R., Chen, C. L., & Chen, C. L. (2012). A hybrid EDA with ACS for solving permutation flow shop scheduling. The International Journal of Advanced Manufacturing Technology, 60, 1139-1147.
62.Uruk, Z., Gultekin, H., & Akturk, M. S. (2013). Two-machine flowshop scheduling with flexible operations and controllable processing times. Computers & Operations Research, 40(2), 639-653.
63.Udhayacumar, P., & Kumanan, S. (2010). Sequencing and scheduling of job and tool in a flexible manufacturing system. International Journal of Advanced Manufacturing Technology, 50, 1075-1084.
64.Varadharajan, T. K., & Rajendran, C. (2005). A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. European Journal of Operational Research, 167, 772-795.
65.Wang, L., Zhou, G., Xu, Y., Wang, S. Y., & Liu, M. (2012). An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. International Journal of Advanced Manufacturing Technology, 60(1-4), 303-305.
66.Wang, S. J., & Liu, M. (2013). A heuristic method for two-stage hybrid flow shop with dedicated machines. Computers & Operations Research, 40(1), 438-450.
67.Wong, W. K., Chan, C. K., & Ip, W. H. (2001). A hybrid flowshop scheduling model for apparel manufacture. International Journal of Clothing Science and Technology, 13(2), 115–131.
68.Xie, X., Tang, L., & Li, Y. P. (2011). Scheduling of a hub reentrant job shop to minimize makespan. International Journal of Clothing Science and Technology, 56, 743-753.
69.Xiong, J., Xing, L. N., & Chen, Y. W. (2013). Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns. International Journal of Production Economics, 141(1), 112-126.
70.Yao, J., & Liu, L. (2009). Optimization analysis of supply chain scheduling in mass customization. International Journal of Production Economics, 117(1), 197-211.
71.Yeung, W. K., Choi, T. M., & Cheng, T. C. E. (2010). Optimal Scheduling in a Single-Supplier Single-Manufacturer Supply Chain with Common Due Windows. IEEE Transactions on Automatic Control, 55, 2767-2777.
72.Yeung, W. K., Choi, T. M., & Cheng, T. C. E. (2011). Supply Chain Scheduling and Coordination with Dual Delivery Modes and Inventory Storage Cost. International Journal of Production Economics, 132, 223-229.
73.Yang, C. L., & Huang, R. H. (2011). Optimal Number and Scheduling of Freeway Bus Fleet. Journal of Statistics & Management Systems, 14, 949-964.
74.Yu, S. C. (2014). Elucidating multiprocessors flow shop scheduling with dependent setup times using a twin particle swarm optimization, Applied Soft Computing, 21, 578-589.
75.Zhang, C.S., Ning, J., & Ouyang, D. (2010). A hybrid alternate two phases particle swarm optimization algorithm for flow shop scheduling problem, Computers & Industrial Engineering, 58, 1-11.
76.Zhang, C. Y., Li, P. G., Rao, Y. Q., & Guan, Z. Y. (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers and Operations Research, 35, 282-294.
77.Zhao F. Q., Tang, J. Z., Wang, J. B., & Jonrinaldi, J. (2014). An improved particle swarm optimization with decline disturbance index (DDPSO) for multi-objective job-shop scheduling problem. Computers & Operations Research, 45, 38-50.
78.Zheng, W. X., Nagasawa, H., & Nishiyama, N. (1993). Single-machine scheduling for minimizing total cost with identical, asymmetrical earliness and tardiness penalties. International Journal of Productions Research, 31, 1611–1620.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊