臺灣博碩士論文加值系統

作業排程關心的問題是機器是否能有效率的處理工件。隨著及時化概念的興盛，工件的及時交付已經成為顧客滿意與否的一個重要指標。而在達成此目標上，排程扮演了一個重要的角色。關於及時化的議題，過往的研究大多都是求解提前懲罰與延遲懲罰加權總合最小。本研究假設機器均相同且工件獨立，並且有一相同之到期日時窗，探討提前與延遲工件數總合最小(或最大化及時工件數)的平行機排程問題。我們先發展與衡量準則相關之定理並據以建構一簡捷演算法，然後使用電腦模擬資料測試此演算法之有效性以及時效性。理論證明與資料測試結果均顯示，本文所提出的求解程序能夠在極短的時間獲得最佳解。更進一步的，本文針對電腦平均運算時間進行討論，結果顯示與電腦平均運算時間之關係為獨立的有：最早到期日參數、最晚到期日參數、處理時間變動型式及總機器數；而關係為相依有：總工件數。另一方面，本文考慮平均及時工件數，結果顯示與平均及時工件數之關係為獨立的有：最早到期日參數及處理時間變動型式；而關係為相依的有：最晚到期日參數、總機器數及總工件數。

Production scheduling is concerned with the problem of scheduling available machines to process jobs effectively. Due to the popularity of the just-in-time philosophy, in-time delivery of jobs has become one of the crucial factors for customer satisfaction. Scheduling plays an important role in achieving this goal. About the just-in-time issue, most of the prior researches were to deal with the problem of minimizing total earliness-tardiness penalty. In this paper, we study the scheduling problem of minimizing the number of early and tardy jobs (or maximizing the number of in-time jobs). Specifically, we consider the problem with a set of independent jobs to be processed on several identical parallel machines. All jobs have a common due window. We first develop some theorems about this performance measure. Then we propose an efficient solution algorithm for the problem according to those theorems. Finally, we use the simulated data to test the effectiveness and efficiency of the algorithm. Our computational experiments show that the algorithm we propose can get optimal solution in very short time. Further, we find that CPU time is independent of , , and m. It is dependent of n. On the other hand, maximizing the number of in-time jobs are independent of and . It is dependent of , m and n.

目 錄
頁次
第 壹 章 緒論--------------------------------------------------------------------- 1
第 一 節 問題背景與研究動機------------------------------------------ 1
第 二 節 研究範圍與限制------------------------------------------------ 2
第 三 節 研究目的--------------------------------------------------------- 4
第 四 節 研究流程--------------------------------------------------------- 4
第 五 節 論文架構--------------------------------------------------------- 6

第 貳 章 文獻探討------------------------------------------------------------ 7
第 一 節 平行機排程問題------------------------------------------------ 7
第 二 節 及時化排程問題------------------------------------------------ 9
第 三 節 時窗限制問題--------------------------------------------------13

第 參 章 | [ , ]| 問題---------------------------14
第 一 節 問題描述--------------------------------------------------------14
第 二 節 定理發展--------------------------------------------------------15
第 三 節 發展演算法-----------------------------------------------------17
第 四 節 釋例--------------------------------------------------------------18

第 肆 章 資料測試----------------------------------------------------21
第 一 節 資料建立--------------------------------------------------------21
第 二 節 資料測試結果與分析-----------------------------------------22

第 伍 章 結論與建議-----------------------------------------------------------26
第 一 節 結論--------------------------------------------------------------26
第 二 節 建議--------------------------------------------------------------28
參考文獻-----------------------------------------------------------------------29



表 目 錄

表 3-4-1 | [ , ]| 釋例資料-----------------------18
表 4-1-1 資料測試型式------------------------------------------------------------22
表 4-2-1 ~U[1, 30]的資料測試結果------------------------------------------22
表 4-2-2 ~U[1, 100]的資料測試結果----------------------------------------23
表 4-2-3 資料分析結果------------------------------------------------------------26

圖 目 錄

圖 1-4-1 研究流程圖---------------------------------------------------------------- 5
圖 4-2-1 總工件數與電腦平均運算時間關係圖-----------------------------24

1.Azizoglu, M., Koksalan, M., & Koksalan, S. K. (2003). Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed. Operational Research Society, 54, 661-664.
2.Baker, E. K. (1983). An exact algorithm for the time-constrained traveling salesman problem. Operation Research Society of America, 31(5), 938-945.
3.Baker, K. R. (1974). Introduction to sequencing and scheduling. NY：John Wiley & Sons.
4.Cai, X. Q., & Zhou, S. (1999). Stochastic scheduling on parallel machines subject to random breakdowns to minimize expected costs for earliness and tardy jobs. Operations Research, 47, 422-437.
5.Cheng, T. C. E., & Diamond, J. E. (1995). Scheduling two job classes on parallel machine. IIE Transactions, 27, 689-693.
6.Chen, T. S., Qi, X. T., & Tu, F. S. (1999). Single machine scheduling to minimize weighted earliness subject to maximum tardiness. Computers Operations Research, 24, 147-152.
7.Chen, Z. L., & Lee, C. Y. (2002). Parallel machine scheduling with a common due window. European Journal of Operational Research, 136, 512-527.
8.Duffuaa, S. O., Raouf A., Ben-Daya, M., & Makki, M. (1997). One-machine scheduling to minimize mean tardiness with minimum number tardy. Production Planning and Control, 8, 226-230.
9.Eck, B. T., & Pinedo, M. (1993). On the minimization of the makespan subject to flowtime optimality. Operations Research, 41, 797-801.
10.Feldmann, M., & Biskup, D. (2003). Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches. Computers and Industrial Engineering, 44, 307-323.
11.George I. A., & Costas P. P. (1998). Scheduling under a common due date on parallel unrelated machine. European Journal of Operation Research, 105, 494-501.
12.Gupta, J. N. D., Hariri, A. M. A., & Potts, C. N. (1999). Single-machine scheduling to minimize maximum tardiness with minimum number of tardy jobs. Annals of Operations Research, 92, 107-123.
13.Gupta, J. N. D., Ruiz-Torres, A. J., & Webster, S. (2003). Minimizing maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow-time. Journal of the Operational Research Society, 54, 1263-1274.
14.Hoogeveen, H. (2005). Invited review: Multicriteria scheduling. European Journal of Operational Research, 167, 592-623.
15.Koksalan, M., Azizoglu, M., & Kondakci, S. K. (1998). Minimizing flowtime and maximum earliness on a single machine. IIE Transactions, 30, 192-200.
16.Kondacki, K. S., & Bekiroglu, T. (1997). Scheduling with bicriteria: Total flowtime and number of tardy jobs. International Journal of Production Economics, 53, 91-99.
17.Koulamas, C. (1996). Single-machine scheduling with time windows and earliness/tardiness penalties. European Journal of Operational Research, 91, 190-202.
18.Lann, A., & Mosheiov, G. (1996). Single machine scheduling to minimize the number of early and tardy jobs. Computers & Operations Research, 23, 769-781.
19.Lann, A., & Mosheiov, G. (2003). A note on the maximum number of on-time jobs on parallel identical machines. Computers and Operations Research, 30, 1745-1749.
20.Liao, C. J., & Huang, R. H. (1991). An algorithm for minimizing the Range of lateness on a single machine. Journal of the Operational Research Society, 42, 183-186.
21.Nagar, A., Haddock, J., & Heragu, S. (1995). Multiple and bicriteria scheduling：A literature survey. European Journal of Operational Research, 81, 88-104.
22.Nelson, R. T., Sarin R. K., & Daniels, R. L. (1986). Scheduling with multiple performance measures: The one-machine case. Management Science, 32, 464-479.
23.Schaller, J. (2004). Single machine scheduling with early and quadratic tardy penalties. Computers and Industrial Engineering, 46, 511-532.
24.Sivrikaya-Serifoðlu, F., & Ulusoy, G. (1999). Parallel machine scheduling with earliness and tardiness penalties. Computers and Operations Research, 26(8), 773-787.
25.Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistic Quarterly, 3(1), 59-66.
26.Soloman, M. M., & Desrosiers, J. (1988). Time windows constrained routing and scheduling problem. Transportation Science, 22(1), 1-13.
27.Soroush, H. M. (1999). Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs. European Journal of Operational Research, 113, 450-468.
28.Van, W. L., & Baker, K. R. (1982). A bicriterion approach to time/cost trade-offs in sequencing. European Journal of Operational Research, 11, 48-54.
29.Van, W. L., & Gelders, L. F. (1980). Solving a bicriterion scheduling problem. European Journal of Operational Research, 4, 42-48.
30.Ventura, J. A., & Radhakrishnan, S. (2003). Single machine scheduling with symmetric earliness and tardiness penalties. European Journal of Operational Research, 144, 598-612.
31.Wu, C. C., Lee, W. C., & You, J. M. (2000). Trade-off solutions in a single-machine scheduling problem for minimizing total earliness and maximum tardiness. International Journal of Systems Science, 31, 639-647.
32.Zheng, W. X., Nagasawa, H., & Nishiyama, N. (1993). Single-machine scheduling for minimizing total cost with identical, asymmetrical earliness and tardiness penalties. International Journal of Production Research, 31, 1611-1620.