具等候時間窗口限制之零工式生產排程工作順序之決定

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：11

、訪客IP：3.144.212.145

姓名

何惠雯(Huan-Wen He ) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

具等候時間窗口限制之零工式生產排程工作順序之決定

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本研究是探討在未給定操作順序下，branch and bound具等候時間窗口限制之零工式（job-shop）生產排程問題，發展一最佳演算法以決定作業之操作順序和極小化完成時間（Cmax）為目標。存在於任兩個作業間之等候時間窗口為一相依時間，此時間窗口影響當前一個作業操作完成後，在一定的時間窗口內必須進行下一個操作作業；目前學術上，大多出現於雙機流水線（two-machine flowshop）排程問題，但其結果並無法應用於現實環境中具等候時間窗口限制的零工式半導體製程，只有許淑芬（1998）做過此類問題，但其論文的主要架構是在給定一個操作順序下，判斷其可行性和極小化完成時間。本研究將此問題擴展至在未給定操作順序下，如何決定出以極小化完成時間為目標之作業操作順序的演算法。
本研究首先探討單一機器排程問題，了解相依時間窗口限制之特性，並發展一演算法決定單機排程問題，爾後再將其結果擴展應用到多台機器問題上。在其求解單一機器排程問題之過程中，首先以分離圖建立模式，以分枝的方式展開可能的作業操作順序，計算各作業節點之可開始操作時間（release time）區間，將相依時間轉換成絕對時間，導入時間窗口一致性的概念，淘汰掉一些不可行的操作順序分枝，並以定界的方式儘早排除掉一些操作順序分枝；將單一機器問題之結果擴展應用到多台機器生產環境時，除了原有的相依時間窗口限制的特性外，還多了多台機器間相互的影響，如搶作業的情形發生，另外有個差異點，則是在多台機器生產環境中，為符合後續作業之等候時間窗口的限制，各工作未必接於時間點零開始操作，可經由延後某些作業的操作而使其為可行的操作順序，而在延後的過程中，本研究中每一個線段上之等候時間為整數（integer number），並把分離圖轉換成多機網圖，多機示意圖再轉成網圖，以融入the k-th shortest path演算法去做作業操作時間的調整，以尋找出最佳的操作順序及其完成時間。

關鍵字(中)

★ 枝界法
★ 第k長的最短路徑
★ 等候時間窗口
★ 零工式生產環境

關鍵字(英)

★ branch and bound
★ job-shop
★ the k-th shortest path
★ time windows

論文目次

目錄
目錄..........................................................Ⅰ
圖目錄........................................................Ⅲ
表目錄........................................................Ⅳ
第一章緒論...................................................1
1.1 研究背景與動機............................................1
1.2 問題敘述..................................................2
1.3 研究目的..................................................3
1.4 研究方法與研究流程........................................3
1.4.1 研究方法..............................................3
1.4.2 研究流程..............................................4
第二章文獻回顧...............................................6
2.1 具時間窗口限制特性的排程問題文獻..........................6
2.1.1 操作時間具時間窗口限制之相關文獻......................6
2.1.2 等候時間具時間窗口限制之相關文獻......................9
2.2 求解零工式生產環境問題之排程文獻.........................10
2.3 第K長最短路徑的文獻......................................13
2.4 結論.....................................................14
第三章具等候時間窗口限制之零工式生產排程演算法...............17
3.1 問題特性.................................................19
3.1.1 單一機器.............................................19
3.1.2 多台機器.............................................20
3.2 符號定義.................................................22
3.3 名詞解釋與利用的特性.....................................23
3.3.1 名詞解釋.............................................23
3.3.2 利用的特性...........................................24
3.4 單一機器問題.............................................24
3.4.1 分枝定界法則.........................................24
3.4.2 單一機器特性相關的命題...............................27
3.4.3 單一機器演算法.......................................29
3.5 多台機器問題.............................................31
3.5.1 分枝定界法則及時間調整法則...........................31
3.5.2 多台機器特性相關的命題...............................34
3.5.3 多台機器演算法.......................................42
3.6 釋例.....................................................48
第四章結論與建議.............................................72
4.1 研究貢獻.................................................72
4.2 研究限制.................................................73
4.3 未來發展方向.............................................73
參考文獻......................................................75
附錄一 LINDO程式..............................................77
附錄二 Double-Sweep Algorithm.................................90

參考文獻

參考文獻
1.許淑芬, “具等候時間窗口限制之零工式生產排程問題,”國立中央大
學研究所碩士論文, 1998.
2.Adams, J., Balas, E., and Zawack, D., “The Shifting
Bottleneck Procedure for Job Shop Scheduling,” Management
Science, 34(3), 1989, pp 391-401.
3.Ahn, B. H., and Shin, J. Y., “Vehicle-routing with Time
Windows and Time-varying Congestion,” Journal of Operational
Research Society, 42, 1991, pp 393-400.
4.Armstrong, R., and Lei, L., and Gu, S., “A Bounding Scheme
for Deriving the Minimal Cycle Time of a Single-transporter N-
stage Process with Time-window Constraint,” European Journal
of Operational Research, 78, 1994 ,pp 130-140.
5.Carlier, J., and Pinson, E., “An Algorithm for Solving the
Job-shop Problem,” Management Science, 35, 1989, pp 164-176.
6.Carlier, J., and Pinson, E., “Adjustments of Heads and Tails
for the Job-shop Scheduling Problem,” In the European
Journal of Operational Research, 78, 1994, pp 146-161.
7.Desrosiers, J., Soumis, F., Desrochers, M., and Sauve., M.,
“Methods for Routing with Time Windows,” European Journal of
Operational Research, 23, 1986, pp 236-245.
8.Desrochers, J., Desrosiers, M., and Solomom, M., “A New
Optimization Algorithm for the Vehicle Routing Problem with
Time Windows ,” Operations Research, 40, 1992, pp 342-354.
9.Desrosiers, J., Dumas, Y., Gelinas, E., and Solomom, M., “An
Optimal Algorithm for the Traveling Salesman Problem with
Time Windows,” Operations Research, 43, 1995, pp 367-371.
10.Fisher, M., and Jaikumar, R., “A Generalized Assignment
Heuristic for Vehicle Routing,” Networks, 11(2), 1981, pp
109-124.
11.Gillett, B., and Miller, L., “A Heuristic Algorithm for the
Vehicle Dispatch Problem,” Operations research, 22, 1974,
pp 340-349.
12.Grabowski, J., and Janiak, A., “Job Shop Scheduling with
Resource - Time Models of Operations,” European Journal of
Operational Research, 28, 1987, pp 58-73.
13.Kolen , A., Rinnooy Kan, A. H. G., and Trienekens, H. W. J.
M., “Vehicle Routing with Time Windows,” Operations
Research, 35, 1987, pp 266-273.
14.Koskosidis, Y. A., and Powell, W. B., “Clustering
Algorithms for Consolidation of Customer Orders into Vehicle
Shipments,” Transportation Research-B, 26B, 1992, pp 365-
379.
15.Lei, L., and Wang, T. J., “A proof: The Cyclic Hoist
Scheduling Problem is NP-complete,” Working paper No.89-16,
Rutger University, August 1989.
16.Lei, L., and Wang, T. J., “The Minimum Common-cycle
Algorithm for Cycle Scheduling of Time Windows
Constraints,” Management Science, 37/12,1991, pp 1629-1639.
17.Levy, L., and Bodin, L., “Scheduling the Postal Carriers
for the United States Postal Service : An Application of Arc
Partitioning and Routing,” In: Golden, B. L. and Assad, A.
A. (eds.), Vehicle Routing: Methods and Studies,North-
Holland,1988.
18.Phillips, D. T., and Alberto, G. D., “Fundamentals of
Network Analysis,” Prentice-Hall, Chapter 2, 1981, pp 72-90.
19.Phillips, L. W., and Unger, P. S., “Mathematical
Programming Solution of a Hoist Scheduling Program,” AIIE
Transactions, 8/2, 1976, pp 219-225.
20.Psaraftis, H., “An Exact Algorithm for the Single Vehicle
Many-to-many Dail-a-ride Problem with Time Windows,”
Transportation Science, 17, 1983, pp 351-360.
21.Shapiro, G. W., and Nuttle, H. W., “Hoist Scheduling for a
PCB Electroplating Facility,” AIIE Transactions, 20/2,
1988, pp 157-167.
22.Shier, D. R., “Iterative Methods for Determining the k
Shortest Paths in a Network,” Networks, 6, 1976, pp 205-230.
23.Swersey, A. J., and Ballard, W., “Scheduling School
Buses,” Management Science, 30, 1984, pp 844-853.
24.Yamada, T., and Nakano, R., “Job-shop Scheduling,” Genetic
Algorithms in Engineering Systems, Chapter 7, 1997, pp 134-
160.
25.Yang, D. L., and Chern, M. S.,“A Two Machine Flow shop
Sequencing Problem with Limited Waiting Time Constraints,”
Computers and Industrial Engineering, 28/2, 1994, pp 63-70.
26.Yih, Y., Liang, T. P., and Moskowitz, H., “Robot Scheduling
in a Circuit Board Production Line a Hybrid OR/ANN
Approach,” AIIE Transactions, 1993.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2001-6-29

推文