跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.91) 您好!臺灣時間:2025/02/11 19:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王智毅
研究生(外文):Chih-Yi Wang
論文名稱:可允許中斷之開放工廠總完工時間最小化問題之研究
論文名稱(外文):Scheduling Preemptive Open-shop to Minimize Total Completion Time
指導教授:廖經芳廖經芳引用關係
指導教授(外文):Ching-Fang Liaw
學位類別:碩士
校院名稱:朝陽科技大學
系所名稱:工業工程與管理系碩士班
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:60
中文關鍵詞:生產排程開放工廠可允許中斷總完工時間
外文關鍵詞:Total Completion TimeSchedulingOpen shopPreemptive
相關次數:
  • 被引用被引用:0
  • 點閱點閱:298
  • 評分評分:
  • 下載下載:58
  • 收藏至我的研究室書目清單書目收藏:0
在生產過程中在製品是製造上的一大成本,故欲減少生產成本就應該使在製品的數量最小化,而總完工時間就是工廠生產排程中一項評估在製品數量非常重要的準則。
近年來,開放工廠排程問題(Open Shop Scheduling Problem)已漸漸地被重視,但相較於其他的工廠排程問題,開放工廠排程問題在求解技術上仍有很大的改進空間。本論文將針對可允許中斷之開放工廠排程問題,發展一有效的近似解法。
可允許中斷之開放工廠之排程問題可簡單地描述如下,有n項獨立工件及m部不同的機器,每項工件經過機器的順序是不固定的,而且工件的處理是可以被中斷的,同一時間內,每部機器最多只能針對一項工件進行處理且每項工件僅能在一部機器上加工。
而在已知工件完工順序的前提下,求解總完工時間(Total Completion T ime) 最小化的問題可以表示為線性規劃 (Linear Programming)的模式。當機器數目m=2時此線性規劃的模式可以簡化為一O(n)之計算式,加速其求解的速度;但是當機器數目m > 2時,就必須重複地運用線性規劃的模式計算其總完工時間,並無其他簡化的方法求解。因此本研究針對可允許中斷之開放工廠,以總完工時間最小化為研究目標,發展一啟發式演算法(Heuristic),期望能迅速且有效率地解決大規模之問題,最後透過大量隨機的測試例題,進行求解績效的評估。
本研究所發展的演算法,可以有效地求解m部機器之問題,然而對於演算法(二)在求解題目的過程雖然較費時,但是其平均整體求解績效優於演算法(一)。




關鍵字:生產排程,開放工廠,可允許中斷,總完工時間
Production scheduling is very important in practice . A good scheduling can order the jobs efficiently , improve the machine utilization and reduce the production cost . Currently , the research of production scheduling is getting more and more emphasized . In this research the scheduling problem of minimizing total completion time in a preemptive open shop is examined .
The open shop preemptive scheduling problem can be formulated as follows . There are n jobs that have to be processed on m machines . Each job consists of m operations each of which is to be processed on a different machine. The order in which the operations are processed is immaterial . Each job is processed by one machine at a time and each machine processes one job at a time . A schedule is preemptive if the execution of any operation may arbitrarily often be interrupted and resumed at a later time .
Given a job completion sequence , the problem can be expressed as a linear program . When the number of machine is two , the linear program can be replaced by an algorithm with complexity O(n) which produces no more than n-1 preemptions . When the number of machine is greater than two , we develop an efficient heuristic for solving the total completion time preemptive open shop scheduling problem. Finally , computational experiments are conducted to evaluate the performance of the proposed algorithm . The Heuristics presented in this research can solve m-machine problem efficiently. Also, HeuristicⅡperforms better than HeuristicⅠ.
Keyword:Scheduling , Open shop , Preemptive , Total Completion Time
摘要 I
Abstact III
誌謝 IV
目錄 V
圖目錄 VIII
表目錄 IX
第一章 緒論 1
1-1 研究動機與背景 1
1-2 排程問題之分類 1
1-2-1單程處理排程問題 2
1-2-2 多程處排程問題 2
1-2-3 排程問題的評估準則 3
1-3排程問題的決解方法 4
1-4 問題描述 5
1-5研究範圍與限制 6
1-6研究目的 6
1-7 研究步驟與架構 7
第二章 文獻探討 9
2-1總完工時間之相關文獻: 9
2-1-1 單機排程 9
2-1-2 平行機器 10
2-1-3流程工廠(Flow shop): 10
2-1-4零工工廠(Job shop): 11
2-2 開放工廠之相關文獻: 11
2-2-1 工件不允許中斷之相關文獻 11
2-2-2工件允許可中斷情形之相關文獻 12
2-3文獻整理 14
第三章研究方法 18
3-1線性規劃求解 18
3-2求解兩部機器總完工時間最小化問題 20
3-3求解m部機器總完工時間最小化問題 21
3-3-1建立數學模式 21
3-4 啟發式演算法 23
3-4-1 啟發式演算法之設計(一) 23
3-4-2 啟發式演算法(一)之實例說明 26
3-4-3 啟發式演算法之設計(二) 33
3-4-4 啟發式演算法(二)之實例說明 35
3-5 下限值演算法(LB) 45
第四章 實例驗證 46
4-1 測試例題之產生 46
4-2 啟發式演算法之績效評估 47
第五章 結論與建議 52
5-1 結論 52
5-2 未來研究方向 53
參考文獻 54






















表目錄
表2.1 開放工廠之文獻 14
表3.1 decrementing set 架構示意表 23
表3.2 decrementing set 架構(a) 26
表3.2 decrementing set 架構(b) 27
表3.2 decrementing set 架構(c) 29
表3.2 decrementing set 架構(d) 30
表3.2 decrementing set 架構(e) 31
表3.3工件在機器上處理時間(a) 35
表3.3工件在機器上處理時間(b) 36
表3.3 工件在機器上處理時間(c) 40
表3.3 工件在機器上處理時間(d) 43
表4.1 下限值之績效評估 47
表4.2 演算法之績效評估(a) 48
表4.2 演算法之績效評估(b) 48
表4.3 演算法求解題目時間之評估(a) 49
表4.3 演算法求解題目時間之評估(b) 49
表4.4 演算法(二)求得總時程與最佳解差異比較(a) 50
表4.4 演算法(二)求得總時程與最佳解差異比較(b) 51































圖目錄
圖1.1 研究流程 8
圖3.1 機器處理工作的時間配置圖(a) 27
圖3.1 機器處理工作的時間配置圖(b) 28
圖3.1 機器處理工作的時間配置圖(c) 30
圖3.1 機器處理工作的時間配置圖(d) 31
圖3.1 機器處理工作的時間配置圖(e) 32
圖3.2 J4在機器上的處理順序 36
圖3.3 J1在機器上的處理順序 37
圖 3.4 J2在機器上的處理順序 38
圖 3.5 J3在機器上的處理順序 40
圖 3.6 J1在機器上的處理順序 42
圖 3.7 J2在機器上的處理順序 43
圖 3.8 工作在機械上的處理順序 44
1.  Elmaghraby, S.E., and Park, S.H., “Scheduling jobs on a number of identical machines”, AIIE Transactions, Vol.6, pp.1-13 (1974).
2. Deman, V., John, M., and Baker, K.R., “Minimizing mean flow time in the flow shop with no intermediate queues”, AIIE Transactions, Vol.6, No.1, pp.28-34 (1974).
3. Emmons, H., “One machine sequencing to minimize mean flow time with minimum number tardy”, Naval Research Logistics Quarterly , Vol.22, No.3, pp.585-592 (1975).
4. Zaloom, V., and Vatz, D., “Note on optimal scheduling of two parallel processors”, Naval Research Logistics Quarterly, Vol.22, No.4, pp.823-827 (1975).
5. Garey, M.R., Johnson, D.S., and Sethi, R., “Complexity of flow shop and job shop scheduling”, Mathematics of Operations Research, Vol.1, No.2,pp.117-129 (1976).
6. Gonzalez, T., and Sahni, S., “Open shop scheduling to minimize finish time”, JACM, Vol.23, No.4, pp.665-679 (1976).
7. Barnes, J.W., and Brennan, J.J., “An improved algorithm for scheduling jobs on identical machines”, AIIE Transactions, Vol.9, pp.25-31 (1977).
8. Sethi, R., “On the complexity of mean flow time scheduling”, Mathematics of Operations Research, Vol.2, No.4, pp.320-330 (1977).
9.Gonzalez,T., “A note on open shop preemptive schedules”, IEEE Transactions on Computer, Vol.28, pp.782-786 (1979).
10.Graham, T., Lawer, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G., “ Optimization and approximation in deterministic sequence and scheduling a survey”, Annals of Discrete Mathematics, Vol.5, pp.287-326(1979).
11.Cho,Y.,and S.,Sahni, “Preemptive scheduling of independent jobs with release and due time on open, flow,and job shop”, Operations Research, Vol.29, pp.511-522 (1981).
12.Lawler,E.L., J.K., Lenstra, and A.H.G., Rinnooy Kan “ Minimizing maximum lateness in a two-machine open shop”, Mathematics of Operation Research, Vol.6, pp.138-153 (1981).
13.Achugbue, J.O., and Chin F.Y., “Scheduling the open shop to minimize mean flow time”, SIAM J. COMPUT., Vol.11, pp.709-720 (1982).
14.Szwarc, W., “Flow shop problem with mean completion time criterion”, IIE Transactions (Institute of Industrial Engineering), Vol.15, No.2, pp.172-176 (1983).

15. Liaw, C., “Multi-machine scheduling problems”, Master thesis, Dept. of Industrial Management, National Cheng-Kung Univ., Taiwan (1987).
16.Brucker,P.,Jurisch,B.,and Jurisch,M., “Open shop problem with unit time operatons”, ZOR, Vol.37, pp.59-73 (1987).
17.Sarin, S.C., Ahn, S., and Bishop, A.B., “An improved branching scheme for the branch and bound procedure of scheduling n jobs on m parallel machines to minimize total weighted flow time”, International Journal of Production Research, Vol.26, pp.1183-1191 (1988).
18.Aksjonov.V.A. , “A polynomial-time algorithm of approximate solution of a scheduling problem”, Upravlyaemye Sistemy, Vol.28, pp.273-281 (1989).
19.Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B.,“Sequencing and Scheduling: Algorithms and Complexity”, ReportBS-R8909, Center for Mathematics and Computer Science, P.O. Box 4079, 1009 AB Amsterdam, The Netherlands (1989).
20.Ho, J.C., and Chang, Y.L., “New heuristic for n-job, m-machine flow shop problem”, European Journal of Operational Research, Vol.52,No.2, pp.194-202 (1991).


21.Rajendran, C., “Heuristic algorithm for scheduling in a flow shop to minimize total flow time”, International Journal of Production Economics, Vol.29, No.1, pp.65-73 (1993).
22.Liu,C.Y., “A branch and bound algorithm for the preemptive Open shop problem ”, Journal of the Chinese Institute of Industrial Engineers, Vol.12,No.1, pp.25-31 (1995).
23.Webster, S., “Weighted flow time for scheduling identical processors”, European Journal of Operational Research, Vol.80, No.1, pp.103-111(1995).
24.Croce, F.D., Narayan, V., and Tadei, R., “Two-machine total completion time flow shop problem”, European Journal of Operational Research, Vol.90, No.2, pp.227-237 (1996).
25.Sun, D., and Batta, R., “Scheduling large job shop: A decomposition approach”, International Journal of Production Research, Vol.34, No.7,pp.2019-2033 (1996).
26.Ramudhin,A.,and Maruer,P., “The generalized shifting bottleneck procedure”, Europen Journal of Operational Research, Vol.93, pp.34-48 (1996).
27.Werra, D.de, Hoffman,A.J., Mahadev,N.V.R., Peled,U.N., “Restrictions and preassignments in preemptive open shop scheduling”, DISCRETE APPLIED MATHEMATICS, Vol.68, No.2, pp.169-188 (1996).
28.Gladky,A.A., “A two-machine preemptive open shop scheduling problem:An elementary proof of NP-completeness”, European Journal of Operational Research, Vol.103, No.3, pp.113-116 (1997).
29.Holthans, O., and Rajendran, C., “Efficient dispatching rules for
scheduling in a job shop”, International Journal of Production Economics , Vol.48, No.1, pp.87-105 (1997)
30.Rajendran, C., and Ziegler, H., “Efficient heuristic for scheduling in a flow shop to minimize total weight flow time of jobs”, European Journal of Operational Research, Vol.103, No.1, pp.129-138 (1997).
31.Liaw, C., “An iterative improvement approach for the non-preemptive open shop scheduling problem”, European Journal of Operational Research, Vol.111, No.3, pp.509-517 (1998).
32.Liu,C,Y., and Bulfin,R.L., “Scheduling ordered open shop”, Computers & Operations Research, Vol.14,No.3, pp.257-264 (1998).
33.Koksalan, M., Azizoglu, M., Kondakci, and Koksalan, S., “Minimizing flow time and maximum earliness on a single machine”, IIE Transactions (Institute of Industrial Engineerings), Vol.30, No.2,pp.192-200 (1998).


34.Mckoy, D.H.C., and Egbelu, P.J., “Minimizing production flow time in a process and assembly job shop”, International Journal of Production Research, Vol.36, No.8, pp.2315-2332 (1998).
35.Sergey V. Sevastianov, Gerhard J.Woeginger , “Makespan minimization in open shops:A polynomial time approximation scheme”, Mathematical Programming, Vol.82, pp.191-198 (1998).
36.Woo, H.S., and Yeh, D.S., “Heuristic algorithm for mean flow time objective in flow shop scheduling”, Computers & Operations Research, Vol.25, No.3, pp.175-182 (1998).
37.Azizoglu, M., and Kirca, O., “On the minimization of total weighted flow time with identical and uniform parallel machines”, European Journal of Operational Research, Vol.113, pp.91-100 (1999).
38.Liaw, C., “A Tabu search algorithm for the open shop scheduling problem”, European Journal of Operational Research, Vol.26, No.2, pp.109-126 (1999).
39.George J. Kyparisis, Christos, Koulamas, “Open shop scheduling with makespan and total completion time criteria”, Comprters and operations research, Vol.27, No.2, pp.15-27 (2000).


40.Liaw, C.,Cheng,C.,Chen,M., “The total completion time open shop scheduling problem with a given sequence of jobs on one machine”, Comprters and operations research, Vol.22, pp.1251-1266 (2002).
41.Holger Hennes ,Heidemarie Brasel,, “On the open-shop problem with preemption and minimizing the average completion time”,European Journal Of Operational Research, Vol.157, pp.607-619 (2004).
42.Liaw,C., “Scheduling two-machine preemptive open shops to minimize total completion time”,Computer and Operation Research, Vol.31, pp.1349-1363 (2004).
43.Liaw, C., “Scheduling preemptive open shop to minimize total tardiness ” ,European Journal Of Operational Research, Vol.16, pp.173-183 (2005).
44.Cheng,T.C.E,Ng. C.T.,Yuan,J.J.,Liu,Z.H., “Single machine scheduling to minimize total weighted tardiness”,European Journal Of Operational Research, Vol.165, pp.423-443 (2005).
45.陳哲宇,「應用塔布搜尋法求解兩部機器可分割工作開放工廠總延遲時間最小化之排程問題」,碩士論文,朝陽科技大學工業工程與管理研究所,台中(2002).
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top