 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：47 、訪客IP：3.145.196.61
姓名 陳幸滿(Xing-Man Chen) 查詢紙本館藏 畢業系所 工業管理研究所 論文名稱 雙機流程型生產環境下具批量流與等候時間限制的多產品排程問題
(Lot streaming and Scheduling of Multiple Products in Two-Machine Flow Shops with Limited Waiting Time Constraint)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 本研究探討具批量流(lot streaming)與等候時間限制(limited waiting time)特性的雙機流程型生產（two-machine flow shop）排程問題，以極小化完成時間為目標。批量流將工作分割成數個子批量（sublot）或轉運批（transfer batch），以便一製程完成後，可立刻送至下一製程，繼續處理加工，而不需等到整個工作完成後再移送至下一個製程。由於同一工作能在不同的製程上同時處理，可達到作業重疊(operation overlap)，縮短工作的完成時間。本研究討論子批量為連續型態(continuous-sized sublots)的批量流問題。存在於任二個製程間的等候時間窗口為一相依時間，等候時間限制前一製程完成後，在窗口時間的上限內必須進行下一製程。
本研究沿襲相關文獻使用的二步驟方式，求解多產品排程問題。首先針對單一產品問題提出一線性規劃模式(linear programming model)，並延伸幾何級數型態解(geometric form solution)至具等候時間限制的環境，求得最佳的子批量分割與最小完成時間。爾後再將單一產品問題求得的子批量引用到多產品問題中，提出一為枝界法(branch-and-bound algorithm)的啟發式演算法，求得一多產品加工順序與最小完成時間。
本研究針對提出的枝界法進行下列的實驗和資料分析，驗證演算法的正確性和效率。透過以下二個特例：不具批量流特性的問題(Yang and Chern, 1995)，和等候時間上限無限大的問題(Vickson, 1995)，證實枝界法的正確性。一般狀況下的實驗結果顯示，運用枝界法求得的解非常近似最佳解，且大部分為最佳解；經由枝界法求解過程中產生的節點數顯著比窮舉少非常多，當等候時間的上限增加時，產生的節點數會隨之減少，求解的速度會隨之增加。摘要(英) This study treats the optimal lot streaming problem to minimize the makespan for multiple products in a two-machine flow shop with limited waiting time constraint. Lot streaming is the process of creating sublots (or transfer batches) to move the completed portion of a production sublot to downstream machines so that operations can be overlapped. Limited waiting time constraint means that for each product the waiting between two machines cannot be greater than a given upper bound. This problem is studied allowing continuous-sized sublots.
We use two steps to solve lot streaming and scheduling of multiple products problem. First, a linear programming model and the optimal geometric form solution are proposed to find the optimal lot streams to minimize makespan for each product. Then, we develop a heuristic which is a branch-and-bound algorithm for the multiple products problem to find a sequence of products to minimize makespan under the assumptions that the optimal set of sublot sizes is given from each single product problem. Properties of machine dominance and revised Johnson’s rule are derived and implemented in the proposed algorithm for eliminating nodes efficiently in the branching tree.
The following computational analyses are conducted for model validation and algorithm performance. (1) Validate the branch-and-bound algorithm by examples of two special cases: the problems with infinite waiting time constraint (Vickson, 1995) as well as the problem without lot streaming (Yang and Chern, 1995), namely, the whole product is a single lot. The same optimal solution can be found by the proposed algorithm. (2) Computation experiences indicate that this heuristic can deliver close-to-optimal solutions for this problem and find the optimal solutions for most of tests. The number of averaged generated nodes by the proposed algorithm is seen to be extremely small compared with the number of total enumerative nodes in branching tree. When the upper bound of waiting time is increased, the number of averaged generated nodes is decreased and the optimal solution is found fast.關鍵字(中) ★ 批量流
★ 等候時間限制
★ 啟發式解法
★ 枝界法
★ 流程型生產環境關鍵字(英) ★ Lot streaming
★ Limited waiting time constraint
★ Heuristic
★ Branch-and-bound algorithm
★ Flow shop論文目次 Abstract I
Table of contents II
List of figures IV
List of tables V
Chapter 1 Introduction 1
1.1 Motivation and background 1
1.2 Problem description 2
1.3 Research objectives 3
1.4 Research methodology and framework 4
1.4.1 Research methodology 4
1.4.2 Research framework 5
Chapter 2 Literature review 6
2.1 Makespan minimization problem with lot streaming in two-machine flow shops 6
2.1.1 Lot streaming problem with continuous-sized sublots 6
2.1.2 Lot streaming problem with integer-sized sublots 9
2.2 Scheduling problem with dependent time window of waiting 10
Chapter 3 Lot streaming problem with limited waiting time constraint in two-machine flow shops 13
3.0 Notation and problem assumptions 13
3.1 Lot streaming problem with continuous-sized sublots for a single product 15
3.1.1 Linear programming formulation 15
3.1.2 Solution of linear programming model 17
3.2 Sequencing and lot streaming for multiple products problem 19
Chapter 4 Example and computational analysis 29
4.1 Example 1 29
4.2 Validation of branch-and-bound algorithm by special case 34
4.2.1 Special case without lot streaming (Yang and Chern, 1995) 34
4.2.2 Special case without waiting time constraint (Vickson, 1995) 34
4.3 Evaluation of the branch-and-bound algorithm 36
Chapter 5 Conclusion 39
5.1 Research contribution 39
5.2 Further research 40
Reference 41
Appendix 43
Appendix A: Special case without lot streaming (Yang and Chern, 1995) 43
Appendix B: Special case without waiting time constraint (Vickson, 1995) 44
Appendix C: Computational experiences of N = 5 46參考文獻 許淑芬(1998)，「具等候時間窗口限制之零工式生產排程問題」，中央大學工業管理研究所碩士論文。
黃淑娟(2000)，「雙階段流程型工廠在有限等待時間限制下之排程問題」，中原大學工業工程研究所碩士論文。
Armstrong, R., L. Lei, and S. Gu (1994), “A Bounding Scheme for Deriving the Minimal Cycle Time of a Single-transporter N-stage process with Time-window Constraint,” European Journal of Operational Research, 78, 130-140
Chen, J. and G. Steiner (1999), “Discrete Lot Streaming in Two-machine Flow Shops,” Infor, 37, 160-173.
Desrochers, M., J. Desrosiers and M. Solomon (1992), “A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows ,” Operations Research., 40, 342-354.
Desrosiers, J., Y. Dumas, E. Gelinas and M. Solomon (1995), “An Optimal Algorithm for the Traveling Salesman Problem with Time Windows,” Operations Research., 43, 367-371.
Desrosiers, J., F. Soumis and, M. Sauve (1984), “Methods for Routing with Time Windows by Column Generation,” Networks., 14, 545-565.
Desrosiers, J., F. Soumis, M. Desrochers, and M. Sauve (1986),”Methods for Routing with Time Windows,” European Journal of Operational Research, 23, 236-245.
Lei, L., and T. J. Wang (1989), “A proof: The Cyclic Hoist Scheduling Problem is NP-complete,” Working paper No.89-16, Rutger University,August.
Lei, L., and T. J. Wang (1991), “The Minimum Common-cycle Algorithm for Cycle Scheduling of Time Windows Constraints,” Management Science, 37(12), 1629-1639.
Kolen , A., A. H. G. Rinnooy Kan and H.W.J.M. Trienekens (1987), “Vehicle Routing with Time Windows,” Operations Research., 35, 266-273.
Potts, C. N. and K. R. Baker (1989), “Flowshop Scheduling with Lot Streaming,” Operations Research Letters, 8, 297-303.
Sen, A., E. Topaloglu, and O. S. Benli (1998), “Optimal Streaming of a Single Job in a Two-stage Flow Shop,” European Journal of Operational Research, 110, 42-62.
Shapiro, G. W., and H. W. Nuttle (1988), “Hoist Scheduling for a PCB Electroplating facility,” AIIE Transactions, 20(2), 157-167.
Sriskandarajah, C. and E. Wagneur (1999), “Lot Streaming and Scheduling Multiple Products in Two-machine No-wait Flowshops,” IIE Transaction, 31, 659-707.
Trietsch, D. and K. R. Baker (1993), “Basic Techniques for Lot Streaming,” Operations Research, 41, 1065-1076
Trustcott, W. (1986), “Production Scheduling with Capacity Constrained Transportation Activities,” Journal of Operational Management, 6, 333-348.
Vickson, R. G. (1995), “Optimal Lot Streaming for Multiple Products in a Two-machine Flow Shop,” European Journal of Operational Research, 85, 556-575.
Yang, D.L. and M.S. Chern (1995), “A Two-machine Flowshop Sequencing Problem with Limited Waiting Time Constraint,” Computers ind. Engng, 28, 63-70.
Yih, Y., T. P. Liang and H. Moskowitz (1993), “Robot Scheduling in a Circuit Board Production Line: a Hybrid OR/ANN Approach, ” AIIE Transactions.指導教授 沈國基(Gwo-Ji Sheen) 審核日期 2003-7-7 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit