基于新的动态邻域算法的车间调度问题的研究
|
摘要
作业加工调度问题是NP难的,被认为是最难的组合优化问题之一。在解决工业生产、经济管理和网络通讯等诸多问题时,都要涉及求解这个问题。优质、快速地求解作业加工调度问题,既有重要的理论意义,又能带来巨大的经济效益。
转换瓶颈算法是解决作业加工调度问题的最有效的算法之一,本论文中用转换瓶颈算法来产生问题的初始值,进而提高搜索效率。动态邻域算法的基本思想是利用两个主要工具"shake(振动)”和"local search(局部搜索)”,局部搜索用于探索一个更为优的结果,振动使局部最小跳入它的下一个邻域,从而继续进行局部搜索。本论文是依据这个基本思想研究和分析并进行改进,提出一个新的算法。
为了提高振动的效率,本文根据卡里尔定理和格拉博夫斯基定理提出了六个推论,以避免无用的局部邻域结构的切换,并且提出了新的邻域结构,即：“向前插入”,“向后插入”,“直接交换”。同时把振动分为“正常振动”和“贪婪振动”。实验表明基于六个推论,振动更加有驱动力。基于新的邻域结构,可以找到更好的某个点的邻域最小值。
The job shop scheduling problem is not only NP hard problem, but also regarded as one of the most difficult combinatorial optimization problems as well. It is well known that the problems in those fields of industrial production, economic management, network communication and cryptography etc. make direct appeal to this problem. Therefore, solving the job shop scheduling problem efficiently and effectively will make a great of economic benefits. Job shop scheduling problem is well known to be a difficult, strongly NP—complete problem, the objective of this is minimizing the completion time of all the jobs, called the make span, subject to the constraints of this kind of problem.
The Shifting Bottleneck Procedure (SBP) proposed by Adams, Balas& Zawack is an effective heuristic method for solving the job shop scheduling problem. In my research, the SBP will be using to generate the initial solution. Our purpose is to cut down the executing time. Variable Neighborhood Search is a recent meta-heuristic for solving combinatorial and global optimization problems. Its basic idea is the systematic change of neighborhood within the local search. In an ordinary VNS algorithm two main functions'shake'and'local search'play an important role. Local search explores for an improved solution within the local neighborhood, while shake diversifies the solution by switching to another local neighborhood. In the related study, resultant effectiveness and computational efficiency still remain challenging task.
In this thesis, in order to improve the efficiency of shake function we proposed 6 propositions to avoid useless neighborhood structures in Exchange, Forward-Insert, Backward-Insert, moreover divide the shake function to normal shake and intensified shake. In the experiments, it is showed that based on the above 6 propositions, the shake function is more driving when trapped in the local optimum. In our experiment, if the random solution was adopted, it is always taking more time while obtain a same final result.
转换瓶颈算法是解决作业加工调度问题的最有效的算法之一,本论文中用转换瓶颈算法来产生问题的初始值,进而提高搜索效率。动态邻域算法的基本思想是利用两个主要工具"shake(振动)”和"local search(局部搜索)”,局部搜索用于探索一个更为优的结果,振动使局部最小跳入它的下一个邻域,从而继续进行局部搜索。本论文是依据这个基本思想研究和分析并进行改进,提出一个新的算法。
为了提高振动的效率,本文根据卡里尔定理和格拉博夫斯基定理提出了六个推论,以避免无用的局部邻域结构的切换,并且提出了新的邻域结构,即：“向前插入”,“向后插入”,“直接交换”。同时把振动分为“正常振动”和“贪婪振动”。实验表明基于六个推论,振动更加有驱动力。基于新的邻域结构,可以找到更好的某个点的邻域最小值。
The job shop scheduling problem is not only NP hard problem, but also regarded as one of the most difficult combinatorial optimization problems as well. It is well known that the problems in those fields of industrial production, economic management, network communication and cryptography etc. make direct appeal to this problem. Therefore, solving the job shop scheduling problem efficiently and effectively will make a great of economic benefits. Job shop scheduling problem is well known to be a difficult, strongly NP—complete problem, the objective of this is minimizing the completion time of all the jobs, called the make span, subject to the constraints of this kind of problem.
The Shifting Bottleneck Procedure (SBP) proposed by Adams, Balas& Zawack is an effective heuristic method for solving the job shop scheduling problem. In my research, the SBP will be using to generate the initial solution. Our purpose is to cut down the executing time. Variable Neighborhood Search is a recent meta-heuristic for solving combinatorial and global optimization problems. Its basic idea is the systematic change of neighborhood within the local search. In an ordinary VNS algorithm two main functions'shake'and'local search'play an important role. Local search explores for an improved solution within the local neighborhood, while shake diversifies the solution by switching to another local neighborhood. In the related study, resultant effectiveness and computational efficiency still remain challenging task.
In this thesis, in order to improve the efficiency of shake function we proposed 6 propositions to avoid useless neighborhood structures in Exchange, Forward-Insert, Backward-Insert, moreover divide the shake function to normal shake and intensified shake. In the experiments, it is showed that based on the above 6 propositions, the shake function is more driving when trapped in the local optimum. In our experiment, if the random solution was adopted, it is always taking more time while obtain a same final result.
引文
[1]A.S. Jain, S. Meeran, Deterministic job-shop scheduling:Past, present and future, European Journal of Operational Research,113 (1999), pp.390-434.
[2]J.Adams, E.Balas, and D. Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science,34(1988), pp.391-401
[3]Yajie Lou, An Efficient Decomposition Approach for Production Scheduling Problems Focused on the Longest Active Chain, (2007)
[4]F.Glover and M.Laguna, Tabu Search, Kluwer Academic Publishers,Boston, 1997
[5]D. SUN, Scheduling Larger Job Shops:a Decomposition Approach, International Journal of Operation Research, Vol.34, No.7(1996), pp.2019-2033.
[6]Kenneth R. Baker, Introduction to Sequencing and Scheduling, John Wiley, New York,1974.
[7]Jacques Carlier, The one-machine sequencing problem, European Journal of Operational Research 11(1982),pp.42-47
[8]Taillard, E., Benchmarks for Basic Scheduling Problems, European Journal of Operation Research,64 (1993),278-285.
[9]Ferdinando Pezzella and Emanuela Merelli, A tabu search method guided by shifting bottleneck for the job shop scheduling problem (2000)
[10]OR-Library, http://people.brunel.ac.uk/-mastjjb/jeb/info.html
[11]Egon Balas, Alkis Vazacopoulos, Guided Local Search with Shifting Bottleneck for Job Shop Scheduling, Management Science, Vol.44, No.2, pp.262-275
[12]Mehmet Sevkli and M.Emin Aydin, Variable Neighborhood Search for Job Shop Scheduling Problems, Journal Of Software, VOL.1,NO 2
[13]Cheng, R., Gen, M., and Tsujimura, Y.:A Tutorial Survey of Job Shop Scheduling Problems Using genetic Algorithms-I. Representation. Journal of Computers and Industrial Engineering 30(4) (1996) 983-997.
[14]Dell'Amico, M., and Trubian, M.:Applying Tabu-Search to the Job-Shop Scheduling Problem. Annals of Operations Research 4 (1993) 231-252.
[15]Huang, W., and Yin, A.:An Improved Shifting Bottleneck Procedure for the Job Shop Scheduling Problem. Computers& Operations Research 31 (2004) 2093-2110.
[16]Mladenovic, N., and Hansen, P.:Variable Neighbourhood Search. Computers and Operations Research 24 (1997) 1097-1100.
[17]Alba, E., and Tomassini, M., (2002),:Parallelism and evolutionary algorithms, IEEE Transactions on Evolutionary Computation,6(5) (2002), 443-462.
[18]Fleszar, K. and Hindi, K. S.:New heuristics for one-dimensional bin-packing. Computers& Operations Research,29 (7), (2002),821-839.
[19]M.D.Davis and E J. Weyuker. Computability,Complixity,and Languages: Fundamentals of Theoretical Computer Science. INC:Academic Press,1983
[20]Aiex, R. M., Binato, S., and Resende, M. G. C.:Parallel GRASP with Path-Relinking for Job Shop Scheduling. Parallel Computing 29 (2003) 393-430.
[21]Applegate, D., and Cook, W.:A Computational Study of Job-Shop Scheduling. ORSA Journal on Computing 3(2) (1991) 149-156.
[22]Aydin, M. E., and Fogarty, T. C.:A Distributed Evolutionary Simulated Annealing Algorithm for Combinatorial Optimisation Problems. Journal of Heuristics 10 (2004) 269-292.
[23]Beasley, J.E. "Obtaining Test Problems via Internet." Journal of Global Optimisation 8,429-433, http://people.brunel.ac.uk/-mastjjb/jeb/info.html.
[24]Bierwith, C.:A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms. OR Spektrum 17 (1995) 87-92.
[25]Blum, C., and Sampels, M.:An Ant Colony Optimization Algorithm for Shop Scheduling Problems. Journal of Mathematical Modelling and Algorithms 3 (2004) 285-308.
[26]Crainic, T. G., Gendreau, M.,Hansen, P.,Mladenovic, N.:Cooperative Parallel Variable Neighborhood Search for thep-Median 10 (2004) 293-314
[27]Carlier, J., and Pison, E.:An Algorithm for Solving the Job-Shop Problem, Management Science 35 (1989) 164-176.
[28]Cheng, R., Gen, M., and Tsujimura, Y.:A Tutorial Survey of Job Shop Scheduling Problems Using genetic Algorithms-I. Representation. Journal of Computers and Industrial Engineering 30(4) (1996) 983-997.
[29]Colorni, A., Dorigo, M., Maniezzo, V., and Trubian, M.:Ant System for Job-Shop Scheduling. Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL) 34(1) (1994) 39-53.
[30]Dorndorf, U., and Pesch, E.:Evolution Based Learning in a Job Shop Scheduling Environment, Computers& Operations Research 22 (1995) June 26,20050:30 International Journal of Production Research "A hybrid PSO for the JSSP"
[31]Dorndorf, U., Pesch, E., and Phan-Huy, T.:Constraint Propagation and Problem Decomposition:A Preprocessing Procedure for the Job Shop Problem, Annals of Operations Research 115 (2002) 125-145.
[32]Garcia-Lopez, F., Melian-Batista, B., Moreno-Perez, J.A. and Moreno-Vega, M.:The parallel variable neighbourhood Search for the p-Median Problem 8 (2002)375-388
[33]Garey, M. Johnson, D., and Sethy, R.:The Complexity of Flow Shop and Job Shop Scheduling. Mathematics of Operations Research 1 (1976) 117-129.
[34]Goncalves, J. F., Mendes, J. M., and Resende, M.:A hybrid genetic algorithm for the job shop scheduling problem, European Journal of Operations Research 167(1) (2004) 77-95.
[35]Huang, W., and Yin, A.:An Improved Shifting Bottleneck Procedure for the Job Shop Scheduling Problem. Computers& Operations Research 31 (2004) 2093-2110.
[36]Jain, A., and Meeran, S.:Deterministic Job-Shop Scheduling:Past, Present and Future. European Journal of Operational Research.113:(1999) 390-434.
[37]Kolonko, M.:Some New Results on Simulated Annealing Applied to the Job Shop Scheduling Problem. European Journal of Operational Research 113, (1999) 123-136.
[38]Mladenovic, N., and Hansen, P.:Variable Neighborhood Search. Computers and Operations Research 24 (1997) 1097-1100.
[2]J.Adams, E.Balas, and D. Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science,34(1988), pp.391-401
[3]Yajie Lou, An Efficient Decomposition Approach for Production Scheduling Problems Focused on the Longest Active Chain, (2007)
[4]F.Glover and M.Laguna, Tabu Search, Kluwer Academic Publishers,Boston, 1997
[5]D. SUN, Scheduling Larger Job Shops:a Decomposition Approach, International Journal of Operation Research, Vol.34, No.7(1996), pp.2019-2033.
[6]Kenneth R. Baker, Introduction to Sequencing and Scheduling, John Wiley, New York,1974.
[7]Jacques Carlier, The one-machine sequencing problem, European Journal of Operational Research 11(1982),pp.42-47
[8]Taillard, E., Benchmarks for Basic Scheduling Problems, European Journal of Operation Research,64 (1993),278-285.
[9]Ferdinando Pezzella and Emanuela Merelli, A tabu search method guided by shifting bottleneck for the job shop scheduling problem (2000)
[10]OR-Library, http://people.brunel.ac.uk/-mastjjb/jeb/info.html
[11]Egon Balas, Alkis Vazacopoulos, Guided Local Search with Shifting Bottleneck for Job Shop Scheduling, Management Science, Vol.44, No.2, pp.262-275
[12]Mehmet Sevkli and M.Emin Aydin, Variable Neighborhood Search for Job Shop Scheduling Problems, Journal Of Software, VOL.1,NO 2
[13]Cheng, R., Gen, M., and Tsujimura, Y.:A Tutorial Survey of Job Shop Scheduling Problems Using genetic Algorithms-I. Representation. Journal of Computers and Industrial Engineering 30(4) (1996) 983-997.
[14]Dell'Amico, M., and Trubian, M.:Applying Tabu-Search to the Job-Shop Scheduling Problem. Annals of Operations Research 4 (1993) 231-252.
[15]Huang, W., and Yin, A.:An Improved Shifting Bottleneck Procedure for the Job Shop Scheduling Problem. Computers& Operations Research 31 (2004) 2093-2110.
[16]Mladenovic, N., and Hansen, P.:Variable Neighbourhood Search. Computers and Operations Research 24 (1997) 1097-1100.
[17]Alba, E., and Tomassini, M., (2002),:Parallelism and evolutionary algorithms, IEEE Transactions on Evolutionary Computation,6(5) (2002), 443-462.
[18]Fleszar, K. and Hindi, K. S.:New heuristics for one-dimensional bin-packing. Computers& Operations Research,29 (7), (2002),821-839.
[19]M.D.Davis and E J. Weyuker. Computability,Complixity,and Languages: Fundamentals of Theoretical Computer Science. INC:Academic Press,1983
[20]Aiex, R. M., Binato, S., and Resende, M. G. C.:Parallel GRASP with Path-Relinking for Job Shop Scheduling. Parallel Computing 29 (2003) 393-430.
[21]Applegate, D., and Cook, W.:A Computational Study of Job-Shop Scheduling. ORSA Journal on Computing 3(2) (1991) 149-156.
[22]Aydin, M. E., and Fogarty, T. C.:A Distributed Evolutionary Simulated Annealing Algorithm for Combinatorial Optimisation Problems. Journal of Heuristics 10 (2004) 269-292.
[23]Beasley, J.E. "Obtaining Test Problems via Internet." Journal of Global Optimisation 8,429-433, http://people.brunel.ac.uk/-mastjjb/jeb/info.html.
[24]Bierwith, C.:A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms. OR Spektrum 17 (1995) 87-92.
[25]Blum, C., and Sampels, M.:An Ant Colony Optimization Algorithm for Shop Scheduling Problems. Journal of Mathematical Modelling and Algorithms 3 (2004) 285-308.
[26]Crainic, T. G., Gendreau, M.,Hansen, P.,Mladenovic, N.:Cooperative Parallel Variable Neighborhood Search for thep-Median 10 (2004) 293-314
[27]Carlier, J., and Pison, E.:An Algorithm for Solving the Job-Shop Problem, Management Science 35 (1989) 164-176.
[28]Cheng, R., Gen, M., and Tsujimura, Y.:A Tutorial Survey of Job Shop Scheduling Problems Using genetic Algorithms-I. Representation. Journal of Computers and Industrial Engineering 30(4) (1996) 983-997.
[29]Colorni, A., Dorigo, M., Maniezzo, V., and Trubian, M.:Ant System for Job-Shop Scheduling. Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL) 34(1) (1994) 39-53.
[30]Dorndorf, U., and Pesch, E.:Evolution Based Learning in a Job Shop Scheduling Environment, Computers& Operations Research 22 (1995) June 26,20050:30 International Journal of Production Research "A hybrid PSO for the JSSP"
[31]Dorndorf, U., Pesch, E., and Phan-Huy, T.:Constraint Propagation and Problem Decomposition:A Preprocessing Procedure for the Job Shop Problem, Annals of Operations Research 115 (2002) 125-145.
[32]Garcia-Lopez, F., Melian-Batista, B., Moreno-Perez, J.A. and Moreno-Vega, M.:The parallel variable neighbourhood Search for the p-Median Problem 8 (2002)375-388
[33]Garey, M. Johnson, D., and Sethy, R.:The Complexity of Flow Shop and Job Shop Scheduling. Mathematics of Operations Research 1 (1976) 117-129.
[34]Goncalves, J. F., Mendes, J. M., and Resende, M.:A hybrid genetic algorithm for the job shop scheduling problem, European Journal of Operations Research 167(1) (2004) 77-95.
[35]Huang, W., and Yin, A.:An Improved Shifting Bottleneck Procedure for the Job Shop Scheduling Problem. Computers& Operations Research 31 (2004) 2093-2110.
[36]Jain, A., and Meeran, S.:Deterministic Job-Shop Scheduling:Past, Present and Future. European Journal of Operational Research.113:(1999) 390-434.
[37]Kolonko, M.:Some New Results on Simulated Annealing Applied to the Job Shop Scheduling Problem. European Journal of Operational Research 113, (1999) 123-136.
[38]Mladenovic, N., and Hansen, P.:Variable Neighborhood Search. Computers and Operations Research 24 (1997) 1097-1100.