臺灣博碩士論文加值系統

因全球化影響下，工廠排程技術問題不斷的改良提升，因此如何設計一套有效生產排程方式，提升機器使用效能及減少生產成本，是目前最主要的課題。最近這幾年來，因生產的總產品項越來越複雜，所以傳統的生產排程已經不敷需求，需要加以改良，而越來越多的製造業利用及時化生產(Just in Time)的方式，以有效的降低存貨成本並且即時反應顧客需求，並且某些商品會具有時效性的問題，如生鮮產品類等，有一定的保存期限會對生產成本增加有很大的影響，因此必須具有最大提前完工時間( )之限制。再者單機排程研究考量績效衡量準則相當多，其中最小化帶折扣總加權完工時間(Minimizing Discounted Total Weighted Completion Time；MDTWCT)慢慢受到重視，主要利用加權折扣最短加工時間(Weighted Discounted Shortest Processing Time；WDSPT)求解MDTWCT是為最佳解。
因此本研究問題應用結合分枝界限法(Branch-and-Bound method；B&B)和WDSPT法，建構近似解演算法，並制定發展凌越法則及下限值，以求解最大提早完工時間限制之MDTWT單機排程問題。

Due to the influence of globalization, the factory’s scheduling technology problems are improvement continuously. Now the most important topic for discussion is to design a set of effective production scheduling mode, to improve the efficiency of machine and reduce the production cost. Recently, the traditional production scheduling can not fulfill requirements anymore, it needs to improvement because the total product items becoming more and more complex. More and more manufacturing use Just In Time(JIT) mode to reduce cost of stock effectively and response customer’s requirements in time. Some goods have time-limit problem and that will be a major influence on production cost, just like vegetables or fruits etc... Therefore, it’s need to limited the . And there are many criterions to estimate for achievements in the single machine scheduling research, in which the minimizing discounted total weighted completion time(MDTWCT) is received much attention gradually. The best result and principal is by weighted discounted shortest processing time(WDSPT) to solve MDTWCT.
Hence, this research combine the branch-and-bound method and WDSPT to found on Heuristic Algorithm. Set up dominance criterion and lower bound to solve the problem of MDTWT single machine scheduling.

誌謝 ii
摘要 iii
ABSTRACT v
目次 vii
表目次 x
圖目次 xii
第一章、緒論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 研究問題與限制條件 3
1.3.1 研究問題 3
1.3.2 限制條件與假設 3
1.4 符號說明 4
1.5 研究流程 5
1.6 論文架構 7
第二章、文獻探討 8
2.1 排程問題 8
2.2 單機排程問題 9
2.3 加權帶折扣最短加工時間 11
2.4 分枝界限法 14
2.4.1 分枝(Branching) 15
2.4.2 界限(Bounding) 15
2.4.3 洞悉(Fathomed) 16
第三章、研究方法 17
3.1啟發式演算法建構 17
3.1.1啟發式演算法建構步驟 17
3.1.2啟發式演算法範例說明 18
3.2分枝界限法模式建構 21
3.2.1上限值(Upper Bound)設定 21
3.2.2下限值(Lower Bound)設定 21
3.2.3分枝界限法求解步驟 22
3.2.4分枝界限法範例說明 23
第四章、實驗結果與分析 26
4.1實驗題目設計 26
4.2參數設計 27
4.3實驗結果 35
第五章、結論與建議 43
5.1結論 43
5.2建議 43
參考文獻 45

1. Sule, D.R. (1996) “Industrial Scheduling”, PWS. Publishing Company.
2. Cheng, T.C.E. and Sin, C.C.S. (1990) “A state-of-the-art review of parallel-machine scheduling research”, European Journal of Operational Research, 47, pp. 271-292.
3. Conway, R.W., Maxwell, W.L. and Miller, L.W. (1967) “Theory of Scheduling”, Addison-Wesey, Boston.
4. Zheng,W. X., Nagasawa, H. and Nishiyama, N.(1993) “Single-machine scheduling for minimizing total cost with identical, asymmetrical earliness and tardiness penalties”, International Journal of Production Research, 31, pp.1611-1620.
5. Kunnathur A.S., Gupta S.K.(1990) “Minimize the makespan with late startpenalties added to processing time in a single facility scheduling problem”, European Journal of Operational Research, 47, pp. 56-64.
6. Wu C.C., Lee W.C., Shiau Y.R. (2006) “Minimizing the total
completion time on a single machine under linear deterioration” , Int J Adv Manuf Technol DOI: 10.1007/s00170-006-0565-8.
7. Ten, H.A.(1991) “Minimizing Total Earliness, Tardiness and Setup Cost” , Research Report NO.RR1991-12. School of Management and Organization University of Groningen.
8. Tavakkoli-Moghaddam R., Moslehi G., Vasei M., Azaron A. (2005) “A branch-and-bound algorithm for a single machine sequencing to minimize the sum of maximum earliness and tardiness with idle insert” , Applied Mathematics and Computation 388-408.
9. Azizoglu M、Koksalan M and Koksalan SK.(2003) “Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed” , Journal of the Operational Research Society, 661-664.
10. Hall, N.G. and. Posner, M.E. (1991) “Earliness-Tardiness Scheduling Problems I ：Weighted Deviation of Completion Times about a Common Due Date” , Operations Research, pp.836-849.
11. Hall, V.G., Kubiak and Sethi, S.P., “Earlinss-Tardiness Scheduling Problems, II : Deviation of Completion Times About a Restrictive Common Due Date” , Operations Research, Vol.39, pp.847-856.
12. Davis, J. and Kanet, J. (1989) “Single Machine Scheduling with a Nonregulat Convex Performance Measure” , IEEE International Conference on, 7, pp.343-356.
13. Tanaka, S. and Sasaki, T. (2003) “A branch-and-bound algorithm for the single-machine weighted earliness-tardiness scheduling problem with job independent weights” , IEEE International Conference on, 2 , pp.1571-1577.
14. Huang R-H and Yang C-L.(2008) “An algorithm for minimizing flow time and maximum earliness on a single machine” , Journal of the Operational Research Society, pp.1-5.
15. Pinedo M.(2002) “Single Machine Models”, Scheduling Theory, Algorithms, and Systems, 3, pp.39-40.
16. 李建更、阮曉鋼、楊明 (2004) 「單機帶折扣的加權完成時間總和調度問題最優調度的區間攝動魯棒性」，第五屆全球智能控制與自動化大會，中國杭州。
17. Yang Wen-Hua.(2007) “Scheduling jobs on a single machine to maximize the total revenue of jobs” , Computers & Operations Research, pp.565-583.
18. 成龍、劉小冬、楊斌鑫 (2004) 「單機排序1｜sp-graph｜ 的最優算法」，系統工程理論方法應用。
19. 趙琨、唐恒永 (2003) 「無空閒Flow shop帶折扣加權排序的演算法」，瀋陽師範大學學報(自然科學版)。
20. 肖勇、唐恒永 (2003) 「帶有折扣因子的樹型約束排序問題的最優算法」，系統工程理論方法應用。
21. 唐恒永、肖勇 (2002) 「問題1| S, GT| 的最優算法」，瀋陽師範學院學報:自然科學版。
22. 王吉波、唐恒永 (2001) 「Flow Shop 排序問題F2｜prmu｜ 的一個啟發式算法」，系統工程理論方法應用。
23. Koksalan M, Azizoglu M and Kondakci SK.(1998) “Minimizing flowtime and maximum earliness on a single machine” , IIE Trans 30, pp.192-200.