以基因演算法求解不可延遲批次排程問題之研究｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	李宛柔 Wan-Jou Lee
論文名稱：	以基因演算法求解不可延遲批次排程問題之研究 Solving No-wait Batch Scheduling Problems by Genetic Algorithm
指導教授：	葉瑞徽 Ruey-Huei Yeh
口試委員:	許總欣 Tsung-Shin Hsu 郭伯勳 Po-Hsun Kuo
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業管理系 Department of Industrial Management
論文出版年：	2007
畢業學年度：	95
語文別：	英文
論文頁數：	86
中文關鍵詞：	排程問題、不可延遲、批次處理、基因演算法
外文關鍵詞：	Scheduling, No-wait, Batch, Genetic Algorithm
相關次數：	點閱：265 下載：7
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

傳統生產製造業的排程研究中，通常假設每個步驟的加工作業完成後，設有暫存區以等待下一步驟作業的開始。然而某些產業基於生產技術或製程上的限制，各作業間必須是連續不間斷地銜接進行，不允許有延遲時間，例如，半導體廠、煉鋼廠、化學製程、熱處理製程等。這種不允許加工過程間斷的生產限制稱為「不可延遲」。為符合此要求，於等候線上之工件便可能必須被迫停留一定的間隔時間，以確保不會發生加工衝突，而具有此生產特性的製程，通常皆需要較長的加工處理時間，因此常伴隨著批次處理的生產條件以彌補效益不足的產出。此類排程問題因而延伸成為「不可延遲批次處理」的研究，在這種限制下要求最小化最大完工時間是一種指數複雜度的問題。本論文提出結合一啟發式演算法及基因演算法，分別應用於更精確的等待時間間隔及較有效率的派工法則兩方面，以求解此排程問題。藉由基因演算法反覆進行取代與淘汰的程序，以搜尋到更佳的可行解。並進一步以半導體廠具有此生產特性的某工作站為例，分別以傳統的先進先出經驗法則與本文提出以兩演算法為基礎的分析模式來進行模擬實際生產的績效比較，實驗結果顯示此手法能增進可行解的品質，並對於績效有所改善。

A no-wait scheduling problem indicates a circumstance where there are no allowed buffers within each operation from job release to finish with the technological constraint. Common examples of a no-wait restriction are the production line in semiconductor fabrication facilities, steel factories, chemical process, and so on. In order to meet the constraint, jobs in queue have to wait for a span of time to avoid possible collision with discarding. Thus, the delay time intervals between jobs must be predetermined. Production with this constraint often goes along with batch processing to make up a deficiency of inefficient throughput due to longer processing time. This thesis proposes an approach incorporating a heuristic algorithm and a genetic algorithm to deal with the determination of accurate delay time intervals and efficient dispatching rule for the scheduling problem with the objective of minimizing maximum completion time (makespan). Furthermore, an analysis of a wet etching station in the semiconductor fabrication facilities will be presented to demonstrate the traditional method and the proposed approach. The computational results show that the proposed approach can improve the solution performance.

摘要 I
Abstract	II
致謝 III
Table of Content IV
List of Figures V
List of Tables VI
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 2
1.3 Objective 3
1.4 Organization of Thesis	5
Chapter 2 Literature Review 8
2.1 No-wait Scheduling Problem 8
2.2 Batch Formation Issue 12
2.3 Genetic Algorithm 15
Chapter 3 Problem Statement and Proposed Approach 21
3.1 Problem Description 21
3.2 Model Formulation 23
3.3 Traditional Approach 26
3.4 Bertolissi’s Algorithm for Delay Time Intervals 29
3.5 Incorporation of Genetic Algorithm with Batch Formation Method for Dispatching Rule 33
3.5.1 Parameters Setting 35
3.5.2 Encoding of individuals 35
3.5.3 Generating Initial Population 36
3.5.4 Batch Formation 37
3.5.5 Decoding of Individuals and Fitness Evaluation 39
3.5.6 Genetic Operators 41
3.5.7 Termination 45
3.5.8 Selection 45
3.6 An Illustrative Example 46
Chapter 4 Case Study 57
4.1 Background 57
4.1.1 Machine environment 58
4.1.2 Machine Visualization 60
4.2 Computational Experiments 63
Chapter 6 Conclusions 70
References 71

                                

• Ammar, O., “Makespan minimization in no-wait flow shop problem with two batching machines”, Computers & Operations Research, 34, 1033-1050 (2007).
• Bertolissi, E., “Heuristic algorithm for scheduling in the no-wait flow-shop”, Journal of Materials Processing Technology, 107, 459-465 (2000).
• Carlos, A. B., Z. Yong, and S. Nobuo, “No-wait and blocking job-shops: challenging problems for GA’s”, 0-7803-77-2/01 IEEE, 2349-2351 (2001).
• Chen, F. Frank, Dong-Won Kim, and Dong-Gil Na, “Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective”, Robotics and Computer Integrated Manufacturing, 19, 173-181 (2003).
• Cheng, S. W. and U. Reha, “A genetic algorithm to minimize maximum lateness on a batch processing machine”, Computers & Operations Research, 29, 1621-1640 (2002).
• Christopher, D. G., G. K. Karl, and U. Reha, “A tabu search approach to scheduling an automated wet etch station”, Journal of Manufacturing System, 16, 102-116 (1997).
• Ceyda, O. and M. F. Ercan, “A Genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks”, Journal of Scheduling, 8, 323-351 (2005).
• Damodaran, P. and K. Shihari, “Mixed integer formulation to minimize makespan in flow shop with batch processing machines”, Mathematical and Computer Modeling, 40, 1465-1472 (2004).
• Gupta, A. K. and A. I. Sivakumar, “Optimization of due-date objectives in scheduling semiconductor batch manufacturing”, International Journal of Machine Tools & Manufacture, 46, 1671-1679 (2006).
• Hsieh, M. D., L. Amos, K. Kenley, and H. L. Wang, “A decision support system of real time dispatching in semiconductor wafer fabrication with shortest process time in wet bench”, 0-7803-7894-6/03 IEEE, 301-303 (2003).
• Hung, Yi-Feng and Ing-Ren Chen, “A simulation study of dispatch rules for reducing flow times in semiconductor wafer fabrication”, Production Planning & Control, 9, 714-722 (1998).
• Ishii, N. and M. Muraki, “A genetic framework for an on-line scheduling and control system in batch process management”, Computers chem. Engng, 21, 1291-1310 (1997).
• Jose, M. F. and S. Christoph, “An enhanced timetabling procedure for the no-wait job shop problem:a complete local search approach”, Computers & Operations Research, 331, 1200-1231 (2006).
• Jung, J. H., H. L. Chang, and L. In-Beum, “A genetic algorithm for scheduling of multi-product batch processes”, Computers Chem. Engng, 22, 1725-1730 (1998).
• Karimi, I. A., Zerlinda Y. L. Tan, and B. Swarnendu, “An improved formulation for scheduling an automated wet-etch station”, Computers and Chemical Engineering, 29, 217-224 (2004).
• Kasin, O. and J. M. Scott, “Scheduling batch processing machines in complex job shops”, Proceedings of the 2001 Winter Simulation Conference
• Khan, Z., B. Prasad, and T. Singhq, “Machining control optimization by genetic algorithm and simulated annealing”, Computers Ops Res., 24, 647-657 (1997).
• Lars, M. and H. Ilka, “Simulation-based assessment of batching heuristics in semiconductor manufacturing”, Proceeding of the 2003 Winter Simulation Conference.
• Liaw, Ching-Fang, Chun-Yuan Cheng, and Mingchih Chen, “Scheduling two-machine no-wait open shops to minimize makespan”, Computers & Operations Research, 32, 901-917 (2005).
• Lin, Bertrand M. T. and T. C. Edwin Cheng, “Batch scheduling in no-wait two machine flowshop to minimize the makespan”, Computers & Operations Research, 28, 613-624 (2001).
• Liu, Zhaohui, Jinjiang Yuan, and T. C. Edwin Cheng, “On scheduling an unbounded batch machine”, Operations Research Letters, 31, 42-48 (2003).
• Macchiaroli, R., S. Mole, and S. Riemma, “Modeling and optimization of industrial manufacturing processes subject to no-wait constrains”, Int. J. Prod. Res., 11, 2585-2607 (1999).
• Mascis, A. and D. Pacciarelli, “Job-shop scheduling with blocking and no-wait constrains”, European Journal of Operational research, 143, 498-517 (2002).
• Meral, A. and W. Scott, “Scheduling a batch processing machine with incompatible job families”, Computers & Industrial Engineering, 39, 325-335 (2001).
• Monch, L., B. Hari, John W. Fowler, and Michele E. Pfund, “Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times”, Computer & Operations Research, 32, 2731-2750 (2005).
• Nicholas, G. H., L. Gilbert, S. Esaignani, and S. Chelliah , “Scheduling and lot streaming in flowshops with no-wait in process”, Journal of Scheduling, 6, 339-354 (2003).
• Nirmal, G. and F. David, “Resident-entity based simulation of batch chamber tools in 300MM semiconductor manufacturing”, Proceeding of the 2003 Winter Simulation Conference.
• Raaymakers, W. H. M. and J. A. Hoogeveen, “Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing”, European Journal of Operational Research, 126, 131-151 (2000).
• Ruben, R., M. Concepcion, and A. Javier, “Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics”, European Journal of Operational Research, 165, 34-54 (2005).
• Ruben, R. and M. Concepcion, “A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility”, European Journal of Operational Research, 169, 781-800 (2006).
• Subodha, K., P. B. Tapan, and C. Sriskandarajah, “Lot streaming and scheduling heuristics for m-machine no-wait flowshops”, Computers & Industrial Engineering, 38, 149-172 (2000).
• Taho, Y., K. Yiyo, and C. Chiwoon, “A genetic algorithms simulation approach for the multi-attribute combinatorial dispatching decision problem”, European Journal of Operational Research, 176, 1859-1873 (2007).
• Vince, C., I. Stefano, P. B. Tapan, and S. Chelliah, “Minimizing makespan in a blocking flowshop using genetic algorithms”, Int. J. Production Economics, 70, 101-115 (2001).
• Wang, Yunzeng and G. Yigal, “Input control in a batch production system with lead times, due dates and random yields”, European Journal of Operational Research, 126, 371-385 (2000).

簡易檢索 / 詳目顯示

相關論文