跳到主要內容

臺灣博碩士論文加值系統

(44.192.15.251) 您好!臺灣時間:2024/02/25 06:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:潘文容
研究生(外文):Wen-Jung Pan
論文名稱:同站多機之開放型工廠排程法則
論文名稱(外文):Open Shop Scheduling Rule for Multi-machine in Each Workstation
指導教授:李鴻濤李鴻濤引用關係林宏澤林宏澤引用關係
指導教授(外文):Hong-Tau LeeHung-Tso Lin
學位類別:碩士
校院名稱:國立勤益技術學院
系所名稱:工業工程與管理系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:83
中文關鍵詞:排程開放型工廠混整數規劃
外文關鍵詞:SchedulingOpen shopMixed integer programming
相關次數:
  • 被引用被引用:9
  • 點閱點閱:283
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本文探討同站多機之開放型工廠(open shop)排程問題,為同一工作站中含有多部不同功能之機器,可於同時段內執行二項以上分屬不同工作(job)之作業(task),此一特殊情形實務上出現於與民生相關之道路工程中。由於道路工程進行時除需使用各施工單位內部之專門設備與人員外,尚需佔用道路施工,施工期間必然造成交通阻塞、噪音、空氣污染等社會成本,因此妥善安排這些作業之施工起迄時間,既能使各施工單位之專門設備與人員可連續於不同道路上施工,以提高施工效率,又能使道路佔用施工時間總和最小,以縮短交通阻塞、噪音、空氣污染等社會成本。
此類道路工程排程問題之基本性質為各道路(視為工廠中之工作站)可同時進行水管、瓦斯管及電信管線等多項分屬不同施工單位之舖設作業,由於作業之進行並無特定先後順序,如有 個單位(瓦斯公司、自來水公司、電信公司···等)共提出 件施工案,每一施工案預定於 條路段(視為 個工作站)施行管線配置作業,對施工單位而言,其配管之路段順序並無限制,因此以開放型工廠視之;而同一路段上可同時進行水管、瓦斯管及電信管線等多項舖設作業,視為每個工作站可於同時段內由各不同功能之機器執行不同作業之施工,因此具有同時施工現象。在排程限制方面需確保各該單位之 項作業可連續於 條路段上展開,此為無中間等候(no intermediate queue,NIQ)之限制,以提高作業執行效率;排程目標為縮短 條路段之施工佔用期間,如此便能降低交通阻塞、噪音、空氣污染等社會成本。
本文所探討之排程問題可表達為 ,除具有開放型工廠之性質外,另具有同一工作站於同時段內可進行二件以上分屬不同工作之作業的實務現象。本文以整體方法(monolithic approach)建構混整數規劃(mixed integer programming)模式以尋求小型問題之最佳排程,提供啟發式(heuristic)排程演算效率和應用效益之比較基準。並研擬啟發式排程法則,以期在經濟演算時間內,擬定滿意之道路施工排程,提供工程規劃與管理之依據,有助於實務問題之解決。
In this paper we address a scheduling problem taken from the roads construction related to the lives of people. The production system is special type open shop with the characteristics of each work station as a functionally different machine proceeds different task of work in the same period. In the fields of schedule limitation have to ensure after finishing the execution of constructing unit in one road, we can immediately transfer to another mounted task with relative materials and staff in order to risen the efficiency and make sure there’s limitation of NIQ (no intermediate queue) so that the m tasks can be done in m methods sequentially for every unit. The objective is minimize the sum of occupying the construction of m roads.
In this research, we utilize the monolithic approach and mixed integer programming to solve the small size problem of the optimizing schedule and provide the efficient calculus of heuristic and the efficient application of the comparable standard. A heuristic is proposed to find the near-optimal schedule for the problem. The performance of the heuristic is evaluated by comparing its solution with optimal solution for small-sized problems. As the heuristic is satisfying road constructing schedule in the efficient calculated period so that it can solve the practical problems.
中文摘要 --------------------------------------------- i
英文摘要 -------------------------------------------- iii
誌謝 ------------------------------------------------ iv
目錄 ------------------------------------------------- v
表目錄 ---------------------------------------------- vii
圖目錄 ----------------------------------------------- ix
一、 緒論---------------------------------------------- 1
1.1 研究動機與目的-------------------------------------- 1
1.2 問題背景與特性--------------------------------------- 2
1.3 基本假設-------------------------------------------- 3
1.4 研究架構-------------------------------------------- 4
二、 文獻探討-------------------------------------------- 7
2.1 排程問題概述----------------------------------------- 7
2.2 開放型工廠------------------------------------------ 9
2.3 混整數規劃------------------------------------------ 10
三、 求解方法------------------------------------------- 12
3.1 混整數規劃模式--------------------------------------- 12
3.1.1 符號定義------------------------------------------ 12
3.1.2 數學模式------------------------------------------ 13
3.1.3 隨機題組之執行結果--------------------------------- 16
3.1.4 區集題組之執行結果--------------------------------- 22
3.2 分枝界限法------------------------------------------ 23
3.2.1 分枝步驟------------------------------------------ 23
3.2.2 界限步驟------------------------------------------ 24
3.2.3 洞悉步驟------------------------------------------ 30
3.1.4 舉例說明------------------------------------------ 30
四、 啟發式演算法---------------------------------------- 32
4.1.1 啟發式演算法(一)之設計------------------------------ 32
4.1.2 啟發式演算法(一)之舉例說明-------------------------- 32
4.1.3 隨機題組之啟發式演算法(一)效率評估------------------ 36
4.1.4 區集題組之啟發式演算法(一)效率評估------------------ 42
4.2 啟發式演算法(二)------------------------------------- 46
4.2.1 啟發式演算法(二)之設計------------------------------ 46
4.2.2 啟發式演算法(二)之舉例說明--------------------------- 46
4.2.3 隨機題組之啟發式演算法(二)效率評估------------------ 49
4.2.4 區集題組之啟發式演算法(二)效率評估------------------ 54
4.3 建議之啟發式演算法------------------------------------ 58
4.3.1 建議之啟發式演算法設計------------------------------- 59
4.3.2 建議之啟發式演算法舉例說明--------------------------- 59
4.3.3 隨機題組之建議啟發式演算法效率評估------------------ 59
4.3.4 區集題組之建議啟發式演算法效率評估------------------ 65
五、 結論與建議----------------------------------------- 70
5.1 結論----------------------------------------------- 70
5.2 建議----------------------------------------------- 71
參考文獻 ----------------------------------------------- 72
1.廖慶榮,1994,作業研究,初版,三民書局,台北市。
2.Adiri, I., Aizikowitz, N., 1989, “Open-shop scheduling problems with dominated machines”, Naval Research Logistics, Vol. 36, pp. 273-281.
3.Adiri, I., Amit, N., 1984, “Openshop and flowshop scheduling to minimize sum of completion times”, Computers and Operations Research, Vol. 11, pp. 275-284.
4.Dell, Amico, M., Trubian, M., 1993, “Applying tabu search to the job shop scheduling problem”, Annals of Operations Research, Vol. 41, pp. 231-252.
5.Gonzalez, T., Sahni, S., 1976, “Openshop scheduling to minimize finish time”, JACM, Vol. 23, pp. 665-679.
6.Graham R.L., et al, 1979, “Optimization and approximation in deterministic sequencing and scheduling : a survey”, Annals of Discrete Mathematics, Vol. 5, pp. 287-326.
7.Greene, J.T., Sadowski, P.R., 1986, “A mixed integer program for loading and scheduling multiple flexible manufacturing cells”, European Journal of Operational Research, Vol. 24, pp. 379-386.
8.Horng, H.C., Chou, S.H., 2002, “Comparing dispatching rules in an open shop- a simulation study”, IIE Annual Conference .
9.Schaller, J., 2001, “A new lower bound for the flow shop group scheduling problem”, Computer & Industrial Engineering, Vol. 41, pp. 151-161.
10.Konno, T., Ishii, H., 2000, “An open shop scheduling problem with fuzzy allowable time and fuzzy resource constraint”, Fuzzy Sets and Systems, Vol.109, pp. 141-147.
11.Kyparisis, G.J., Koulamas, C., 2000, “Open shop scheduling with makespan and total completion time criteria”, Computers and Operations Research, Vol. 27, pp. 15-27.
12.Lawler, E.L., et al, 1989, “ Sequencing and scheduling: algorithms and complexity”, Report BS-R8909, Centre for Mathematics and Computer Science, P.O. Box 4079,1009 AB Amsterdam, The Netherlands.
13.Liaw, C,F., 1999, “A tabu search algorithm for the open shop scheduling problem”, Computers and Operations Research, Vol. 26, pp. 109-126.
14.Liaw, C.F., 2000, “A hybrid genetic algorithm for the open shop scheduling problem”, European Journal of Operational Research, Vol. 124, pp. 28-42.
15.Lin, H.F., Liu, C.Y. and Liu, P.Y., 1995, “A heuristic approach to the total tardiness in non-preemptive open-shop scheduling”, International Journal of Industrial Engineering, Vol. 2, pp. 25-33.
16.Liu, C.Y., and Bulfin, R.L., 1988, “Scheduling open shops with unit execution times to minimize functions of due dates” Operations Research Journal, Vol. 14, pp. 257-264.
17.MacCarthy, B.L., and Jiyin Liu, 1993, “Addressing the gap in scheduling research : a review of optimization and heuristic methods in production scheduling”, International Journal of Production Research, Vol. 1, pp.59-79.
18.Nowicki, E., and Smutnicki, C., 1996, “A fast taboo search algorithm for the job shop problem”, Management Science, Vol. 42, pp. 797-813.
19.Parunak, H.V.D., 1991, “Characterizing the Manufacturing Scheduling Problem”, Journal of Manufacturing Systems, Vol. 3, pp. 241-259.
20.Pinedo, M., 1995, “Scheduling: theory, algorithms, and systems”, Prentice-Hall, Englewood Cliffs, NJ.
21.Roy, B., and Sussmann, B. 1964, Les problems d’ordonnancement avec constraints disjunctives. SEMA Note D.S. 9, Paris.
22.Sawik, T., 2000, “Simultaneous vs. sequential loading and scheduling of flexible assembly systems”, International Journal of Production Research, Vol. 38, pp. 3267-3282.
23.Schaller, J., 2001, “A new lower bound for the flow shop group scheduling problem”, Computer & Industrial Engineering, Vol. 41, pp. 151-161.
24.Srikar, B., and Ghosh, S., 1986, “A MILP model for the n-job, m-stage flowshop with sequence dependent set-up times”, International Journal of Production Research, Vol. 24, pp. 1459-1474.
25.Stafford, E.F., and Tseng, F.T., 1990, ”On the Srikar-Ghosh MILP model for the N×M SDST flowshop problem ”, International Journal of Production Research, Vol. 28, pp. 1817-1830.
26.Sule, D.R., 1996, ”Industrial Scheduling”, PWS, Boston,
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 張坤鄉(1991)。國中教師休閒活動狀況之調查研究。教育資料文摘,28(4),150-163。
2. 張孝銘、高俊雄(2001)。休閒需求與休閒阻礙間之相關研究--以彰化市居民為實證,體育學報,30,143-152。
3. 張玉鈴、余嬪(1999)。大學生休閒內在動機、休閒阻礙、休閒無聊感與自我統合之關係研究,彰化師大輔導學報,20,83-111。
4. 高俊雄(1996)。休閒概念面面觀,國立體育學院論叢,6(1),69-78。
5. 李素馨(1997)。都市女性休閒類型和休閒阻礙。戶外遊憩研究,10(1),43-68。
6. 宋明順(1992)。休閒與工作-大眾休閒時代的衝擊。社會教育學刊,21,1-19。
7. 呂建政(1999)。休閒教育的課程內涵與實施。公民訓育學報,8,181-195。
8. 謝靜敏、藍慧禎、楊心婷、林素鈴(1995)。加強休閒教育的途徑。諮商與輔導,116,6-8。
9. 薛銘卿(1992)。休閒及休閒活動定義之詮釋:非規範及規範性觀點。戶外遊憩研究,5(3/4),71-89。
10. 葉智魁(1995)。工作與休閒--提昇生活素質的反省。戶外遊憩研究,8(2),31-46。
11. 許建民、高俊雄(2000)。以三類型阻礙模式探討都市六年級學童運動休閒阻礙參與阻礙與性別及自尊之關係。戶外遊憩研究,13(1),41-61。
12. 吳忠宏、范莉雯(2003)。以九年一貫課程為架構之休閒教育模式與內容,戶外遊憩研究,16(1),1-23。
13. 余嬪(1996)。提高全民休閒修養:由加強休閒教育開始。教育研究雙月刊,55,6-9。