臺灣人文及社會科學引文索引資料庫系統

:::

詳目顯示

回上一頁
第 1 筆 / 總合 1 筆   第一頁 上一頁 下一頁 最後一頁
/1頁
題名：具機器可用時間與機器合適度限制下之平行機台最佳化排程問題
作者：廖祿文 引用關係
作者(外文)：Lu-Wen Liao
校院名稱：國立中央大學
系所名稱：工業管理研究所
指導教授：沈國基
學位類別：博士
出版日期：2006
主題關鍵詞：機器合適度限制；排程；平行機台；網路流量；分支定界演算法；機器可用時間限制；Scheduling；Parallel machines；Network flows；Branch and bound algorithm；Machine availability constraint；Machine eligibility constraint
原始連結：連回原系統網址new window
相關次數：
  • 被引用次數被引用次數:期刊(0) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:0
  • 共同引用共同引用:0
  • 點閱點閱:0
本論文主要在探討有限規劃時間幅度下，具機器可用時間與機器合適度限制下之平行機台最佳化排程問題。機器可用時間限制(Machine availability constraint)，意指每一機台具有服務時間之限制；而機器合適度限制(Machine eligibility constraint)，意指每一工件被限定在特定機台服務之限制。目前尚無研究同時考慮上述二限制，然而實務上如電視台廣告、半導體製程等等之排程問題，皆須同時納入此二限制。本研究首先將理論研究，延伸至含此二限制之問題，分別探討:一、極小化最大完工時間(Makespan, Cmax)之排程問題； 二、極小化最大延遲時間(Maximum lateness, Lmax)之排程問題。本論文最後將上述研究成果，推廣應用至工件的操作時間具不可分割特性下(Job preemption is not allowed)之平行機台排程問題，此為本論文第三個所探討的排程問題。
針對極小化最大完工時間之排程問題，我們利用網路流量分析方法(Network flow approach)，將排程問題轉換成多個最大流量網路問題(Maximum network flow problem)，並建構相對應之網路流量模型。每一個網路流量模型，描述了工件與機台可操作時間，在給定不同的「最大完工時間」下之相互關係。本研究利用二元搜尋方法與最大流量網路問題演算法，建構一多項式演算法(Polynomial time algorithm)。此一多項式演算法依序求解問題中之最大流量網路問題，以得到最小之「最大完工時間」。針對極小化最大延遲時間之排程問題，本研究利用臨界值(Critical values)之概念，與運用相類似上述極小化最大完工時間之排程問題之網路流量分析方法，提出兩階段之二元搜尋演算法來求解此一排程問題。本論文最後，將以極小化最大延遲時間之排程問題的結果，進一步應用到第三類排程問題上，以求解問題之下界值(Lower bound)。並依據工件與機台間之相互特性，整理出相關命題(Propositions)，發展分支定界法(Branch and bound algorithm)，以求取問題之最佳解。
In this dissertation we consider the parallel machine scheduling problem with machine availability and eligibility constraints under a given planning horizon. Machine availability constraint indicates that each machine is not continuously available at all times throughout the planning horizon; machine eligibility constraint means that each job can only be processed on specified machines. We observe that there is a little published works in machine scheduling considered machine availability and eligibility constraints simultaneously. But this type of scheduling problem can be found in some practical environments, such as TV advertising scheduling and the testing of fabricated wafers in semiconductor manufacturing. In this dissertation, therefore, we extend the existing works to consider the following three types of scheduling problems with machine availability and eligibility constraint simultaneously. We first consider the first type of the scheduling problem where the objective is to minimizing the maximum makespan (Cmax). Then, we consider the second type of scheduling problem where the objective is to minimizing the minimum lateness (Lmax). Finally, we extend the result of the second type of scheduling problem to deal with the more general scheduling problem where the job preemption is not allowed.
For the minimization of Cmax, we utilize a network flow approach to formulate the scheduling problem into a series of maximum flow problem, and propose a polynomial time algorithm to solve the scheduling problem optimally. For the minimization of Lmax, we first introduce the concept of the critical values, and then apply the network flow approach for developing a two-phase binary search algorithm to solve the problem optimally. Finally, we extend the result of the second type of scheduling problem to derive a lower bound of the scheduling problem in which job preemption is not allowed; and then we investigate the characteristics of jobs and machines to find related propositions for developing a branch and bound algorithm to solve the scheduling problem optimally.
1.Ahuja, R.K., T.L. Magnanti and J.B.Orlin (1993), Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, New Jersey).
2.Ahuja, R.K., and J.B. Orlin (1989), A fast and simple algorithm for the maximum flow problem, Operations Research 37 (5), 748-759.
3.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.
4.Blazewicz, J., K. Ecker, E. Pesch, G. Schmidt, and J. Weglarz (2001), Scheduling Computer and Manufacturing Processes (Springer, Berlin).
5.Blazewicz, J., K. Ecker, G. Schmidt, and J. Weglarz (1993), Scheduling in Computer and Manufacturing Systems (Springer, Berlin).
6.Centeno, G., and R.L Armacost (1997), Parallel machine scheduling with release time and machine eligibility restrictions, Computers & Industrial Engineering 33(1-2), 273-276.
7.Centeno, G., and 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.
8.Dantzig, G. B., and D. R. Fulkerson (1956), On the max-flow min-cut theorem of networks, in: H. W. Kuhn, A. W. Tucker (eds.), Liner Inequalities and Related Systems, Annals of Mathematics Study 38 (Princeton University Press, Princeton, New York) 215-221.
9.Ford, L.R., and D.R. Fulkerson (1956), Maximal flow through a network, Canadian Journal of Mathematics 8, 399-404.
10.Fulkerson, D.R., and G.B. Dantzig (1955), Computations of maximum flow in networks, Naval Research Logistics Quarterly Quart 2, 277-283.
11.Gharbi, A., and M. Haouari (2005), Optimal parallel machines scheduling with availability constraints, Discrete Applied Mathematics 148, 63-87
12.Graham, R.L., E.L. Lawer, J.K. Lenstra, and A.H.G. Rinnooy Ken (1979), Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics 5, 287-326.
13.Horn, W.A. (1974), Some simple scheduling algorithms, Naval Research Logistics Quarterly 21, 177-185.
14.Hwang, H.C., and S.Y. Chang (1998), Parallel machines scheduling with machine shutdowns, Computers & Mathematics with Applications 36(3), 21-31.
15.Hwang, H.C., S.Y. Chang, and K. Lee (2004), Parallel machine scheduling under a grade of service provision, Computer & Operations Research 31, 2055-2061.
16.Hwang, H.C., K. Lee, and S.Y. Chang (2005), The effect of machine availability on the worst-case performance of LPT, Discrete Applied Mathematics 148, 49-61.
17.Kellerer, H. (1998), Algorithm for multiprocessor scheduling with machine release time, IIE Transactions 30, 991-999.
18.Lawer, E.L. (1976), Combinational Optimization: Networks and Matroids (Holt, Rinehart & Winston, New York).
19.Labetoulle, J., E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnoy Kan (1984), Preemptive scheduling of uniform machines subject to release dates, in: W.R. Pulleyblank (eds.), Progress in Combinatorial Optimization (Academic Press, New York) 245-261.
20.Lee, C.Y. (1991), Parallel machines scheduling with nonsimultaneous machine available time, Discrete Applied Mathematics 30, 53-61.
21.Lee, C.Y. (1996), Machine scheduling with an availability constraint, Journal of Global Optimization 9, 395-416.
22.Lee, C.Y., L. Lei, and M. Pinedo (1997), Current trends in deterministic scheduling, Annals of Operations Research 70, 1-41.
23.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.
24.Liao, C.J., D.L. Shyur, and C.H. Lin (2005), Makespan minimization for two parallel machines with an availability constraint, European Journal of Operational Research 160, 445-456.
25.Lin, G..H., E.Y. Yao, and Y. He (1998), Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times, Operations Research Letters 22, 75-81.
26.Liu, Z., and E. Sanlaville (1995), Profile scheduling of list algorithm, in: P. Chretienne et al. (eds.), Scheduling Theory and its Applications (Wiley, New York) 91-110.
27.Lin, Y., and W. Li (2004), Parallel machine scheduling of machine-dependent jobs with unit-length, European Journal of Operational Research 156, 261-266.
28.Pinedo, M. (2002), Scheduling: Theory, Algorithm and System (New Jersey, Prentice Hall).
29.Sanlaville, E. (1995), Nearly on line scheduling of preemptive independent tasks, Discrete Applied Mathematics 57, 229-241.
30.Sanlaville, E., and G. Schmidt (1998), Machine scheduling with availability constraints, Acta Informatica 35, 795-811.
31.Schmidt, G. (1984), Scheduling on semi-identical processors, Zeitschrift für Operations Research A28, 153-162.
32.Schmidt, G. (1988), Scheduling independent tasks with deadlines on semi-identical processors, Journal of the Operational Research Society 39, 271-277.
33.Schmidt, G. (2000), Scheduling with limited machine availability, European Journal of Operational Research 121, 1-15.
34.Takao, A., and A. Yasuhito (2000), Recent developments in maximum flow algorithms, Journal of the Operations Research Society of Japan 43(1), 2-31.
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top
QR Code
QRCODE

臺灣人文及社會科學引文索引資料庫

目前上線人數：589（臺灣：583，外國：6） ／ 本年度總使用人次：2658005 ／ 訪客人次（自102年09月）：68452263
國家圖書館著作權聲明 Copyright © 2013 All rights reserved.
本館地址: 100201臺北市中山南路20號． 本館地圖及交通資訊．
總機：(02)23619132．最佳瀏覽解析度為1024x768以上