具最小與最大時間延遲限制之零工式排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：57

、訪客IP：3.133.138.129

姓名

伍先楚(Hsien-chu Wu) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

具最小與最大時間延遲限制之零工式排程問題
(Job-Shop Scheduling with Minimum and Maximum Time Lags)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

本研究主旨為探討一零工式排程問題，其作業間具有最小與最大時間延遲之限制，目標為使總完工時間最小化。最小延遲時間為作業與作業間必須間隔的等待時間，而最大延遲時間為作業與作業間至多的等待時間。
本研究主要是延伸沈國基與廖祿文(2007)所提出的研究結果，將具最小與最大時間延遲之單一機台排程問題擴展到零工式排程題。我們先以分離圖(disjunctive graph)來表示本研究的問題。接著，我們結合 Carlier 跟 Pinson (1989)所提出的“head and tail”概念以及沈國基與廖祿文(2007)所提出的分枝定界法來尋找這個排程問題的最佳解。首先，我們先研究並修改有關Carlier跟 Pinson (1989)所提出的“head and tail”概念。然後，我們將“head and tail”概念用於沈國基與廖祿文(2007)所提出的分枝定界法，將其修正來適用於決定零工式系統下的作業排程問題。
實驗的分析顯示，在分枝過程中的淘汰法則是有效率的並且在分枝定界法中只有非常小比例的節點被產生。本研究的分枝定界法能順利的求得此排程問題的最佳解，但是當作業與作業間的延遲時間間隔太逼近，會容易造成作業的開始時間範圍消失，並且得到不可行解。此分枝定界法能用於求解 10 台機器和 20 個工作的排程問題，並得到最佳解。

摘要(英)

In this thesis,we study the problem of job-shop scheduling with minimum and maximum time lags when minimizing the makespan.This problem comes from industrial applications. Maximal time lags may be used to model situations when the delay between operations must not be too long in order to avoid deterioration of the products. Minimal time lags arise when waiting times between operations are imposed. Namely,each operation in job-shop system must be waiting for the lower bound of waiting time but do not exceed the upper bound of waiting time to perform the next operation. Besides, minimum and maximum time lags constraints on the starting time of each operation are also consider.
We will extend the research from Sheen and Liao (2007) to solve this scheduling problem. We incorporate the concept of“head and tail”proposed by Carlier and Pinson (1989) and the branch and bound algorithm proposed by Sheen and Liao (2007) to solved the job-shop scheduling with minimum and maximum time lags problem. First,we modified the propositions of“head and tail”from Carlier and Pinson (1989).Second,we utilized these propositions improve the branching process which proposed by Sheen and Liao (2007) to find the input and output of a given clique and let the branch and bound algorithm to solve the sequence of operation on each machine in job-shop system for obtaining the optimal solution.
Computational analysis shows that the propositions and rules for eliminating nodes during branching process is effective and very low percentage of nodes is generated by the branch and bound algorithm. The branch and bound algorithm could solve instances optimally. But,if the width of waiting time range be narrower between any pair of operations,it will easy to cause starting time interval of operation to become empty and make the infeasible result. The branch and bound algorithm can get the optimal solution for the problem with up to 10 machines and 20 jobs.

關鍵字(中)

★ 排程
★ 零工式排程
★ 最小與最大時間延遲限制
★ 分離圖

關鍵字(英)

★ Scheduling
★ Job-Shop
★ Minimum and Maximum Time Lags constrain
★ Disjunctive graph

論文目次

摘要 i
Abstract ii
Table of Content iii
List of Figure v
List of Tables vi
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 3
1.3 Research objectives 6
1.4 Research methodology and framework 6
1.4.1 Research methodology 6
1.4.2 Research framework 7
Chapter 2 Literature review 9
2.1 Disjunctive Graph 9
2.2 Job-Shop Scheduling 11
2.3 Minimum and Maximum Time Lags 13
Chapter 3 Algorithm for Job-Shop scheduling with minimum and maximum time lags 16
3.1 Notations 16
3.2 Modify the branch and bound algorithm proposed by Sheen and Liao (2007) 17
3.2.1 Disjunctive graph (Before determine the sequence of operation) 18
3.2.2 Schedule 20
3.2.3 Time lags 20
3.2.4 Starting time interval 22
3.2.5 Propositions 24
3.2.5.1 Increase of Release Dates and Tails 26
3.2.5.2 Input of clique (E) and Output of clique (H) determination 28
3.2.6 Branching scheme 29
3.2.7 Bounding scheme 32
3.2.8 Branch and bound algorithm 33
3.2.9 Feasible schedule 37
Chapter 4 Computational Analysis 38
4.1 Test Problem Generation 38
4.2 Validation of the Branch and Bound Algorithm 39
4.3 Evaluation of the Branch and Bound Algorithm 41
Chapter 5 Conclusion 56
5.1 Research Conclusion and Contribution 56
5.2 Research Limitation 57
5.3 Further Research 57
References 58
Appendix A. The propositions from Sheen and Liao (2007) 61
Appendix B. Adjustment of starting time intervals, release times and tail times [Adopted from Sheen and Liao (2007) 64
Appendix C. The detail process of modified the branch and bound algorithm from Sheen and Liao (2007) 66
Appendix D. Algorithm for a one machine scheduling problem in job-shop system with a given operation sequence [adopted from Sheen and Liao(2007)] 72
Appendix E. The detail parameters result calculated by our branch and bound algorithm for instance la01 74

參考文獻

[1] Adams, J., E. Balas., and D. Zawack. (1988), The shifting bottleneck procedure for job-shop scheduling. Management Science Vol. 34, No. 3, pp. 391- 401.
[2] Balas, E.(1969), Machine Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm, Operations Research, Vol. 17, No. 6. (Nov. - Dec.), pp. 941-957.
[3] Baker KR.(1974), Introduction to Sequencing and Scheduling. Wiley: New York.
[4] Brucker, P., B. Jurisch., and A. Kramer (1994), The job-shop problem and immediate selection. Annals of Operations Research, Vol. 50, pp. 73-114.
[5] Brucker, P., B. Jurisch., and B. Sievers. (1994), A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, Vol.49, pp.
107-127
[6] Brucker, P., T. Hilbig., and J. Hurink. (1999), A branch and bound algorithm for a single-machine scheduling problem with positive and negative time lags. Discrete
applied mathematics; Vol. 94, iss. 1-3, pp. 77.
[7] Brucker, P., S. Knust., T.C.E. Cheng., and N.V. Shakhlevich. (2004), Complexity results for flow-shop and open-shop scheduling problems with transportation delays. Annals of Operations Research; Vol.129, iss.1, pp. 81
[8] Carlier J.(1982), The one-machine sequencing problem. European Journal of Operational Research Vol. 11, pp. 42-47.
[9] Carlier, J., and E. Pinson. (1989), An algorithm for solving the job shop problem. Management Science Vol. 35, pp.164–176.
[10] Carlier, J., and E. Pinson. (1990), A practical use of Jackson’s preemptive schedule for solving the job-shop problem. Annals of Operations Research Vol. 26, pp. 269–287.
[11] Carlier, J., and E. Pinson. (1994), Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research Vol.78, pp. 146 –161.
[12] Chu C, Proth J-M.(1996), Single machine scheduling with chain structured precedence constraints and separation time windows. IEEE Transactions on Robotics and Automation Vol. 12, No. 6, pp. 835 – 43.
[13] Deo, N.(1974), Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, NJ.
[14] Dauzere-Peres S., and J.B. Lasserre. (1993), A modified shifting bottleneck procedure for job-shop scheduling. International Journal of Production Research
Vol. 31, No. 4, pp. 923-932.
[15] Dell'Amico M. (1996), Shop problems with twomachines and time lags. Operations Research Vol.44, No. 5, pp. 77–87.
[16] Fondrevelle, J., A Oulamara and M.C. Portmann (2006), Permutation flowshop scheduling problems with maximal and minimal time lags. Computers & operations research Vol. 33, iss. 6, pp. 1540
[17] Garey, M.R., and D.S. Johnson. (1979), Computers and Intertractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA.
[18] Hurink, J., and J. Keuchel. (2001), Local search algorithm for a single-machine scheduling problem with positive and negative time-lags. Discrete Applied
Mathematics Vol. 112, pp. 179-197.
[19] Jain, A.S., and S. Meeran. (1999), Deterministic job-shop scheduling: Past, present and future. European journal of operational research Vol.113, iss. 2, pp.
390
[20] Muth, J.F., and G.L.Thompson. (eds.) (1963),industrial Scheduling, Prentice-Hall, Englewood Cliffs, NJ.
[21] Roy, B., and B. Sussman. (1964), Les problemes
d'ordonnancement avec constraintes disjonctives, SEMA, Note D.S., No. 9, Paris.
[22] Rinnooy Kan, A.H.G. (1976), Machine scheduling problems: Classification, complexity and computations. In: Stenfert Kroese, H.E., Leiden, B.V. (Eds.),
Martinus Nijhoff, The Hague, The Netherlands.
[23] Sheen, G..J., and L.W. Liao. (2007), A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags. European Journal of Operational Research Vol. 181, pp. 102 -116.
[24] White, K.P., and R.V. Rogers. (1990), Job-shop scheduling: Limits of the binary disjunctive formulation. International Journal of Production Research Vol. 28,
No.12, pp. 2187 - 2200.
[25] Wikum, E.D., D.C. Llewllyn., and G..L. Nemhauser. (1994), One-machine generalized precedence constrained scheduling problems. Operations Research Letters Vol. 16, pp. 87-99.
[26] Yang, D.L., and M.S. Chern. (1995),A two-machine flow-shop sequencing problem with limited waiting time constraint. Computers & Industrial Engineering Vol. 28, pp. 63-70.

指導教授

沈國基(Gwo-gi Sheen)

審核日期

2008-10-9

推文