Tabu search algorithm for flexible job shop with batch processing to minimize the makespan

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：149

、訪客IP：18.116.13.113

姓名

唐祈(Chi Tang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

(Tabu search algorithm for flexible job shop with batch processing to minimize the makespan)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2027-7-31以後開放)

摘要(中)

本研究主旨在於探討彈性式零工式生產上考慮批次生產以及機台限制的排程問題，
目標為最小化最大完工時間。此排程問題是半導體產業實務上所面對的問題。
針對此問題，我們使用 batch-oblivious 分離圖來表示並且提出建築於此分離圖的禁
忌搜尋法來解決此問題。為使禁忌搜尋法可以有效地處裡批次生產，我們應用了一計算
各工件起始時間的過程，透過在遍歷整個分離圖的過程中，去盡可能的填滿個個批次，
提升各個批次的使用率。在實驗部分，我們透過與不同指標性的數值結果比較，去證明
我們所提出之禁忌搜尋法的通用性和適用性。

摘要(英)

In this paper, we study a scheduling problem on the flexible job shop problem with
batching processing and machine eligibility constraint which objective is minimizing the
makespan. We use the novel disjunctive graph, the batch-oblivious disjunctive graph, to
represent this scheduling problem.
We propose the tabu search algorithm based on the batch-oblivious disjunctive graph to
solve the problem. More addition, to tackle the batching process, we apply the adaptive start
computation procedure to take batching decisions during traversals disjunctive graph. In
computational results, we compare our result with benchmark instances of different problems
prove the applicability of our algorithm.

關鍵字(中)

★ 彈性式零工式生產
★ 批量
★ 機台限制
★ 禁忌搜尋法
★ 最晚完工時間

關鍵字(英)

★ Flexible job shop
★ Batch processing
★ Makespan
★ Machine eligibility
★ Tabu search

論文目次

摘要 i
Abstract ii
Table of contents iii
List of figures v
List of tables vi
Chapter 1 Introduction 1
1.1 Research motivation and background 1
1.2 Problem definition 3
1.3 Research objective 5
1.4 Research methodology 5
1.5 Research framework 6
Chapter 2 Literature Review 8
2.1 Flexible Job-shop scheduling problem 8
2.2 Batch process 10
2.3 Disjunctive graph 11
Chapter 3 Research Methodology 12
3.1 The disjunctive graph representation 12
3.2 Tabu Search 15
3.2.1 Initial solution 16
3.2.2 Move definition 17
3.2.3 Neighborhood structure 19
3.2.4 Evaluation of moves 22
3.2.5 Adaptive start date computation 23
3.2.6 Tabu list 25
Chapter 4 Computation result 26
4.1 Flexible job shop instances of Brandimarte (1993) 26
4.2 Flexible job shop instances of Ham (2017) 29
4.3 Performance of new hierarchy structure of moves 31
Chapter 5 Conclusion 34
5.1 Research contribution 34
5.2 Research limitation 35
5.3 Future research 35
Reference 36
Appendix A 39

參考文獻

[1] Bierwirth, C., & Kuhpfahl, J. (2017). Extended GRASP for the job shop scheduling problem with total weighted tardiness objective. European Journal of Operational Research, 261(3), 835-848.
[2] Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations research, 41(3), 157-183.
[3] Brucker, P., & Schlie, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45(4), 369-375.
[4] Carlier, J., & Pinson, É. (1989). An algorithm for solving the job-shop problem. Management science, 35(2), 164-176.
[5] Chaudhry, I. A., & Khan, A. A. (2016). A research survey: review of flexible job shop scheduling techniques. International Transactions in Operational Research, 23(3), 551-591.
[6] Dauzère-Pérès, S., & Paulli, J. (1994). Solving the general multiprocessor job-shop scheduling problem. Management Report Series, 182.
[7] Dauzère-Pérès, S., & Paulli, J. (1997). An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annals of Operations Research, 70, 281-306.
[8] Fowler, J. W., & Mönch, L. (2021). A survey of scheduling with parallel batch (p-batch) processing. European Journal of Operational Research.
[9] Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117-129.
[10] Glover, F., & McMillan, C. (1986). The general employee scheduling problem. An integration of MS and AI. Computers & operations research, 13(5), 563-573.
[11] Hurink, J., Jurisch, B., & Thole, M. (1994). Tabu search for the job-shop scheduling problem with multi-purpose machines. Operations-Research-Spektrum, 15(4), 205-215.
[12] Ham, A. (2017). Flexible job shop scheduling problem for parallel batch processing machine with compatible job families. Applied Mathematical Modelling, 45, 551-562.
[13] Jansen, K., Mastrolilli, M., & Solis-Oba, R. (2005). Approximation algorithms for flexible job shop problems. International Journal of Foundations of Computer Science, 16(02), 361-379.
[14] Knopp, S., Dauzère-Pérès, S., & Yugma, C. (2017). A batch-oblivious approach for complex job-shop scheduling problems. European Journal of Operational Research, 263(1), 50-61.
[15] Liouane, N., Saad, I., Hammadi, S., & Borne, P. (2007). Ant systems & local search optimization for flexible job shop scheduling production. International Journal of Computers Communications & Control, 2(2), 174-184.
[16] Liu, H., Abraham, A., & Wang, Z. (2009). A multi-swarm approach to multi-objective flexible job-shop scheduling problems. Fundamenta Informaticae, 95(4), 465-489.
[17] Mason, S. J., Fowler, J. W., Carlyle, W. M., & Montgomery, D. C. (2005). Heuristics for minimizing total weighted tardiness in complex job shops. International Journal of Production Research, 43(10), 1943-1963.
[18] Mathirajan, M., & Sivakumar, A. I. (2006). A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. The International Journal of Advanced Manufacturing Technology, 29(9), 990-1001.
[19] Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management science, 42(6), 797-813.
[20] Ovacik, I.M., R. Uzsoy. (1997). Decomposition Methods for Complex Factory Scheduling Problems. Kluwer Academic Publishers.
[21] Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: A review. European journal of operational research, 120(2), 228-249.
[22] Paulli, J. (1995). A hierarchical approach for the FMS scheduling problem. European Journal of Operational Research, 86(1), 32-42.
[23] Pinedo, M. (2008). Scheduling: Theory, Algorithms, and System, Springer, Berlin.
[24] Roy, B., & Sussmann, B. (1964). Scheduling problems with disjunctive constraints. Note ds, 9.
[25] Sobeyko, O., & Mönch, L. (2016). Heuristic approaches for scheduling jobs in large-scale flexible job shops. Computers & Operations Research, 68, 97-109.
[26] Xing, L. N., Chen, Y. W., & Yang, K. W. (2009). An efficient search method for multi-objective flexible job shop scheduling problems. Journal of Intelligent manufacturing, 20(3), 283-293.
[27] Yugma, C., Dauzère-Pérès, S., Artigues, C., Derreumaux, A., & Sibille, O. (2012). A batching and scheduling algorithm for the diffusion area in semiconductor manufacturing. International Journal of Production Research, 50(8), 2118-2132.
[28] Zhang, G., Shao, X., Li, P., & Gao, L. (2009). An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering, 56(4), 1309-1318.
[29] Zandieh, M., Mahdavi, I., & Bagheri, A. (2008). Solving the flexible job-shop scheduling problem by a genetic algorithm. Journal of Applied Sciences, 8(24), 4650-4655.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2022-7-5

推文