臺灣博碩士論文加值系統

能將有限的生產資源做最適當的分配，進而使得生產系統能夠以高效率、低成本的方式，產出合乎顧客要求的產品或服務，即是一個良好的排程作業。而排程作業的好壞，可利用衡量準則來評估，其主要可分為規則性與非規則性衡量準則，在過去研究多目標排程問題的論文中，大部分侷限於規則性衡量準則。近年來，及時化系統的觀念受到重視，生產系統開始要求排程作業需要同時考慮製成品存貨與在製品存貨成本，也就必須同時考量規則性與非規則性衡量準則。本研究以總加權完工時間與最大提前完工時間之雙目標排程為探討主題。
本文研究主題是以特定最大提前完工時間之最小化總加權完工時間的單機排程問題來進行。本研究針對此問題，建立近似解演算法，能夠在最短的時間內求得近似最佳解。接著發展凌越法則以及訂定下界值，建構分枝界限法，以求取最佳解。最後進行模擬測試，比較分析近似解演算法之績效，作成結論，供作實務應用與後續研究參考。

An excellent operations scheduling can reduces production cost by arranging the orders. To consider multiple objectives production scheduling can fulfill the complexity requirement of management. So, to consider multiple objectives production scheduling is necessary. The performance measure including regular and non-regular, it can be use to measure scheduling. In the past, almost scholars consider regular performance measure in scheduling problems. Recently, since the concept of JIT (Just In Time) had taken into consideration, so to consider both regular and non-regular performances on scheduling are necessary in JIT production system. Because JIT requires that the production system must to reduce in-process inventory and finished inventory. In other words, the manager must to consider both the total weighted completion time and maximum earliness performance measures on scheduling.
The study presents the heuristic algorithm and shows one problem can be solved. One problem is to minimize total weighted completion time subject to given maximum earliness on single machine. The computational results show that the heuristic algorithm can get the heuristic optimal solution in tiny time.

誌謝 i
摘要 ii
Abstract iii
目次 iv
圖目次 vii
表目次 ix
第一章、緒論 1
1.1 問題背景與研究動機 1
1.2 研究目的 2
1.3 研究問題與基本假設 4
1.3.1 研究問題 4
1.3.2 基本假設 4
1.4 符號說明 5
1.5 研究流程 6
1.6 論文架構 8
第二章、文獻探討 9
2.1 一般排程問題解法 9
2.1.1 最佳化解法 9
2.1.2 啟發式解法 10
2.1.3 派工法則 10
2.2 多目標單機排程問題 10
2.3 其他相關之多目標排程問題 13
2.4 分枝界限法 14
2.4.1分枝 15
2.4.2界限 15
2.4.3洞悉 16
第三章、研究方法 17
3.1啟發式演算法之發展 17
3.1.1定理發展 18
3.1.2建立啟發式演算法 19
3.1.1釋例 20
3.2分枝界限法模式建構 22
3.2.1上限值設定 22
3.2.2下限值(Lower Bound)設定 22
3.2.3凌越法則 23
3.2.4分枝界限法求解步驟 23
3.2.5釋例 26
第四章、實驗結果與分析 28
4.1測試資料建立 28
4.2參數設計 29
4.3實驗結果 36
第五章、結論與建議 42
5.1結論 42
5.2建議 44
參考文獻 45
表目次
表3-1 釋例 20
表3-2 釋例結果 21
表4-1測試資料型態 28
表4-2 測試資料類型子集 29
表4-3 A子集數據 30
表4-4 B子集數據 30
表4-5 C子集數據 31
表4-6 D子集數據 31
表4-7 E子集數據 32
表4-8 F子集數據 32
表4-9 G子集數據 33
表4-10 H子集數據 33
表4-11 I子集數據 34
表4-12 J子集數據 34
表4-13各子集參數區間數據 35
表4-23 數據資料 36
表4-24 數據資料 38
表4-25 ANOVA分析 40
圖目次
圖1-1研究流程圖 7
圖2-1分枝界限法之流程圖 14
圖3-1洞悉步驟 25
圖3-2 釋例圖 26

1.Smith, W. E. （1956）. Various optimizers for single-stage production. Naval Research Logistic Quarterly, 3, pp.59-66.
2.Emmons, H. （1975）. One machines sequencing to minimize mean flow time with minimum tardy. Naval Research Logistic Quarterly, 22, pp.585-592.
3.Emmons, H. （1975）. A note on a scheduling problem with a dual criteria. Naval Research Logistic Quarterly, 22, pp.615-616.
4.Van Wassenhove, L. N. & Baker, K. R. （1982）. A bicriterion approach to time/cost trade-offs in sequencing. European Journal of Operation Research, 11, pp.48-54.
5.Sen, T. & Gupta, S. K. （1983）. A branch and bound procedure to solve a bi-criterion scheduling problem. IIE Transaction, 15, pp84-88.
6.Nelson, R. T., Sarin R. K. & Daniels R. L. （1986）. Scheduling with multiple performance measures: The one-machine case. Management Science, 42, pp183-186.
7.Dileepan, p. & Sen, T. （1988）. Bicriterion static scheduling research for a single machine. Omega, 16, pp53-59.
8.Fry, T. D., Armstrong, R. D., & Lewis, H.（1989）. A framework for single machine multiple objective sequencing research. Omega, 17, pp.595-607.
9.Deniels, R. L.（1994）. Incorporating performance information into multi-objective scheduling. European Journal of Operation Research, 77, pp.272-286.
10.Nagar, A ., Haddock, J., & Heragu, S.（1995）. Multiple and bicriteria scheduling: A literature survey. European Journal of Operation Research, 81, pp.88-104.
11.Kondacki, K. S. & Bekiroglu, T.（1997）. Scheduling with bicriteria: Total flow time and number of tardy jobs. International Journal of Production Economics, 53, pp.91-99.
12.Kiksalan, M., Azizoglu, M., & Kondakci, S. K.（1998）. Minimizing flow time and maximum earliness on a single machine. IIE Transaction, 30, pp.192-200.
13.Chen, T. S., Qi, X. T., & Tu, F. S.（1999）. Single machine scheduling to minimize weighted earliness subject to maximum tardiness. Computers and Operations Research, 24, pp.147-152.
14.Azizoglu, M., Koksalan, M., & Kondakci, S. K.（2003）. Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed. Journal of the Operational Research Society, 54, pp.661-664.
15.Azizoglu, M., Koksalan, M., & Kondakci, S. K.（2003）. Single machine scheduling with maximum earliness and number tardy. Computers and Industrial Engineering, 45, pp.257-268.
16.Huang, R. H. & Yang, C. L.（2006）. Single machine scheduling to minimize the number of early and tardy jobs. Computers and Operations Research, 23, pp.769-781.
17.Jones, M. S. & Russell, R. S.（1990）. Multiple performance measure in the selection of a sequencing rule. International Journal of Operations and Production Management, 10, pp29-41.
18.Eck, B. T. & Pinedo, M.（1993）. On the minimization of the makespan subject to flowtime optimality. Operations Research, 41, pp.797-801.
19.Rajendran, C.（1999）. Formulations and heuristics for scheduling in a kanban flowshop to minimize the sum of weighted flow time, weighted tardiness and weighted earliness of containers. International Journal of Production Research, 37, pp.1137-1158.
20.Gupta, J. N. D.（2003）. Minimizing Maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow time. Journal of the Operation Research Society, 54, pp.1263-1274.
21.Toktas, B., Azizoglu, M., & Koksalan, S. K.（2003）. Two-machine flow shop scheduling with two criteria: maximum earliness and make-span. European Journal of Operation Research, 157, pp.286-295.
22.Yeung, W. K., Oguz, C., & Edwin Cheng, T. C.（2004）. Two-stage flowshow earliness and tardiness machine scheduling involving a common due window. International Journal of Production Economics, 90, pp.421-434.
23.Koksalan M, Azizoglu M and Kondakci SK.(1998), Minimizing flowtime and maximum earliness on a single machine, IIE Transaction, 30, pp.192-200.