批量機台具合適度限制及等候時間限制求最小化總完工時間之生產排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：138

、訪客IP：18.117.182.179

姓名

黃逸華(Yi-Hua Huang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

批量機台具合適度限制及等候時間限制求最小化總完工時間之生產排程問題
(The Parallel Batch Machine Scheduling with Machine Eligibility and Waiting Time Constraints to Minimize Total Completion Time)

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

在本研究中，我們研究 ?? 個可以進行批次加工的工作跟 ?? 台平行機台的排程問題，這些平行機台的處理時間是不同的，針對不同機台的合適度條件，即是說工作有適合自己加工的機台，在符合的機台環境下，該工作才能加工，另外工作可以集合成批次再進到機台內開始進行加工，我們研究的目標是在找最小化的總完工時間。
為了求出這個問題的最佳解，本研究提出了一個分枝定界的演算法，在本研究的演算法中首先針對每個工作抵達機台的時間作排列，將率先抵達的工作針對每個機台的可用批次位置做分枝，決定工作在合適機台的批次上加工，接著在考慮剩餘的工作進入相同或不同批次時，該如何作規劃。

摘要(英)

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.

關鍵字(中)

★ 總完工時間
★ 平行機台
★ 批量加工
★ 等候時間限制

關鍵字(英)

★ Parallel machine
★ batching processing
★ waiting time constraints
★ total completion time

論文目次

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 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).

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2018-8-22

推文