以分支定界法求解具批量機台與時間延滯之零工式生產排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：7

、訪客IP：18.224.180.183

姓名

相虹(Hsiang Hung) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以分支定界法求解具批量機台與時間延滯之零工式生產排程問題
(A Branch and Bound Algorithm for Job Shop Problem with a Batch Machine and Time-Lags)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本研究探討用分支定界法求解零工式生產排程的問題，其環境具有批量生產與時間延遲之限制特性，批量生產為機台上指定之作業可以被批量加工。而等候時間延滯上的限制中，因考量到批量機台的加工，故當作業從前一個工作站離開後，該作業不需要等待最小的時間，可以直接進入下個工作站，但仍需要在一定的時間之內抵達下一個工作站。
因此時間延滯上的限制需要考慮到當工件抵達機台上可以開始被加工的時間，再加上指定機台具有批量生產之功能，希望藉由批量生產來減少所需的完工時間。為了解決以上研究內容中提出的限制問題，我們將在本研究中發展一分支定界的演算法，並加入批量生產的限制，目標為在此環境下能夠得到最小的完工時間。

摘要(英)

The main purpose of this research is to discuss a branch and bound algorithm for job shop problem with a batch machine and time-lags, the environment have the batches and the time lags, batch processing of machine indicated on the workpiece can be batch processing, and waiting time constraints, when after the completion of the artifacts used workstation, over a period of time is needed to enter to the next station for processing, and the workpiece must wait for a certain minimum time, at the same time wait for no more than a certain time.
Therefore, the waiting time limit needs to take into account the time that each workpiece can start processing. In addition, some limited machines have the capacity of mass production. It is hoped that by batch processing, the required completion time can be reduced. To solve this problem, we will develop a branch and bound algorithm, and the objective is minimize the maximum makespan.

關鍵字(中)

★ 批量生產
★ 時間延滯
★ 分支定界法
★ 零工式

關鍵字(英)

★ Batch
★ Time-Lags
★ Branch and Bound
★ Job Shop

論文目次

Contents
摘要 i
Abstract ii
Contents ii
List of figures v
List of tables vi
Chapter 1 Introduction 1
1.1 Research background and motivation 1
1.2 Problem definition 3
1.3 Research objectives 5
1.4 Research methodology 5
1.5 Research framework 6
Chapter 2 Literature Review 8
2.1 Job shop problem 8
2.2 Job shop problem with time-lags 9
2.3 Job shop problem with batches 11
Chapter 3 Methodology 12
3.1 Notations 12
3.2 Problem statement 15
3.3 Proposition 18
3.4 Branching scheme 20
3.5 Adjustment of starting time intervals, release times and tail values 23
3.6 Bounding scheme 23
3.7 Algorithms 26
Chapter 4 Computational Analysis 30
4.1 Instance Generation 30
4.2 Validation of the branch and bound algorithm 31
4.3 Performance of the branch and bound algorithm 32
4.3.1 Performance of nodes eliminated 32
4.3.2 Percentage of nodes eliminated by a specific proposition 33
4.3.3 Maximum size of instance 35
Chapter 5 Conclusion 37
5.1 Research Contribution 37
5.2 Research Limitation 38
5.3 Further Research 38
Reference 39
Appendix 41

參考文獻

[1] Adams, J., Balas, E., & Zawack, D. (1988). The Shifting Bottleneck Procedure for Job Shop Scheduling. Management science 34(3),391-401.
[2] Artigues, C., Huguet, M.-J., & Lopez, P. (2011). Generalized disjunctive constraint propagation for solving the job shop problem with time lags. Engineering Applications of Artificial Intelligence, 24(2), 220–231.
[3] Baker KR. (1974), Introduction to Sequencing and Scheduling. Wiley: New York.
[4] Balas, E. (1969). Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm. Operations Research, 17(6), 941–957.
[5] Brucker, P., Jurisch, B., and Sievers, B. (1994). A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49(1-3), 107–127.
[6] Carlier, J. (1982). The one-machine sequencing problem. European Journal of Operational Research, 11(1), 42–47.
[7] Carlier, J., & Pinson, E. (1989). An Algorithm for Solving the Job-Shop Problem. Management Science, 35(2), 164–176.
[8] Carlier, J., & Pinson, E. (1990). A practical use of Jackson’s preemptive schedule for solving the job shop problem. Annals of Operations Research, 26(1-4), 269–287.
[9] Carlier, J., & Pinson, E. (1994). Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research, 78(2), 146–161.
[10] Caumond, A., Lacomme, P., & Tchernev, N. (2008). A memetic algorithm for the job-shop with time-lags. Computers & Operations Research, 35(7), 2331–2356.
[11] Dauzere-Peres, S., & J.B. Lasserre (1993). A modified shifting bottleneck procedure for job-shop scheduling. International Journal of Production Research, 31(4), 923–932.
[12] Giffler, B., & Thompson, G. L. (1960). Algorithms for Solving Production-Scheduling Problems. Operations Research, 8(4), 487–503.
[13] Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979). Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Annals of Discrete Mathematics, 287–326.
[14] Gonzalez, T., & Sahni, S. (1978). Flowshop and Job shop Schedules: Complexity and Approximation. Operations Research, 26(1), 36–52.
[15] 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.
[16] Pinedo, Michael L. (2008). Scheduling Theory, Algorithms, and Systems. Third Edition. Chapter 7, 179-189.
[17] Sheen, G.-J., & Liao, L.-W. (2007). A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags. European Journal of Operational Research, 181(1), 102–116.
[18] Tangudu, S. K., & Kurz, M. E. (2006). A branch and bound algorithm to minimise total weighted tardiness on a single batch processing machine with ready times and incompatible job families. Production Planning & Control, 17(7), 728–741.
[19] Wang, J., & Luh, P. B. (1997). Scheduling Job Shops with Batch Machines Using the Lagrangian Relaxation Technique. European Journal of Control, 3(4), 268–279.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2020-8-18

推文