臺灣博碩士論文加值系統

排程是一種資源與時間分配的決策，在一個資源有限的生產系統中，需要優良的排程作業以達到最佳化的工作分派與加工時序安排，讓組織內有限資源作最有效的運用。而近年來及時化的觀念越來越受到業者重視，決策者開始注意到過去被忽略的提前完工的成本。
考量在製品與製成品之存貨成本，我們希望藉由總流程時間與提前完工件數為準則之單機排程研究，解決管理者面對及時化生產問題可能遭遇的瓶頸；透過提供管理者有效降低成本及提高生產效率的排程決策，以使企業更有效率運用資源提升競爭優勢。
因此，本研究以總流程時間與提前完工件數之多目標排程問題進行研究，提出數個凌越法則以建構分枝界限法。模擬資料測試結果，證實本研究所發展的分枝界限法可在極短時間內取得完整的有效排序集合，可作為管理實務應用，或相關研究參考。

Scheduling deals with the allocation of resource to arrange over time. It is a decision-making process with the goal of optimizing one or more objectives. Effective sequencing and scheduling has become a necessity for survival in the current competitive environment.
In this paper we study the properties of efficient schedules with respect to flow time and the number of tardy jobs. Minimizing the flow time implies minimizing work-in-process inventory. On the other hand, minimizing the number of early can be considered as a measure of customer’s concerns. Therefore, we included measure representing both the manufacture’s and customer’s concerns.
Hence we develop new theorems, that can be used to reduce the problem size and eliminate inferior schedules. Some properties identify the job which can be sequenced last in an efficient schedule. Other properties of efficient solutions are also discussed.

第一章　緒論------------------------------------------------------------------------ 1
　　一、問題背景與研究動機--------------------------------------------------- 1
　　二、研究範圍與限制--------------------------------------------------------- 2
　　三、研究目的------------------------------------------------------------------ 3
　　四、研究流程------------------------------------------------------------------ 5
第二章　文獻探討------------------------------------------------------------------ 7
　　一、一般排程問題解法------------------------------------------------------ 7
　　二、多目標單機排程問題--------------------------------------------------- 8
　　三、其他相關之多目標排程問題------------------------------------------ 10
　　四、分枝界限法--------------------------------------------------------------- 11
第三章　F與nE雙準則之單機排程問題-------------------------------------- 13
　　一、相關定理------------------------------------------------------------------ 13
　　二、分枝界限法--------------------------------------------------------------- 15
　　三、釋例------------------------------------------------------------------------ 16
第四章　資料測試------------------------------------------------------------------ 19
　　一、測試資料建立------------------------------------------------------------ 19
　　二、測試結果------------------------------------------------------------------ 20
　　三、測試結果分析------------------------------------------------------------ 22
第五章　結論與建議--------------------------------------------------------------- 25
　　一、結論------------------------------------------------------------------------ 25
　　二、結論------------------------------------------------------------------------ 26
參考文獻------------------------------------------------------------------------------ 27

1.Azizoglu, M., Koksalan, M., & Koksalan, S. K. (2003a). Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed. Operations Research Society, 54, 661-664.
2.Azizoglu, M., Kondakci, S., & Koksalan, M. (2003b). Single machine scheduling with maximum earliness and number tardy. Computers and Industrial Engineering, 45, 257-268.
3.Backer, J. R. & Mcmahon, G. B. (1985). Scheduling the general job-shop. Management Science, 31, 594-598.
4.Balas, E. (1969). Machine scheduling via disjunctive graphs︰An implicit Enumeration algorithm. Operations Research, 17, 941-957.
5.Brooks, G. H. & White, C. R. (1965). An algorithm for finding optimal or near optimal solutions to the production scheduling problem. Journal of Industrial Engineering, 16, 34-40.
6.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, 147-152.
7.Daniels, R. L. (1994). Incorporating performance information into multi-objective scheduling. European Journal of Operation Research, 77, 272-286.
8.Dileepan, P. & Sen, T. (1988). Bicriterion static scheduling research for a single machine. Omega, 16, 53-59.

9.Emmons, H. (1975a). One machines sequencing to minimize mean flow time with minimum tardy. Naval Research Logistic Quarterly, 22, 585-592.
10.Emmons, H. (1975b). A note on a scheduling problem with a dual criteria. Naval Research Logistic Quarterly, 22, 615-616.
11.Fisher, M. L. (1976). A dual algorithm for the one-machine scheduling problem. Math Programmimg, 11.229-251.
12.Fry, T. D., Armstrong, R. D., & Lewis, H. (1989). A framework for single machine multiple objective sequencing research. Omega, 17, 595-607.
13.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, 1263-1274.
14.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, 29-41.
15.Huang, R. H. & Yang, C. L. (2006). Single-machine scheduling to minimize the number of early jobs. Computers and Operations Research, submitted.
16.Ignall, E. & Schrage, L. (1965). Application of the branch and bound technique to some flow shop scheduling problem. Operations Research, 13, 400-412.
17.Ishibuchi, H. & Murata, T. (1998). A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Transaction on System, Man and Cybernetics-Part C Application and Revie, 28, 392-403.

18.Itoh, K., D. Huang, & T. Enkawa. (1993). Twofold look-ahead search for multi-criterion job shop scheduling. International of Journal Production Research, 31, 2215-2234.
19.Koksalan, M., Azizoglu, M., & Kondakci, S. K. (1998). Minimizing flow time and maximum earliness on a single machine. IIE Transaction, 30, 192-200.
20.Kondacki, K. S. & Bekiroglu, T. (1997). Scheduling with bicriteria: Total flow time and number of tardy jobs. International Journal of Production Economics, 53, 91-99.
21.Lageweg, B. J., Lenstra, K., & Rinnooy Kan, A. H. G. (1997). Job-shop scheduling by implicit enumeration. Management Science, 24, 441-450.
22.Li, G. (1997). Single machine earliness and tardiness scheduling. European Journal of Operation Research, 96, 546-558.
23.Liaw, C. F. (1999). A branch and bound algorithm for the single machine earliness and tardiness scheduling problem. Computers and Operations Research, 26, 679-693.
24.Lomnicki, Z. A. (1965). A branch and bound algorithm for the exact solution of the three-machine scheduling problem. Operations Research Quarterly, 16, 89-100.
25.Murata, T., Ishibuchi, H., & Tanaka, H. (1996). Multi-objective genetic algorithm and its application to flowshop scheduling. Computers and Industrial Engineering, 30, 957-968.


26.Nagar, A., Haddock, J., & Heragu, S. (1995). Multiple and bicriteria scheduling: A literature survey. European Journal of Operation Research, 81, 88-104.
27.Neppalli, V. R., Chen, C. L., & Gupta, J. (1996). Genetic algorithms for two stage bicriteria flowshop problem. European Journal of Operation Research, 95, 356-373.
28.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, 1137-1158.
29.Sen, T. & Gupta, S. K. (1983). A branch and bound procedure to solve a bi-criterion scheduling problem. IIE Transaction, 15, 84-88.
30.Singer, M. & Pinedo, M. (1998). A computational study of branch and bound techniques for minimizing the total tardiness in job shops. IIE Scheduling Logistics, 29, 109-119.
31.Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistic Quarterly, 3, 59-66.
32.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, 286-295.
33.Van Wassenhove, L. N. & Baker, K. R. (1982). A bicriterion approach to time/cost trade-offs in sequencing. European Journal of Operation Research, 11, 48-54.

34.Yeung, W. K., Oguz, C., & Edwin Cheng, T. C. (2004). Two-stage flowshop earliness and tardiness machine scheduling involving a common due window. International Journal of Production Economics, 90, 421-434.
35.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, 1661-1620.