在機器可用時間及合適度和工作群組限制下平行機台求極小化最晚完工時間之排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：69

、訪客IP：3.143.218.78

姓名

徐嘉駿(Chia-Chun Hsu) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

在機器可用時間及合適度和工作群組限制下平行機台求極小化最晚完工時間之排程問題
(Parallel machine scheduling with machine availability, eligibility and job family constraints for optimizing minimum makespan)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

本研究主旨在考慮極小化最晚完工時間之排程問題，首先探討n個可切割的工作在m台平行機台的排程問題，其中機器受限於可用時間與合適度的限制條件，而工作之間也有工作群組的限制。接著將問題延伸到一般性的n個不可切割工作在m台平行機台之排程問題。其限制條件有，機台無法一直處於可接受處理的狀態，例如：機台的損壞、維修；每個工作擁有其專有的特性，所以每個工作只能被安排在特定的機台接受服務；某些特性相近的工作會屬於同一個工作群組，當屬於同一個工作群組的工作要在同一台機台的同一個可用時間內接收服務，則將只能選擇其中之一接受服務。
我們首先提出結合最大流量法和二元搜尋法去求得在工作可切割的環境下的最佳解，接下來我們探討工作不可分割的情況下的延伸問題，首先將在工作可切割的環境下所得到的最佳解值，與我們所呈現的分支界限法每個節點所算出的下限值取較大者當分支界限法的下限值，再利用最大處理時間優先法則求得問題的上限值。最後我們提出三個優先法則來增加我們所提出的分支界限法的演算效率。
從數值分析的結果中可以呈現出，我們所提出的優先法則有效率的刪除掉一些不必要產生的節點。我們所提出的演算法能用於7個工作、5台機台和3個工作群組的問題下求得最佳解。

摘要(英)

In this paper we first consider the scheduling problem of n preemptive jobs on m identical parallel machine with machine availability, eligibility and job family constraints when minimizing the maximum completion time. Then we extend the scheduling problem to n non-preemptive jobs. Each machine could not available all time such as machine breakdown or preventive maintenance. Each job has its own characteristics, so it could only be processed on specified machines. Some similar jobs belong to the same family, it means that only one job of the family can be processed on the same availability interval of machine.
We propose a maximum network flow and a binary search algorithm to solve the preemptive problem, and use its solution to compare with each node of lower bound by our propose branch and bound algorithm, then we obtain the bigger one to be the lower bound of non-preemptive problem, and use the longest processing time first rule (LPT) to find an upper bound. Finally, we provide three dominance rules to increase the efficiency of the branch and bound algorithm.
Computational analysis shows that dominance rules could effectively eliminate unnecessary nodes. Our algorithm could get the optimal solution for the problem with up to 7 jobs, 5 machines, and 3 job families effectively.

關鍵字(中)

★ 機器合適度
★ 工作群組
★ 最大流量
★ 排程
★ 分支界限法
★ 機器可用時間
★ 平行機台

關鍵字(英)

★ job family
★ eligibility constraint
★ availability constraint
★ parallel machine
★ branch and bound
★ maximum network flow
★ Scheduling

論文目次

中文摘要 i
Abstract ii
致謝 iii
Table of Content iv
List of Figures vi
List of Tables vii
Chapter 1 Introduction 1
1.1 Background and motivation 1
1.2 Problem definition 2
1.3 Research objectives 4
1.4 Research methodology and framework 4
1.4.1 Research methodology 4
1.4.2 Research framework 5
Chapter 2 Literature review 7
2.1 Machine availability constraints 7
2.2 Machine eligibility constraints 8
2.3 Machine availability and eligibility constraints 9
2.4 Job family constraints 10
Chapter 3 Methodology of the scheduling problem 12
3.1 Notations 12
3.2 Minimizing maximum makespan 14
3.2.1 Example 1 for the base problem 15
3.2.2 Obtain the time epoch set E and determine time interval by ranking all 15
3.2.3 Constructing network for the base problem with 17
3.2.4 Obtain the unit time epoch set and determine unit capacity of time interval 19
3.2.5 Proposed algorithm for solving the problem 23
3.2.5.1 Verifying the feasibility of the problem 23
3.2.5.2 Determining a lower bound and an upper bound of the optimal 26
3.3 Branch and bound algorithm 28
3.3.1 Branching scheme 29
3.3.2 Bounding scheme 34
3.3.2.1 Lower bound 35
3.3.2.2 Upper bound 35
3.3.3 Dominance rule 37
3.3.4 Branch and bound algorithm for 38
Chapter 4 Computational Analysis 41
4.1 Data generation 41
4.2 Validation of the branch and bound algorithm 42
4.3 Performance of our branch and bound algorithm 45
Chapter 5 Conclusion 51
5.1 Research Contribution 51
5.2 Research Limitation 51
5.3 Further Research 52
Reference 53

參考文獻

[1] Ahuja, R.K., T.L. Magnanti and J.B.Orlin (1993), Network flows: Theory, Algorithm, and Applications.
[2] Azizoglu, M., S. Webster (2001), scheduling a batch processing machine with incompatible job families. Computers & Industrial Engineering 39 325-335.
[3] Balasubramanian, H., L. Monch, J. Fowler, and M. Pfund (2004), Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness. International Journal of Production Research 42 1621-1638.
[4] Blazewicz, J., M. Drozdowski, P. Formanowicz, W. Kubiak, and G. Schmidt (2000), Scheduling preemptable tasks on parallel processors with limited availability. Parallel Computing 26 1195-1211.
[5] Blazewicz, J., P. Dell’Olmo, M. Drozdowski, P. Maczka (2003), Scheduling multiprocessor tasks on parallel processors with limited availability. European Journal of Operational Research 149 377-389.
[6] Bodlaender, H.L., Klaus Jansen, Gerhard J. Woeginger (1994), Scheduling with incompatible jobs. Discrete Applied Mathematics 55 219-232.
[7] Brucker, P., Bernd Jurisch, and Andreas Kramer (1997), Complexity of scheduling problems with multi-purpose machines. Annals of Operations Research 70 57-73.
[8] Centeno, G., R.L. Armacost (1997), Parallel machine scheduling with release time and machine eligibility restrictions. Computers & Industrial Engineering 33(1-2) 273-276.
[9] Centeno, G., R.L. Armacost (2004), Minimizing makespan on parallel machines with release time and machine eligibility restrictions. International Journal of Production Research 42(6) 1243-1256.
[10] Gharbi, A., Mohamed Haouari (2005), Optimal parallel machines scheduling with availability constraints. Discrete Applied Mathematics 148 63-87.
[11] Graham, R.L., E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan (1979), Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics 5 287-326
[12] Horn, W.A. (1974), Some simple scheduling algorithm. Naval Research Logistics Quarterly 21 177-185.
[13] Huo, Y., Leung, J.Y.-T., Wang, X. (2008), Preemptive scheduling algorithms with nested and inclusive processing set restrictions. Working paper, Department of Computer Science, New Jersey Institute of Technology, Newark, NJ, USA.
[14] Hwang, H.C., S.Y. Chang (1998), Parallel machine scheduling with machine shutdown. Computers & Mathematics with Applications 36 21-31.
[15] Labetoulle, J., E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnoy Kan (1984), Preemptive scheduling of uniform machines subject to release dates. Progress in Combinational Optimization (Academic Press, New York) 245-261.
[16] Lai (2007), Parallel machine scheduling with machine availability, eligibility and job incompatible constraints. National Central University Master Thesis.
[17] Lee, C.Y (1991), Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics 30 53-61.
[18] Lee, C.Y., Y. He, and G. Tang (2000), A note on “parallel machine scheduling with non-simultaneous machine available time”. Discrete Applied Mathematics 100 133-135.
[19] Leung, J.Y.-T., Chung-Lun Li (2008), Scheduling with processing set restrictions: a survey. Int. J. Production Economics 116 251-262.
[20] Liao, L.W (2006), Parallel machine scheduling with machine availability and eligibility constraints. National Central University Doctor Thesis.
[21] Lin, Y., W. Li (2004), Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research 156 261-266.
[22] Ma, Y., Chengbin Chu, and Chunrong Zuo (2010), A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering 58 199-211.
[23] Malve, S., Reha Uzsoy (2008), A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research 34 3016-3028.
[24] Mehta, S.V., R. Uzsoy (1998), Minimizing total tardiness on a batch processing machine with incompatible job families. IIE Transactions 30 165-178.
[25] Pinedo, M. (2002), Scheduling: Theory, Algorithms and Systems (2nd edition). Englewood Cliffs, NJ: Prentice-Hall.
[26] Pinedo, M. (2008), Scheduling: Theory, Algorithms and Systems (third edition). Operations Research (Springer, New York).
[27] Saidy, H.R.D., M. T. T.-Fard (2008), Study of scheduling problems with machine availability constraint. Journal of Industrial and Systems Engineering 1 360-383.
[28] Sanlaville, E. (1995), Nearly online scheduling of preemptive independent tasks. Discrete Applied Mathematics 57 229-241.
[29] Sanlaville, E., Giinter Schmidt (1998), Machine scheduling with availability constraints. Acta Informatica 35 795-811
[30] Schmidt, G. (1988), Scheduling independent tasks with deadlines on semi-identical processors. Journal of the Operational Research Society 39 271-277.
[31] Schmidt, G. (2000), Scheduling with limited machine availability. European Journal of Operational Research 121 1-15.
[32] Sheen, G.J., and L.W. Liao (2007), Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints. Computer & Operations Research 34 2266-2278.
[33] Sheen, G.J., and L.W. Liao (2008), Parallel machine scheduling with machine availability and eligibility constraints. European Journal of Operational Research 184 458-467.
[34] Sheen, G.J., L.W. Liao, and C.F. Lin (2008), Optimal parallel machines scheduling with machine availability and eligibility constraints. The International Journal of Advanced Manufacturing Technology 36 132-139.
[35] Su, L.H., W.C. Pon (2009), Preemptive open-shop scheduling with machine availability and eligibility constraints. CYCU’s library.
[36] Su, L.H. (2009), Scheduling on identical parallel machines to minimize total completion time with deadline and machine eligibility constraints. The International Journal of Advanced Manufacturing Technology 40 572-581.
[37] Ullman, J.D. (1975), NP-complete scheduling problems. Journal of Computer and System Sciences 10 384-393.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2010-7-19

推文