臺灣博碩士論文加值系統

In this study, we consider the scheduling problem for job shop environment with the objective to minimize the makespan. Variable neighborhood descent (VND) algorithm with two versions VNDI and VNDII is proposed to solve the problem. Besides, two simple neighborhood structures based on critical operation concept are generated to be implemented with VND algorithm. Preliminary test is performed to evaluate performance of two versions of VND and the obtained results indicates that VNDI outperforms VNDII with better solution and shorter computational time. Computational tests are carried out on 45 well-known instances applying VNDI and the results are compared with the benchmark solutions and with several algorithms from other published works, in order to measure the performance of the proposed algorithm. Computational results show that VNDI is effective to find optimal or near-optimal solutions of most of the tested instances in reasonable execution time. Apart from this, VNDI is proved to perform better for rectangular instances or instances for which the number of jobs is much larger than the number of machines, than the square instances.

In this study, we consider the scheduling problem for job shop environment with the objective to minimize the makespan. Variable neighborhood descent (VND) algorithm with two versions VNDI and VNDII is proposed to solve the problem. Besides, two simple neighborhood structures based on critical operation concept are generated to be implemented with VND algorithm. Preliminary test is performed to evaluate performance of two versions of VND and the obtained results indicates that VNDI outperforms VNDII with better solution and shorter computational time. Computational tests are carried out on 45 well-known instances applying VNDI and the results are compared with the benchmark solutions and with several algorithms from other published works, in order to measure the performance of the proposed algorithm. Computational results show that VNDI is effective to find optimal or near-optimal solutions of most of the tested instances in reasonable execution time. Apart from this, VNDI is proved to perform better for rectangular instances or instances for which the number of jobs is much larger than the number of machines, than the square instances.

Table of Contents
Title Page ................................................. i
Abstract in English ........................................ ii
Acknowledgement............................................. iii
Table of Contents .......................................... iv
List of Tables ............................................. vi
List of Figures ............................................ vii
Chapter 1 Introduction ..................................... 1
1.1. Research Background ................................ 1
1.2. Research Motivation................................. 2
1.3. Organization of the thesis ......................... 3
Chapter 2 Literature review ................................ 5
2.1. Review of the job shop scheduling problem literature .. 5
2.2. Encoding for Job Shop Problem ......................... 10
2.3. Neighborhood structure for Job Shop Problem ........... 14
Chapter 3 Methodology ...................................... 20
3.1. Problem Description ................................... 20
3.2. Mathematical Model .................................... 21
3.3. Variable neighborhood descent (VND) background ........ 22
3.4. Approach for the Job Shop Scheduling Problem .......... 25
3.4.1. Solution representation ............................. 26
3.4.2. Initial solution .................................... 26
3.4.3. New neighborhood structure .......................... 26
3.4.4. Shaking process ..................................... 29
3.4.5. Repair mechanism .................................... 29
3.4.6. Termination criterion ............................... 30
3.4.7. Proposed VND algorithm .............................. 31
Chapter 4 Computational results ............................ 34
4.1. Instance selection .................................... 34
4.2. Preliminary tests ..................................... 34
4.2.1. Parameter analysis .................................. 35
4.2.2. Comparison between VNDI and VNDII ................... 49
4.3. Computational results and discussions ................. 51
Chapter 5 Conclusions ...................................... 57
References ................................................. 58

Adams, J., Balas, E., and Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3), 391-401.
Aiex, R. M., Binato, S., and Resende, M. (2003). Parallel Grasp With Path-Relinking For Job Shop Scheduling (Vol. 29).
Akram, K., Kamal, K., and Zeb, A. (2016). Fast simulated annealing hybridized with quenching for solving job shop scheduling problem. Applied Soft Computing, 49, 510-523.
Applegate, D., and Cook, W. (1991). A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3(2), 149-156.
Asadzadeh, L. (2015). A local search genetic algorithm for the job shop scheduling problem with intelligent agents. Computers & Industrial Engineering, 85, 376-383.
Asadzadeh, L., and Zamanifar, K. (2010). An agent-based parallel approach for the job shop scheduling problem with genetic algorithms. Mathematical and Computer Modelling, 52(11), 1957-1965.
Aydin, M. E., and Fogarty, T. C. (2004). A distributed evolutionary simulated annealing algorithm for combinatorial optimisation problems. Journal of Heuristics, 10(3), 269-292.
Balas, E., and Vazacopoulos, A. (1998). Guided local search with shifting bottleneck for job shop scheduling. Management Science, 44(2), 262-275.
Blum, C., and Sampels, M. (2004). An ant colony optimization algorithm for shop scheduling problems. Journal of Mathematical Modelling and Algorithms, 3(3), 285-308.
Černý, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45(1), 41-51.
Cheung, W., and Zhou, H. (2001). Using genetic algorithms and heuristics for job shop scheduling with sequence-dependent setup times. Annals of Operations Research, 107(1), 65-81.
Dell'Amico, M., and Trubian, M. (1993). Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, 41, 231-252.
Della Croce, F., Tadei, R., and Volta, G. (1995). A genetic algorithm for the job shop problem. Computers & Operations Research, 22(1), 15-24.
Demirkol, E., Mehta, S., and Uzsoy, R. (1998). Benchmarks for shop scheduling problems. European Journal of Operational Research, 109(1), 137-141.
Fisher, H., and Thompson, G. L. (1963). Probabilistic learning combinations of local job-shop scheduling rules. Proceeding of the Industrial scheduling, Prentice-Hall, Engle- wood, Chichester, UK.
Gabel, T., and Riedmiller, M. (2007, 1-5 April 2007). Scaling adaptive agent-based reactive job-shop scheduling to large-scale problems. Proceeding of the 2007 IEEE Symposium on Computational Intelligence in Scheduling.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533-549.
Gonçalves, J. F., de Magalhães Mendes, J. J., and Resende, M. c. G. C. (2005). A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research, 167(1), 77-95.
Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. Oxford, England.
Kelley, J. J. E. (1961). Critical-path planning and scheduling: Mathematical basis. Operations Research, 9(3), 296-320.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
Kurdi, M. (2017). An improved island model memetic algorithm with a new cooperation phase for multi-objective job shop scheduling problem. Computers & Industrial Engineering, 111, 183-201.
Laarhoven, P. J. M. v., Aarts, E. H. L., and Lenstra, J. K. (1992). Job Shop Scheduling by Simulated Annealing. Operations Research, 40(1), 113-125.
Lawrence, S. (1984). Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (Supplement). Graduate School of Industrial Administration, Carnegie–Mellon University,
Matsuo, H., Juck Suh, C., and S. Sullivan, R. (1989). A controlled search simulated annealing method for the single machine weighted tardiness problem (Vol. 21).
Mladenović, N., and Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097-1100.
Naderi, B., Ghomi, S. M. T. F., and Aminnayeri, M. (2010). A high performing metaheuristic for job shop scheduling with sequence-dependent setup times. Applied Soft Computing, 10(3), 703-710.
Naderi, B., Zandieh, M., and Fatemi Ghomi, S. M. T. (2009). Scheduling job shop problems with sequence-dependent setup times. International Journal of Production Research, 47(21), 5959-5976.
Nowicki, E., and Smutnicki, C. (1996). A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, 42(6), 797-813.
Og˘uz, C., Sibel Salman, F., and Bilgintürk Yalçın, Z. (2010). Order acceptance and scheduling decisions in make-to-order systems. International Journal of Production Economics, 125(1), 200-211.
Ombuki, B. M., and Ventresca, M. (2004). Local search genetic algorithms for the job shop scheduling problem. Applied Intelligence, 21(1), 99-109.
Pezzella, F., and Merelli, E. (2000). A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, 120(2), 297-310.
Pezzella, F., Morganti, G., and Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research, 35(10), 3202-3212.
Pinedo, M. L. (2012). Scheduling Theory, Algorithms, and Systems (Fourth ed.).
Ponsich, A., and Coello, C. A. (2013). A hybrid Differential Evolution—Tabu Search algorithm for the solution of Job-Shop Scheduling Problems. Applied Soft Computing, 13(1), 462-474.
Roshanaei, V., Naderi, B., Jolai, F., and Khalili, M. (2009). A variable neighborhood search for job shop scheduling with set-up times to minimize makespan. Future Generation Computer Systems, 25(6), 654-661.
Roy, B., and Sussmann, B. (1964). Les problemes d’ ordon ordonnancement avec constraints disjunctives. Proceeding of the SEMA, Note D.S., Paris.
Sevkli, M., and Aydin, M. E. (2006). A Variable Neighbourhood Search Algorithm for Job Shop Scheduling Problems, Berlin, Heidelberg.
Shen, L. (2014). A tabu search algorithm for the job shop problem with sequence dependent setup times. Computers & Industrial Engineering, 78, 95-106.
Stevenson, W. J. (2012). Operations Management (11th ed.): Tim Vertovec.
Taillard, É. D. (1994). Parallel Taboo Search Techniques for the Job Shop Scheduling Problem. ORSA Journal on Computing, 6(2), 108-117.
Talbi, E.-G. (2009). Metaheuristics from design to implementation. Hoboken, New Jersey: John Wiley & Sons, Inc.
Yamada, T., and Nakano, R. (1992). A Genetic Algorithm Applicable to Large-Scale Job-Shop Problems (Vol. 2).
Zhang, C., Li, P., Guan, Z., and Rao, Y. (2007). A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research, 34(11), 3229-3242.
Zhou, Y., Li, B., and Yang, J. (2006). Study on job shop scheduling with sequence-dependent setup times using biological immune algorithm. The International Journal of Advanced Manufacturing Technology, 30(1), 105-111.