利用分支界限法求具有機台可用時間限制與工作可分割特性的平行機台排程問題之最佳解

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：102

、訪客IP：3.142.98.147

姓名

鄭善尉(Shan-wei Cheng) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

利用分支界限法求具有機台可用時間限制與工作可分割特性的平行機台排程問題之最佳解
(A Branch and Bound Algorithm for Parallel Machine Scheduling with Availability and Job Preemption Constraints)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在此研究中，我們考慮當極小化最大總作業之完工時間時，在具機器可用時間且工作具有可分割性限制下，n個可以分割的工作和m台平行機台的排程問題。每台機器只有某些時間區段可以被安排處理工作。所有的機台、工作與機台的可用時間區段，在一開始都是已知的。
我們提出一個分支界限演算法去尋找這個問題的最佳解。首先，我們修改Liao & Sheen (2008)切割時間區間的方式，將時間區間以各機台獨立的方式去做切割。其次，我們提出啟發式演算法，利用以最短剩餘時間加工(SRPT)的法則得出的可行解，當作其上界限值。最後，我們提出分枝的方式與減少分枝不必要分枝的方法。
實驗的分析顯示，分支界限法所產生的節點數比例非常小，顯示提出的淘汰法則強而有力。我們的演算法能用於七個工作和三台機器問題下而得到一個最佳解。

摘要(英)

In this paper, we consider the problem of scheduling n jobs on identical machines with machine availability and job preemption constraints when minimizing the total completion time. Each machine is not continuously available for processing at all time and job preemption is allowed. At the beginning, each job of processing time and the time of machine available is known.
We propose a branch and bound algorithm to find out the optimal solution. First, we focus on our constraint, machine availability to modify the method used in Liao & Sheen (2008) to deal with it. Second, we propose our bounding scheme, branching scheme, and propositions used in branch and bound algorithm. In the end, we use these bounding scheme and dominance rules to eliminate unnecessary nodes of branch and bound algorithm.
Computational analysis shows that the effectiveness of eliminating rules proposed is powerful and very low percentage of nodes is generated by the branch and bound algorithm. Our algorithm can get the optimal solution for the problem with up to 7 jobs and 3 machines.

關鍵字(中)

★ 排程
★ 分支界限法
★ 平行機台
★ 可用時間限制

關鍵字(英)

★ Scheduling
★ branch and bound algorithm
★ parallel machine
★ machine availability

論文目次

Table of Content
摘要 i
Abstract ii
Table of Content iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem description 3
1.3 Research objectives 3
1.4 Research Methodology and Framework 4
1.4.1 Research Methodology 4
1.4.2 Research Framework 4
Chapter 2 Literature Review 6
2.1 Scheduling Problem with Availability Constraint 6
2.2 Branch and Bound Algorithm on Parallel Machine for Total Completion Time 7
Chapter 3 Algorithm for P_m,〖NC〗_win ｜ pmtn┤｜ ∑_(j=1)^n▒C_j 10
3.1 Notations 10
3.2 Obtaining the time epoch set E and determining the available time interval T_(i,l) 11
3.3 Branching and Bound Algorithm for the Problem 13
3.3.1 Branching Scheme 13
3.3.2 Bounding Scheme 14
3.3.2.1 Lower Bound 15
3.3.2.2 Upper Bound 15
3.3.3 Dominance Rules 19
3.3.4 Branch and Bound Algorithm for the Problem P:〖 P〗_m,〖NC〗_win ｜ pmtn┤｜ ∑_(j=1)^n▒C_j 23
Chapter 4 Computational Analysis 27
4.1 Test Problem Generation 27
4.2 Validation of the Branch and Bound Algorithm 28
4.3 Performance of Our Branch and Bound Algorithm 33
Chapter 5 Conclusion 39
5.1 Research Contribution 39
5.2 Research Limitation 39
5.3 Further Research 40
References 41
Appendix. . 44

參考文獻

References
[1] 簡媜富等主編 (2005), “半導體製造技術與管理,” 清大出版社, 新竹市.
[2] Adiri, I., J. Bruno, E. Frostig, and A.H.G. Rinnooy Kan (1989), “Single machine flow-time scheduling with a single breakdown,” Acta Informatica, 26(7), 679-696.
[3] Brucker, P., and S.A. Kravchenko (2008), “Scheduling jobs with equal processing times and time windows on identical parallel machines,” J. Sched., 11, 229–237.
[4] Chen, W.J. (2006), “Minimizing total ﬂow time in the single-machine scheduling problem with periodic maintenance,” Journal of the Operational Research Society, 57, 410–415.
[5] Horn, W.A. (1973), “Technical Note- minimizing average flow time with parallel machines,” Operations Research, 21(3), 846-847.
[6] Hmid, S. D. R., and T.T. Mohammad (2008), “Study of Scheduling Problems with Machine Availability Constraint,” Journal of Industrial and Systems Engineering, 1(4), 360-383.
[7] Kacem, I., Chu, C., and A. Souissi (2006), “Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times,” Computers and Operations Research, 180, 396–405.
[8] Liao, C.J., C.W. Chao and C.H. Lin (2009), “Minimizing the sum of job completion times on capacitated two-parallel machines,” European Journal of Operational Research, 197, 475–481.
[9] Lee, C.Y., and S.D. Liman (1992), “Single-machine flow time scheduling with scheduled maintenance,” Acta Informatica, 29(4), 375-382.
[10] Liu, Z., and E. Sanlaville (1995), “Preemptive scheduling with variable profile, precedence constraints and due dates,” Discrete Applied Mathematics, 58, 253-280.
[11] Liao, L.W., and G.J. Sheen (2008), “Parallel machine scheduling with machine availability and eligibility constraints,” European Journal of Operational Research, 184, 458–467.
[12] Mosheiov, G., (1994), “Minimizing the Sum of Job Completion on Capacitated Parallel Machines,” Mathl. Comput. Modelling, 20(6), 91-99.
[13] Mellouli, R., C. Sadﬁ, C. Chu and I. Kacem (2009), “Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times,” European Journal of Operational Research, 197, 1150–1165.
[14] Ma, Y., C. Chu and C. Zuo (2010), “A survey of scheduling with determinstic machine availability constraints,” Computers & Industrial Engineering, 58, 199-211.
[15] Nessah, R., F. Yalaoui and C. Chu (2008), “A branch and bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates,” Computers and Operations Research, 35(4), 1176-1190.
[16] Ozlen, M., and S. Webster (2010), “Minimising total flow-time on two parallel machines with planned downtimes and resumable jobs,” International Journal of Production Research, 48(1), 201-226.
[17] Pinedo, M. (2008), Scheduling: Theory, Algorithm and System (3th ed), New York: Prentice-Hall.
[18] Reza, H., and M. Taghi (2008), “Study of Scheduling Problems with Machine Availability Constraint,” Journal of Industrial and Systems Engineering, 1, 360-383.
[19] Sanlaville, E., G. Schmidt (1995), “Machine scheduling with availability constraints,” Acta Informatica, 35, 795–811.
[20] Su, L.H., (2009), “Scheduling on identical prarllel machines to minimize total compltion time with deadline and machine eligibility constraints,” The International Journal of Advanced Manufacturing Technology, 40, 572-581.
[21] Su, L.H., T.C.E. Cheng and F.D. Chou (2012), “A minimum-cost network ﬂow approach to preemptive parallel-machine scheduling,” Computers & Industrial Engineering, 64, 453–458.
[22] Schmidt, G. (2000), “Scheduling with limited machine availability,” European Journal of Operational Research, 121, 1-15.
[23] Wang, G., H. Sun and C. Chu (2005), “Preemptive Scheduling with Availability Constraints to Minimize Total Weighted Completion Times,” Annals of Operations Research, 133, 183–192.
[24] Yalaoui, F., and C. Chu (2006), “A new exact method to solve the problem,” International Journal of Production Economics, 100, 168–179.

指導教授

沈國基

審核日期

2013-7-19

推文