臺灣博碩士論文加值系統

無論在實務應用或理論探討上，多目標排程問題一直受到管理決策者與學者的重視，然而問題本質上多為NP-hard，一般用來解決此類問題的方法有兩種，一為可以取得最佳解，但時效性較差的正確解法；另一為啟發式解法。在分秒必爭的激烈的環境中，花很長時間去等待一個最佳解的出現，並不符合企業管理原則。相對的，啟發式解法雖然不能保證得到最佳解，但卻可以迅速的取得近似最佳解，實務上，具備時效性的近似最佳解，對管理者言，可能比最佳解更有意義。
近年來，已經發展出一些共通式啟發解法，如塔布搜尋法(TA，tabu search)、模擬退火法(SA，simulated annealing) 、類神經網路(neural network)、基因演算法(GA，genetic algorithms)、蟻群最佳化(ACO，ant colony optimization)等，可以用來求解複雜度較高的排程問題。
本文整合了蟻群演算法及模擬退火法建構一個求解多目標排程問題的共通式演算法。此整合演算法可以用來求解流程式排程之近似有效解集合。
透過切合實際環境排程問題的設計，整合利用模擬退火法較佳的全域搜尋能力，以及深入搜尋能力較佳的蟻群演算法，可以迅速取得近似最佳解，提供管理者用來解決多目標流程式排程問題。資料測試結果顯示本文所建構之整合演算法比現有之模擬退火法具有更好的求解效果，當機器數超過10個以上，在10種雙準則的多目標問題中，具有80% 以上的勝率。

Managers and scholars have paid much attention to multi-objective scheduling problems in either realistic applications or theoretical studying. However they are almost part of NP-hard problems. In general, there are two ways to cope with these problems. One is Exact Solution which could get optimum solutions but has bad efficiency; the other one is meta-heuristic solution. In competitive environment, in order to seize every time and second, businesses are not willing to spend much time to get exact solution, it does not conform to business management principles. Instead of exact solution, meta-heuristic solution dose not guarantee to find exact solution, but it could get approximate solution very quickly. In reality, approximate solution with efficiency might be meaningful for managers.
Recently, some meta-heuristic solutions, such as Tabu Search, Simulated Annealing, Neural Network, Genetic Algorithms, and Ant Colony Optimization and so on, have been developed to deal with high complexity scheduling problems.
In this research, we integrate ant colony optimization and stimulated annealing to construct a meta-heuristic solution to solve multi-objective scheduling problems. The method could be used to get complete efficient solution set of flow shop scheduling.
We could offer approximate solution very quickly by designing for realistic environmental scheduling problems, integrating the ability of simulated annealing to search global solution and the ability of ant colony optimization to search deeply to managers to cope with multi-objective scheduling problems. The results of data test display that the effect of our integrated algorithm is better than traditional simulated annealing. When test over ten machines, we could get more than 80% wins in ten kinds of multi-objective problems.

第壹章 緒論 1
第一節 問題背景與研究動機 1
第二節 研究範圍與限制 2
第三節 研究目的 6
第四節 研究流程 6
第貳章 文獻探討 8
第一節 排程問題求解方法 8
第二節 多目標作業排程 9
第三節 模擬退火法 13
第四節 螞蟻族群系統 17
第叁章 研究方法 22
第一節 多目標流程式系統排程問題 22
第二節 整合模擬退火與蟻群系統演算法 24
第三節 演算法流程架構 29
第四節 釋例 31
第肆章 資料測試 38
第一節 資料設定 38
第二節 實驗結果 40
第三節 結語 42
第伍章 結論與建議 45
第一節 結論 45
第二節 建議 46
參考文獻 47

中文部分
1.江朋南(2003)。蟻族系統在零工型排程問題之應用。國立台灣科技大學工業管理系碩士論文，台北市。
2.江柏彥(2006)。蟻群系統於多目標流程式排程近似有效解之研究。輔仁大學管理學研究所未完成之碩士論文，新莊市。
3.陳鴻裕(1992)。在具有學習效果下雙機雙準則流程工廠之研究。逢甲大學統計與精算研究所碩士論文，台中市。
4.盧研柏(2003)。混合式模擬退火法應用於迴流特性流程工廠之研究。國立台灣科技大學工業管理系碩士論文，台北市。
英文部分
1.Arroyo, J. E. C. & Armentano, V. A. (2005). Genetic local search for multi-objective flowshop scheduling problems. European Journal of Operational Research, 167, 717-738.
2.Baker, K. R. & Smith, J. C. (2003). A multiple-criterion model for machine scheduling. Journal of Scheduling, 6, 7–16.
3.Bülbül, K., Kaminsky, P., & Yano C. (2003). Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs. Department of IEOR, University of California at Berkeley.
4.Chen, C. L. & Bulfin, R. L. (1993). Complexity of a single machine multi-criteria scheduling problems. European Journal of Operational Research, 70, 115–125.
5.Chou, F. D. & Lee, C. E. (1999). Two-machine flowshop scheduling with bicriteria problem. Computers & Industrial Engineering, 36, 549-564
6.Cochran, J. K., Horng, S., M. & Fowler, J. W. (2003). A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers& Operations Research, 30, 1087-1102.
7.Colorni, A., Dorigo, M., Maniezzo, V., & Trubian, M. (1994). Ant System for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, 34, 39–53.
8.Di Caro, G. & Dorigo, M. A. (1997). A mobile agents approach to adaptive routing, Technical report.
9.Dorigo, M. & Caro, G. D. (1999). The Ant Colony Optimization meta-heuristic. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 11–32. McGraw Hill, London, UK.
10.Dorigo, M. & Gambardella, L. M. (1997). Ant colonies for the traveling salesman problem. BioSystems, 43, 73-81.
11.Dorigo, M. & Gambardella, L. M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1, 53-66.
12.Dorigo, M. & Di Caro, G. (1999). Gambardella LM, Ant algorithms for discrete optimization. Artificial Life, 5, 137-172.
13.Eck, B. T. & Pinedo, M. L. (1993). On the minimization of the makespan subject to flowtime optimality. Operations Research, 41, 797–801.
14.Fisher, M. L. (1976). A dual algorithm for the one-machine scheduling problem. Mathematical Programming, 11, 229-251.
15.Gambardella, L. M. & Dorigo, M. (2001). An ant colony system hybridised with a new local search for the sequential ordering problem. Informs Journal on Computing.
16.Gambardella, L. M., Taillard, E. D., & Dorigo, M. (1997). Ant colonies for the QAP. Technical report.
17.Gupta, A. K. & Sivakumar, A. I. (2004). Multi-objective scheduling of two-job families on a single machine. Omega, 33, 399-405
18.Gupta, J. N. D. & Alex, R. T. (2005). Generating efficient schedules for identical parallel machines involving flow-time and tardy jobs. European Journal of Operational Research, 167, 679-695
19.Gupta, J. N. D., Neppalli, V. R., & Werner, F. (2001). Minimizing total flow time in a two-machine flowshop problem with minimum makespan. International Journal of Production Economics, 69, 323–338.
20.Gupta, S. & Sen, T. (1984). Minimizing the range of lateness on a single machine. Journal of the Operational Research Society, 35, 853-857.
21.Hoogeveen, H. (1992). Single machine bicriteria scheduling. Ph.D. dissertation, University of Eindhoven.
22.Hoogeveen, J. A. (2005). Invited Review: Multicriteria scheduling. European Journal of Operational Researc,. 167, 592-623.
23.Hoogeveen, J. A., Potts, C. N. & Woeginger, G. J. (2000). On-line scheduling on a single machine: maximizing the number of early jobs. Operations Research Letters, 27, 193-197.
24.Hoogeveen, J. A. & van de Velde, S. L. (1996). A branch-and-bound algorithm for single-machine earliness–tardiness scheduling with idle time. INFORMS Journal on Computing, 8, 402–412.
25.Hoogeveen, J. A. & van de Velde, S. L. (1997). Earliness–tardiness scheduling around almost equal due dates. INFORMS Journal on Computing, 9, 92–99.
26.Joseph, Y. T. L. & James, H. A. (2004). Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall/CRC.
27.Kirpatrick, S. Gelatt, J. C., & Vecchi, M. (1983). Optimization by Simulated Annealing. Science, 220, 671-680.
28.Koksalan, M. & Keha, A. B. (2003). Using genetic algotithms for single-machine bicteria scheduling problems. European Journal of Operational Research, 145, 543-556.
29.Kyparisis, G. J. & Koulamas, C. (2000). Open shop scheduling with makespan and total completion time criteria. Computers& Operations Research, 27, 15–27.
30.Lann, Avital, Mosheiov, & Gur. (1996). Single machine scheduling to minimize the number of early and tardy jobs. Computers & Operations Research, 23, 769-781.
31.Lawler, E. L. (1982). Scheduling a single machine to minimize the number of late jobs. Preprint, Computer Science Division, University of California, Berkeley.
32.Lawler, E. L.& Labetoulle, J. (1978). On preemptive scheduling of unrelated parallel machines with linear programming. Journal of the Association of Computing Machinery, 25, 612–619.
33.Lawler, E. L., Lenstra, J. K., & Rinnooy, A.H.G. (1981). Minimizing maximum lateness in a two-machine open shop. Mathematics of Operations Research, 6, 153–158.
34.Lenstra, J. K. (1990). Unpublished manuscript, Lenstra JK, Tardos E, Shmoys DB, Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46, 259–271.
35.Leung, J. Y. T. & Young, G. H. (1989). Minimizing schedule length subject to minimum flow time. SIAM Journal on Computing, 18, 314–326.
36.Li, C. L.; Cheng, T. C. E., & Chen, Z. L. (1995). Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs. Computers & Operations Research, 22, 205-219.
37.Li, G. (1997). Single machine earliness and tardiness scheduling. European Journal of Operational Research, 96, 546-558.
38.Loukil, T., Teghem, J., & Tuyttens, D. (2005). Solving multi-objective production scheduling problems using metaheuristics. European Journal of Operational Research, 161, 42-61.
39.Mansooreh, G. R. & Anagnostopoulos, G. C. (2004). A branch-and-bound algorithm for the early/tardy machine scheduling problems with a common due-date and sequence-dependent setup time. Computer & Operations Research, 31, 1727-1751
40.Mansouri, S. A. (2005). A Multi-Objective Genetic Algorithm for mixed-model sequencing on JIT assembly lines. European Journal of Operational Research, 167, 696-716.
41.Masuda, T. & Ishii, H. (1994). Two machine open shop scheduling problem with bi-criteria. Discrete Applied Mathematics, 52, 253–259.
42.Metropolis, N., Rosenblush, A., & Rosenblush, M. (1953). Teller, A. and Teller, E., Equation of State Calculations by Fast Computing Machind. Journal of Chemical Physics, 21, 1087-1092.
43.Peha, J. M. (1994). Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time. Computer Ops Res, Vol. 22, No. 10, 1089-1100.
44.Richard, W. C., William, L. M., & Louis, W. M. (2003). Operation research. Dover Publications.
45.Roy, B. & Sussmann, B. (1964). Les problems d’ordonnancement avec contraintes disjunctives, Notes DS N.9 Bis, SEMA, Montrouge.
46.Shanthikumar, J. G. (1983). Scheduling jobs on one machine to minimize the maximum tardiness with minimum number of tardy. Computers & Operations Research, 10, 253–265.
47.Smith, W. E. (1956). Various optimizers for single stage production. Nav. Res. Logist, 31, p. 325-333.
48.Sourd, F. (2005). Earliness-tardiness scheduling with setup considerations. Computers & Operations Research, 32, 1849-1865.
49.Stützle, T. (1998). An ant approach to the flow shop problem, in: Proceedings of EUFIT’98, Aachen (Germany), 1560–1564.
50.T’kindt, V. & Billaut, J. C. (2002). Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Berlin.
51.Tadei, R., Grosso, A. & Della Croce, F. (2005). Finding the Pareto-optima for the total and maximum tardiness single machine problem. Discrete Applied Mathematics, 124, 117–126.
52.Tegze, M. & Vlach, M. (1988). Improved bounds for the range of lateness on a single machine. Journal of the Operational Research Society, 39, 675-680,.
53.Toktas, B., Azizoglu, M. & Koksalan, S. K. (2003). Two-machine flow shop scheduling with two criteria: maximum earliness and make-span. European Journal of Operational Research, 157, 286-295.
54.Van Wassenhove, L. N. & Gelders, L. F. (1980). Solving a bicriterion scheduling problem. European Journal of Operational Research, 4, 42-48.
55.Varadharajan, T. K. & Rajendran, C. (2005). A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. European Journal of Operational Research, 167, 772-795.
56.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.
57.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.
58.Zhu, Z. & Heady, R. B. (2000). Minimizing the sum of earliness/tardiness in mult-machine scheduling: a mixed integer programming approach. Computers & Industrial Engineering, 38, 297-305.