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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:黃逸華
研究生(外文):Yi-Hua Huang
論文名稱:批量機台具合適度限制及等候時間限制求最小化總完工時間之生產排程問題
論文名稱(外文):The Parallel Batch Machine Scheduling with Machine Eligibility and Waiting Time Constraints to Minimize Total Completion Time
指導教授:沈國基沈國基引用關係
指導教授(外文):Gwo-Ji Sheen
學位類別:碩士
校院名稱:國立中央大學
系所名稱:工業管理研究所
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2018
畢業學年度:106
語文別:英文
論文頁數:56
中文關鍵詞:總完工時間平行機台批量加工等候時間限制
外文關鍵詞:Parallel machinebatching processingwaiting time constraintstotal completion time
相關次數:
  • 被引用被引用:0
  • 點閱點閱:94
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
在本研究中,我們研究
In this research, we research the scheduling problem with n jobs that can be divided into batches and m parallel machines under availability constraint. Due to the eligibility constraint, each jobs has its own recipe, not all m machines can process job’s recipe. And the jobs have the waiting time before the processing, they can process together when their arrival time smaller than the batch’s waiting time. The objective of our scheduling problem is to minimize the total completion time.
In order to find the best solution to this problem, this research proposes a branch and bound algorithm. In the algorithm of this study, first, we resort a sequence according to the job ‘s arrival time. The available batch positions of the machines are branched, and we determine whether schedule the job to process on the batch of the machine, and then how to plan the remaining job entering the same or different batches.
Contents
摘要 i
Abstract ii
Contents iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Research background and motivation 1
1.2 Problem definition 2
1.3 Research objective 4
1.4 Research methodology 4
1.5 Research framework 5
Chapter 2 Literature Review 7
2.1 Parallel machine scheduling with batch processing 7
2.2 Scheduling problem with eligibility constraints 8
2.3 Parallel machine with release time constraint 8
Chapter 3 Methodology 10
3.1 Notation 10
3.2 Branching scheme 11
3.3 Propositions 16
3.4 Bounding scheme 20
3.5 Branch and bound Algorithm 21
Chapter 4 Analysis 25
4.1 Instance Generation 25
4.2Validation of the branch and bound algorithm 26
4.3 Performance of the branch and bound algorithm 27
Chapter 5 Conclusion 31
5.1 Research Contribution 31
5.2 Research Limitation 32
5.3 Future Research 32
Reference 33
Appendix 35
List of Figures
Figure 1. Demonstration of machine environment. 3
Figure 2. Research framework. 6
Figure 3. Searching tree of branching scheme 15
Figure 4. If Si,d<Si,d', we don’t branch out node d' 17
Figure 5. SPT sequencing of batches 18
Figure 6. Proof of Proposition 2 – original schedule 19
Figure 7. Proof of Proposition 2 – after pairwise interchange schedule 19
Figure 8. Flow chart of branch and bound algorithm 24
Figure 9. Percentage of nodes eliminated by branch and bound algorithm 28
Figure A. 1 Execution of the branch and bound on the numerical example 36
Figure A. 2 The beginning of the tree is root node n1 37
Figure A. 3 The branching out child node n2 from root node n1 38
Figure A. 4 The branching out child node n3 from node n2 40
Figure A. 5 The branching out child node n4 from node n3 42
Figure A. 6 Backtracking from node n4 and right branching node n5 44
List of Tables
Table 1. Job data 25
Table 2. Machine data 25
Table 3. Validation results of branch and bound algorithm 33
Table 4. Instance that can solve by our branch and bond algorithm 36
[1] Ahmadi, J. H., Ahmadi, R. H., Dasu, S., & Tang, C. S. Batching and scheduling jobs on batch and discrete processors. Operations research, 40(4), 750-763. (1992).
[2] Allahverdi, A. The two-and m-machine flowshop scheduling problems with bicriteria of makespan and mean flowtime. European Journal of Operational Research, 147(2), 373-396. (2003).
[3] Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., & Van De Velde, S. L. Scheduling a batching machine. Journal of scheduling, 1(1), 31-54. (1998).
[4] Chandru, V., Lee, C. Y., & Uzsoy, R. Minimizing total completion time on batch processing machines. THE INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 31(9), 2097-2121. (1993).
[5] Cheng, B., Yang, S., Hu, X., & Chen, B. Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes. Applied Mathematical Modelling, 36(7), 3161-3167. (2012).
[6] Li, S. A hybrid two-stage flowshop with part family, batch production, major and minor set-ups. European Journal of Operational Research, 102(1), 142-156. (1997).
[7] Li, X., Ishii, H., & Masuda, T. Single machine batch scheduling problem with fuzzy batch size. Computers & Industrial Engineering, 62(3), 688-692. (2012).
[8] Liao, L. W., & Sheen, G. J. Parallel machine scheduling with machine availability and eligibility constraints. European Journal of Operational Research, 184(2), 458-467. (2008).
[9] Mazdeh, M. M., Sarhadi, M., & Hindi, K. S. A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times. Computers & Operations Research, 35(4), 1099-1111. (2008).
[10] Pinedo, M. L. Scheduling: theory, algorithms, and systems. Springer. (2016).
[11] Salem, A., Anagnostopoulos, G. C., & Rabadi, G. A branch-and-bound algorithm for parallel machine scheduling problems. In Harbour, Maritime & Multimodal Logistics Modeling and Simulation Workshop, Society for Computer Simulation International (SCS) (pp. 88-93). (2000, October).
[12] Shim, S. O., & Kim, Y. D. A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property. Computers & Operations Research, 35(3), 863-875. (2008).
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔