臺灣博碩士論文加值系統

雖然豐田式生產系統 (just-in-time；JIT) 被提出已超過二十餘年的時間，但在現今實務界的生產製造系統中，JIT的概念仍是相當的重要且被廣泛應用。因此在本論文中，我們將討論JIT排程問題中的共同到期日限制下求解總加權提早 (earliness) 及延遲 (tardiness) 最小化之單機排程問題。由於此問題係NP-hard，無最佳化演算法可應用，所以多位學者皆發展各種迭代型演算法如：模擬退火法、基因演算法、塔布搜尋法 (TS) 等，期能在合理的計算時間內得到不錯的結果。因此我們利用變動鄰域搜尋法 (variable neighborhood search；VNS) 結合塔布搜尋法求解此問題。我們提出的VNS/TS演算法具有幾項特色，包括：鄰域間的使用比率、從鄰域中隨機選取五個可行解、B/F局部搜尋法、VNS與TS的結合等。我們將此演算法對標竿問題作測試。實驗結果顯示，VNS/TS演算法不僅在解的品質上有顯著的效果，同時在計算時間方面也有不錯的表現。

Although the concept of just-in-time (JIT) production systems has been proposed for over two decades, it is still important in real-world production systems. In this thesis, we consider minimizing the total weighted earliness and tardiness with a common due date in a single machine environment, which has been proved as an NP-hard problem. Due to the complexity of the problem, metaheuristics, including simulated annealing, genetic algorithm, tabu search, among others, have been proposed for searching good solutions in reasonable computation times. In this thesis, we propose a hybrid metaheuristic that uses tabu search within variable neighborhood search (VNS/TS). There are several distinctive features in the VNS/TS algorithm, including different ratio of the two neighborhoods, generating five points simultaneously in a neighborhood, implementation of the B/F local search, and combination of TS with VNS. By examining the 280 benchmark problem instances, the algorithm shows an excellent performance in not only the solution quality but also the computation time. The results obtained are better than those reported previously in the literature.

CHINESE ABSTRACT………………………………………………………………..i
ENGLISH ABSTRACT……………………………………………………………….ii
ACKNOWLEDGEMENTS…………………………………………………………....iii
CONTENTS………………………………………………………………………...iv
LIST OF FIGURES…………………………………………………………….……v
LIST OF TABLES………………………………………………………………….vi
Chapter 1. INTRODUCTION……………………………………………….………1
Chapter 2. LITERATURE REVIEW......................................5
2.1. Just-in-time scheduling...................................5
2.2. Variable neighborhood search………………………………………9
2.3. Tabu search..............................................11
Chapter 3. THE PROPOSED ALGORITHM................................13
3.1. Components of the proposed VNS algorithm.................13
3.2. B/F local search.........................................15
3.3. Tabu search..............................................17
Chapter 4. COMPUTATIONAL EXPERIMENTS.............................20
4.1. Parameters setting of the proposed VNS/TS algorithm......20
4.2. Formal experiment of the proposed VNS/TS algorithm.......23
Chapter 5. CONCLUSIONS AND FUTURE RESEARCH.......................28
REFERENCES.......................................................30

Al-Turki, U., Fedjki, C., & Andijani, A. (2001). Tabu search for a class of single-machine scheduling problems. Computers and Operations Research, 28, 1223-1230.
Avanthay, C., Hertz, A., & Zufferey, N. (2003). A variable neighborhood search for graph coloring. European Journal of Operational Research, 151, 379-388.
Bagchi, U., Chang, Y. L., & Sullivan, R. S. (1987a). Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date. Naval Research Logistics, 34, 739-751.
Bagchi, U., Sullivan, R. S., & Chang, Y. L. (1986). Minimizing mean absolute deviation of completion times about a common due date. Naval Research Logistics, 33, 227-240.
Bagchi, U., Sullivan, R. S., & Chang, Y. L. (1987b). Minimizing mean absolute deviation of completion times about a common due date. Management Science, 33, 894-906.
Baker, K. R., & Scudder, G. D. (1990). Sequencing with earliness and tardiness penalties: A review. Operations Research, 38, 22-36.
Biskup, D., & Feldmann, M. (2001). Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Computers and Operations Research, 28, 787-801.
Cai, X., Lum, V. Y. S., & Chan, J. M. T. (1997). Scheduling about a common due date with job-dependent asymmetric earliness and tardiness penalties. European Journal of Operational Research, 98, 154-168.
Cheng, T. C. E. (1988). Optimal common due-date with limited completion time deviation. Computers and Operations Research, 15, 91-96.
Cheng, T. C. E. (1991). Optimal constant due-date determination and sequencing of n jobs on a single machine. International Journal of Production Economics, 22, 259-261.
Cheng, T. C. E., & Kahlbacher, H. G.. (1991). A proof for the longest-job-first policy in one-machine scheduling. Naval Research Logistics, 38, 715-720.
Crainic, T. G., Gendreau, M., & Farvolden, J. M. (2000). Simplex-based tabu search for the multicommodity capacitated fixed charge network design problem. INFORMS Journal on Computing, 12, 223-236.
De, P., Ghosh, J. B., & Wells, C. E. (1991). Optimal delivery time quotation and order sequencing. Decision Science, 22, 379-390.
Drummond, L. M. A., Vianna, L. S., Silva M. B., & Ochi L. S. (2002). Distribution parallel metaheuristics based on GRASP and VNS for solving the traveling purchaser problem. Proceedings of the 9th International Conference on Parallel and Distributed System, 257-263.
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.
Gagné, C., Gravel, M., & Price, W. L. (2005). Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems. Journal of the Operational Research Society, 56, 687-698.
Gendreau, M., Guertin, F., Potvin, J.-Y., & Taillard, E. D. (1999). Parallel tabu search for real-time vehicle routing and dispatching. Transportation Science, 33, 381-390.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13, 533-549.
Glover, F. (1993) A user’s guide tabu search. Annals of Operations Research, 41, 3-28.
Glover, F., & Kochenberger, G. A. (2003). Handbook of metaheuristics. Boston, MA: Kluwer Academic Publisher.
Gordon, V., Proth, J.-M., & Chu, C. (2002). A survey of the state-of-the-art of common due date assignment and scheduling research. European Journal of Operational Research, 139, 1-25.
Hall, N. G.., Kubiak, W., & Sethi, S. P. (1991). Earliness-tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date. Operations Research, 39, 847-856.
Hall, N. G.., & Posner, M. E. (1991). Earliness-tardiness scheduling problems, I: Weighted deviation of completion times about a common due date. Operations Research, 39, 836-846.
Hansen, P., Jaumard, B., Mladenović, N., & Parreira, A. (2000). Variable neighborhood search for weighted maximum satisfiability problem. Les Cahiers du GERAD G-2000-62, Montréal, Canada.
Hansen, P., & Mladenović, N. (1997). Variable neighborhood search for the p-Median. Location Science, 5, 207-226.
Hansen, P., & Mladenović, N. (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, 130, 449-467.
Hansen, P., Mladenović, N., & Perez-Brito, D. (2001). Variable neighborhood decomposition search. Journal of Heuristics, 7, 335-350.
Herrmann, J. W., & Lee, C.-Y. (1993). On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date. European Journal of Operational Research, 70, 272-288.
Hino, C. M., Ronconi, D. P., & Mendes, A. B. (2005). Minimizing earliness and tardiness penalties in a single-machine problem with a common due date. European Journal of Operational Research, 160, 190-201.
Hoogeveen, J. A., & van de Velde, S. L. (1991). Scheduling around a small common due date. European Journal of Operational Research, 55, 237-242.
James, R. J. W. (1997). Using tabu search to solve the common due date early/tardy machine scheduling problem. Computers and Operations Research, 24, 199-208.
Kahlbacher, H. G., & Cheng, T. C. E. (1993). Parallel machine scheduling to minimize costs for earliness and number of tardy jobs. Discrete Applied Mathematics, 47, 139-164.
Kanet, J. J. (1981). Minimizing the average deviation of job completion times about a common due date. Naval Research Logistics Quarterly, 28, 643-651.
Li, C.-L., & Cheng, T. C. E. (1994). The parallel machine min-max weighted absolute lateness scheduling problem. Naval Research Logistics, 41, 33-46.
Liaw, C. F. (2003). An efficient tabu search approach for the two-machine preemptive open shop scheduling problem. Computers and Operations Research, 30, 2081-2095.
Lopez, F. G., Batista, B. M., Moreno Pérez, J. A., & Moreno Vega, J. M. (2003). The parallel variable neighborhood search for the p-median problem. Parallel Computing, 29, 575-589.
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers and Operations Research, 24, 1097-1100.
Panwalkar, S. S., Smith, M. L., & Seidmann, A. (1982). Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research, 30, 391-399.
Ribeiro, C. C., & Souza, M. C. (2002). Variable neighborhood search for the degree-constrained minimum spanning tree problem. Discrete Applied Mathematics, 118, 43-54.
Seidmann, A., Panwalkar, S. S., & Smith, M. L. (1981). Optimal assignment of due-dates for a single processor scheduling problem. International Journal of Production Research, 19, 393-399.
Skorin-Kapov, J. (1990). Tabu search applied to the quadratic assignment problem. ORSA Journal on Computing, 2, 33-45.
Tasgetiren, M. F., Liang, Y. C., Sevkli, M., & Gencyilmaz, G. (2004). Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop sequencing problem. Proceedings of the Fourth International Symposium on Intelligent Manufacturing Systems, Sakarya, Turkey, 431-441.