具機器可用時間與機器合適度限制和相依整備作業之平行機台排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：50

、訪客IP：18.116.50.244

姓名

江曜君(Yao-jun Jiang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

具機器可用時間與機器合適度限制和相依整備作業之平行機台排程問題
(An Identical Parallel-Machine Scheduling Problem with the Consideration of Machine Availability, Eligibility and Dependent Setup Time)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在此研究中，我們考慮當極小化總作業之完工時間時，在具機器可用時間與機器合適度且整備作業相依化的限制下，n個不可分割的工作和m台等效平行機台的排程問題。每台機器只有某些時間區段可以被安排處理工作，每個工作也只能被安排在某些特定的機器上，而每當我們欲服務工作時其必須先執行一個整備作業好讓機台的生產環境符合此工作的需求，而此整備作業的執行時間則是由此機台的前續作業與接下來要服務的作業種類來決定的，因此我們才會稱此整備作業為相依的。
在此我們提出一個分枝界限演算法去尋找這個問題的最佳解。首先，我們修改Liao & Sheen (2007)切割時間區間的方式，將時間區間以各機台獨立的方式去做切割，再者我們將欲規劃的各工作視為不能分割的情況下去提出下界值的計算方式，最後我們提出分枝的方式與減少分枝不必要分枝的方法。而我們所提出的
方法透過我們設計的實驗可以發現兩件事情。第一我們可以發現當問題環境於機器總數相同的情況下，當我欲處理較多的工作時，倘若我們使用相依方式處理時間區間時將使得其獲得最佳解的時間與使用獨立切割時間區間的方法來的長的許多。第二，我們也可以發現當預處理的問題越大時，其下界的刪除無用的分枝效率會越來越高。

摘要(英)

In this thesis, we consider the problem of scheduling n non-preemptive jobs on m identical machines with machine availability, eligibility and dependent setup time. The problem comes from industrial applications. Each machine is not continuously available at all time and each job is only allowed to be processed on specific machines. Dependent setup is that the setup time is determined not only by that job but also by the previous job. Then we hope we will develop an efficient algorithm to solve this problem.
First, we focus on our constraint, machine availability to modify the method used in Liao & Sheen (2007) to deal with it. We divide all time epochs on each machine independently and look forward to spend less time getting our solution. Then we propose our lower bound. It doesn’t apply the usual way seem all jobs are preemptive to calculate the value of bound. I still think our jobs are not preemptive to get a value closing the actual situation. Besides, we propose branching schema, propositions and dominance rules to construct our branch and bound algorithm. Finally, through our experiment we could realize the performance of our lower bound and the decision of dealing with machine availability. We find that when the problem size becomes bigger and bigger, the lower bound we proposed can help us cut more and more meaningless bounds. Similarly, we also can find that on the same machine size when
III
we want to solve the problem with more and more jobs, we have to spend much time calculating it. On the other hand, we finally propose some comments and limitations of the studied problem in the end of the thesis.

關鍵字(中)

★ 排程
★ 分枝界限法
★ 平行機台
★ 可用時間限制
★ 合適度限制
★ 相依整備作業

關鍵字(英)

★ machine eligibility
★ dependent setup time
★ total completion time
★ parallel machine
★ branch and bound algorithm
★ machine availability
★ non-preemptive jobs

論文目次

Table of Content
Abstract II
Table of Content V
List of Tables VII
List of Figures VIII
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 2
1.3 Research objectives 3
1.4 Research Methodology and Frame Work 4
1.4.1 Research Methodology 4
1.4.2 Research Framework 4
Chapter 2 Literature review 6
2.1 Machine Availability Constraint 6
2.2 Machine Eligibility Constraint 7
2.3 Dependent setup time Constraints 7
Chapter 3 Algorithm for 9
3.1 Notations 9
3.2 Obtaining the time epoch set E and determining the time interval 10
3.3 Branching and Bound Algorithm for the Problem 12
3.3.1 A lower bound for the problem 12
3.3.2 Branching Scheme 15
3.3.3 Dominance Rules 20
3.3.4 Branch and Bound Algorithm for the Problem 23
Chapter 4 Computational Analysis 30
4.1 Test Problem Generation 30
4.2 Test Problem Optimally 31
4.3 Test Problem Efficient 34
5.1 Research Contribution 39
5.3 Further Research 40
Appendix.1 44
An example of for Branch and Bound Algorithm 44

參考文獻

1. Brucker, P., & Kravchenko, S. A. (2008). Scheduling jobs with equal processing times and time windows on identical parallel machines. Journal of Scheduling (11), pp. 4229-237.
2. Chartrand, G. (1985). Introductory Graph Theory, New York, Dover Pubns.
3. Chen, W. J. (2006). Minimizing total flow time in the single-machine scheduling problem with periodic maintenance. Journal of Operational Research Society (57), pp. 10–415.
4. Chen, W. (2009). Scheduling with dependent setups and maintenance in a textile company. Computers & Industrial Engineering (57), pp. 867–873.
5. Chen, Z.L. & Powell, W. (2003). Exact algorithms for scheduling multiple families of jobs on parallel machines. Naval Research Logistics (50), pp. 823–840.
6. Lee, A., Huang, C. & Chung, S. (2007). Minimizing the Total Completion Time for the TFT-Array Factory Scheduling Problem (TAFSP) . Lecture Notes in Computer Science (4705), pp. 767-778.
7. Lee, W., Lin, Y. & Wu, C. (2010). A branch and bound and heuristic algorithm for the single-machine time-dependent scheduling problem. The International Journal of Advanced Manufacturing Technology (47), pp. 1217–1223.
43
8. Liao, L., & Sheen, G. (2007). Parallel machine scheduling with machine availability and eligibility constraints. European Journal of Operational Research (184), pp. 458–467.
9. Lin, C. F. (2006). Branch and bound algorithm for parallel machine scheduling with availability and eligibility constraints. Institute of Industrial Management, National Central University.
10. Li, Y. W. (2004). Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research (156), pp. 261-266.
11. Mosheiov, G. (1994). Minimizing the sum of job completion on capacitated parallel machines. Mathematical and Computer Modeling (20), pp. 91–99.
12. Nessah, R. (2007). An exact method for problem. Computers & Operations Research (34), pp. 2840 – 2848.
13. Nessah, R., Yalaoui, F., & Chu, C. (2008). A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates. Computers & Operations Research (35), pp. 1176 – 1190.
14. Pinedo, M. (2002). Scheduling: Theory, Algorithm and System (2th ed). New York: Prentice-Hall.

指導教授

沈國基(Gwo-ji Sheen)

審核日期

2011-7-19

推文