Spectrum management and resource allocation(RA)problems are challenging and critical in a vast number of research areas such as wireless communications and computer networks.The traditional approaches for solving such...Spectrum management and resource allocation(RA)problems are challenging and critical in a vast number of research areas such as wireless communications and computer networks.The traditional approaches for solving such problems usually consume time and memory,especially for large-size problems.Recently different machine learning approaches have been considered as potential promising techniques for combinatorial optimization problems,especially the generative model of the deep neural networks.In this work,we propose a resource allocation deep autoencoder network,as one of the promising generative models,for enabling spectrum sharing in underlay device-to-device(D2D)communication by solving linear sum assignment problems(LSAPs).Specifically,we investigate the performance of three different architectures for the conditional variational autoencoders(CVAE).The three proposed architecture are the convolutional neural network(CVAECNN)autoencoder,the feed-forward neural network(CVAE-FNN)autoencoder,and the hybrid(H-CVAE)autoencoder.The simulation results show that the proposed approach could be used as a replacement of the conventional RA techniques,such as the Hungarian algorithm,due to its ability to find solutions of LASPs of different sizes with high accuracy and very fast execution time.Moreover,the simulation results reveal that the accuracy of the proposed hybrid autoencoder architecture outperforms the other proposed architectures and the state-of-the-art DNN techniques.展开更多
A novel algorithm called Colony Location Algorithm (CLA) is proposed. It mimics the phenomena in biotic community that colonies of species could be located in the places most suitable to their growth. The factors work...A novel algorithm called Colony Location Algorithm (CLA) is proposed. It mimics the phenomena in biotic community that colonies of species could be located in the places most suitable to their growth. The factors working on the species location such as the nutrient of soil, resource competition between species, growth and decline process, and effect on environment were considered in CLA via the nutrient function, growth and decline rates, environment evaluation and fertilization strategy. CLA was applied to solve the classical assignment problems. The computation results show that CLA can achieve the optimal solution with higher possibility and shorter running time.展开更多
In order to overcome the shortcoming of the classical Hungarian algorithm that it can only solve the problems where the total cost is the sum of that of each job, an improved Hungarian algorithm is proposed and used t...In order to overcome the shortcoming of the classical Hungarian algorithm that it can only solve the problems where the total cost is the sum of that of each job, an improved Hungarian algorithm is proposed and used to solve the assignment problem of serial-parallel systems. First of all, by replacing parallel jobs with virtual jobs, the proposed algorithm converts the serial-parallel system into a pure serial system, where the classical Hungarian algorithm can be used to generate a temporal assignment plan via optimization. Afterwards, the assignment plan is validated by checking whether the virtual jobs can be realized by real jobs through local searching. If the assignment plan is not valid, the converted system will be adapted by adjusting the parameters of virtual jobs, and then be optimized again. Through iterative searching, the valid optimal assignment plan can eventually be obtained.To evaluate the proposed algorithm, the valid optimal assignment plan is applied to labor allocation of a manufacturing system which is a typical serial-parallel system.展开更多
Assignment of jobs to workers, contract to contractors undergoing a bidding process, assigning nurses to duty post, or time tabling for teachers in school and many more have become a growing concern to both management...Assignment of jobs to workers, contract to contractors undergoing a bidding process, assigning nurses to duty post, or time tabling for teachers in school and many more have become a growing concern to both management and sector leaders alike. Hungarian algorithm has been the most successful tool for solving such problems. The authors have proposed a heuristic method for solving assignment problems with less computing time in comparison with Hungarian algorithm that gives comparable results with an added advantage of easy implementation. The proposed heuristic method is used to compute some bench mark problems.展开更多
This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly genetic, meaning...This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly genetic, meaning that any decomposition method and different heuristics for the genetic operators can be considered. To validate the approach, the decomposition algorithm due to Newman was used and several crossover operators based on structural knowledge such as the cluster, separator and the cut were tested. The experimental results obtained on the most challenging Minimum Interference-FAP problems of CALMA instances are very promising and lead to interesting perspectives to be explored in the future.展开更多
Competition based neural networks have been used to solve the generalized assignment problem andthe quadratic assignment problem.Both problems are very difficult and are ε approximation complete.Theneural network app...Competition based neural networks have been used to solve the generalized assignment problem andthe quadratic assignment problem.Both problems are very difficult and are ε approximation complete.Theneural network approach has yielded highly competitive performance and good performance for thequadratic assignment problem.These neural networks are guaranteed to produce feasible solutions.展开更多
The dynamic weapon target assignment(DWTA)problem is of great significance in modern air combat.However,DWTA is a highly complex constrained multi-objective combinatorial optimization problem.An improved elitist non-d...The dynamic weapon target assignment(DWTA)problem is of great significance in modern air combat.However,DWTA is a highly complex constrained multi-objective combinatorial optimization problem.An improved elitist non-dominated sorting genetic algorithm-II(NSGA-II)called the non-dominated shuffled frog leaping algorithm(NSFLA)is proposed to maximize damage to enemy targets and minimize the self-threat in air combat constraints.In NSFLA,the shuffled frog leaping algorithm(SFLA)is introduced to NSGA-II to replace the inside evolutionary scheme of the genetic algorithm(GA),displaying low optimization speed and heterogeneous space search defects.Two improvements have also been raised to promote the internal optimization performance of SFLA.Firstly,the local evolution scheme,a novel crossover mechanism,ensures that each individual participates in updating instead of only the worst ones,which can expand the diversity of the population.Secondly,a discrete adaptive mutation algorithm based on the function change rate is applied to balance the global and local search.Finally,the scheme is verified in various air combat scenarios.The results show that the proposed NSFLA has apparent advantages in solution quality and efficiency,especially in many aircraft and the dynamic air combat environment.展开更多
This paper investigates the dynamical behaviour of network traffic flow. Assume that trip rates may be influenced by the level of service on the network and travellers are willing to take a faster route. A discrete dy...This paper investigates the dynamical behaviour of network traffic flow. Assume that trip rates may be influenced by the level of service on the network and travellers are willing to take a faster route. A discrete dynamical model for the day-to-day adjustment process of route choice is presented. The model is then applied to a simple network for analysing the day-to-day behaviours of network flow. It finds that equilibrium is arrived if network flow consists of travellers not very sensitive to the differences of travel cost. Oscillations and chaos of network traffic flow are also found when travellers are sensitive to the travel cost and travel demand in a simple network.展开更多
Traditional Hungarian method can only solve standard assignment problems, while can not solve competition assignment problems. This article emphatically discussed the difference between standard assignment problems an...Traditional Hungarian method can only solve standard assignment problems, while can not solve competition assignment problems. This article emphatically discussed the difference between standard assignment problems and competition assignment problems. The kinds of competition assignment problem algorithms based on Hungarian method and the solutions of them were studied.展开更多
A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet...A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity, and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a real- wofld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was ￥ 1 591276 one week and the running time was no more than 4 rain, which shows that the model and algorithm are fairly good for domestic airline.展开更多
In this paper, we address one of the issues in the frequency assignment problem for cellular mobile networks in which we intend to minimize the interference levels when assigning frequencies from a limited frequency s...In this paper, we address one of the issues in the frequency assignment problem for cellular mobile networks in which we intend to minimize the interference levels when assigning frequencies from a limited frequency spectrum. In order to satisfy the increasing demand in such cellular mobile networks, we use a hybrid approach consisting of a Particle Swarm Optimization(PSO) combined with a Tabu Search(TS) algorithm. This approach takes both advantages of PSO efficiency in global optimization and TS in avoiding the premature convergence that would lead PSO to stagnate in a local minimum. Moreover, we propose a new efficient, simple, and inexpensive model for storing and evaluating solution's assignment. The purpose of this model reduces the solution's storage volume as well as the computations required to evaluate thesesolutions in comparison with the classical model. Our simulation results on the most known benchmarking instances prove the effectiveness of our proposed algorithm in comparison with previous related works in terms of convergence rate, the number of iterations, the solution storage volume and the running time required to converge to the optimal solution.展开更多
Recently, Yadaiah and Haragopal published in the American Journal of Operations Research a new approach to solving the unbalanced assignment problem. They also provide a numerical example which they solve with their a...Recently, Yadaiah and Haragopal published in the American Journal of Operations Research a new approach to solving the unbalanced assignment problem. They also provide a numerical example which they solve with their approach and get a cost of 1550 which they claim is optimum. This approach might be of interest;however, their approach does not guarantee the optimal solution. In this short paper, we will show that solving this same example from the Yadaiah and Haragopal paper by using a simple textbook formulation to balance the problem and then solve it with the classic Hungarian method of Kuhn yields the true optimal solution with a cost of 1520.展开更多
Solving the absent assignment problem of the shortest time limit in a weighted bipartite graph with the minimal weighted k-matching algorithm is unsuitable for situations in which large numbers of problems need to be ...Solving the absent assignment problem of the shortest time limit in a weighted bipartite graph with the minimal weighted k-matching algorithm is unsuitable for situations in which large numbers of problems need to be addressed by large numbers of parties. This paper simplifies the algorithm of searching for the even alternating path that contains a maximal element using the minimal weighted k-matching theorem and intercept graph. A program for solving the maximal efficiency assignment problem was compiled. As a case study, the program was used to solve the assignment problem of water piping repair in the case of a large number of companies and broken pipes, and the validity of the program was verified.展开更多
Cell association is a significant research issue in future mobile communication systems due to the unacceptably large computational time of traditional schemes.This article proposes a polynomial-time cell association ...Cell association is a significant research issue in future mobile communication systems due to the unacceptably large computational time of traditional schemes.This article proposes a polynomial-time cell association scheme which not only completes the association in polynomial time but also fits for a generic optimization objective function.On the one hand,traditional cell association as a non-deterministic polynomial(NP)hard problem with a generic utility function is heuristically transformed into a 2-dimensional assignment optimization and solved by a certain polynomial-time algorithm,which significantly saves computational time.On the other hand,the scheme jointly considers utility maximization and load balancing among multiple base stations(BSs)by maintaining an experience pool storing a set of weighting factor values and their corresponding performances.When an association optimization is required,a suitable weighting factor value is taken from the pool to calculate a long square utility matrix and a certain polynomial-time algorithm will be applied for the association.Comparing with several representative schemes,the proposed scheme achieves large system capacity and high fairness within a relatively short computational time.展开更多
The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite co...The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.展开更多
A new troubleshooting algorithm for solving assignment problem based on existing algorithms is proposed, and an analysis on the related theory is given. By applying the new troubleshooting algorithm to the Lagrange re...A new troubleshooting algorithm for solving assignment problem based on existing algorithms is proposed, and an analysis on the related theory is given. By applying the new troubleshooting algorithm to the Lagrange relaxation algorithm of the multi-dimensional assignment problem of data association for multi-passive-sensor multi-target location systems, and comparing the simulation results with that of the Hungarian algorithm which is the classical optimal solving algorithm, and the multi-layer ordersearching algorithm which is a sub-optimal solving algorithm, the performance and applying conditions of the new algorithm are summarized. Theory analysis and simulation results prove the effectiveness and superiority of the new algorithm.展开更多
In this paper we carried out a probabilistic analysis for a machine repair system with a general service-time distribution by means of generalized Markov renewal processes. Some formulas for the steady-state performan...In this paper we carried out a probabilistic analysis for a machine repair system with a general service-time distribution by means of generalized Markov renewal processes. Some formulas for the steady-state performance measures. such as the distribution of queue sizes, average queue length, degree of repairman utilization and so on. are then derived. Finally, the machine repair model and a multiple critcria decision-making method are applied to study machine assignment problem with a general service-time distribution to determine the optimum number of machines being serviced by one repairman.展开更多
In this paper, we first consider the position restriction scheduling problems on a single machine. The problems have been solved in certain special cases, especially for those obtained by restricting the processing ti...In this paper, we first consider the position restriction scheduling problems on a single machine. The problems have been solved in certain special cases, especially for those obtained by restricting the processing time pj = 1. We introduce the bipartite matching algorithm to provide some polynomial-time algorithms to solve them. Then we further consider a problem on unrelated processors.展开更多
System reliability optimization problem of multi-source multi-sink flow network is defined by searching the optimal components that maximize the reliability and minimize the total assignment cost. Therefore, a genetic...System reliability optimization problem of multi-source multi-sink flow network is defined by searching the optimal components that maximize the reliability and minimize the total assignment cost. Therefore, a genetic-based approach is proposed to solve the components assignment problem under budget constraint. The mathematical model of the optimization problem is presented and solved by the proposed genetic-based approach. The proposed approach is based on determining the optimal set of lower boundary points that maximize the system reliability such that the total assignment cost does not exceed the specified budget. Finally, to evaluate our approach, we applied it to various network examples with different numbers of available components;two-source two-sink network and three-source two-sink network.展开更多
In this paper, we discuss a new approach for solving an unbalanced assignment problem. A Lexi-search algorithm is used to assign all the jobs to machines optimally. The results of new approach are compared with existi...In this paper, we discuss a new approach for solving an unbalanced assignment problem. A Lexi-search algorithm is used to assign all the jobs to machines optimally. The results of new approach are compared with existing approaches, and this approach outperforms other methods. Finally, numerical example (Table 1) has been given to show the efficiency of the proposed methodology.展开更多
基金supported in part by the China NSFC Grant 61872248Guangdong NSF 2017A030312008+1 种基金Fok Ying-Tong Education Foundation for Young Teachers in the Higher Education Institutions of China (Grant No.161064)GDUPS (2015)
文摘Spectrum management and resource allocation(RA)problems are challenging and critical in a vast number of research areas such as wireless communications and computer networks.The traditional approaches for solving such problems usually consume time and memory,especially for large-size problems.Recently different machine learning approaches have been considered as potential promising techniques for combinatorial optimization problems,especially the generative model of the deep neural networks.In this work,we propose a resource allocation deep autoencoder network,as one of the promising generative models,for enabling spectrum sharing in underlay device-to-device(D2D)communication by solving linear sum assignment problems(LSAPs).Specifically,we investigate the performance of three different architectures for the conditional variational autoencoders(CVAE).The three proposed architecture are the convolutional neural network(CVAECNN)autoencoder,the feed-forward neural network(CVAE-FNN)autoencoder,and the hybrid(H-CVAE)autoencoder.The simulation results show that the proposed approach could be used as a replacement of the conventional RA techniques,such as the Hungarian algorithm,due to its ability to find solutions of LASPs of different sizes with high accuracy and very fast execution time.Moreover,the simulation results reveal that the accuracy of the proposed hybrid autoencoder architecture outperforms the other proposed architectures and the state-of-the-art DNN techniques.
基金This work was supported by the National Natural Science Foundation of China (No. 70171056)the Key Lab Foundation of Education Ministry,Santou University, China
文摘A novel algorithm called Colony Location Algorithm (CLA) is proposed. It mimics the phenomena in biotic community that colonies of species could be located in the places most suitable to their growth. The factors working on the species location such as the nutrient of soil, resource competition between species, growth and decline process, and effect on environment were considered in CLA via the nutrient function, growth and decline rates, environment evaluation and fertilization strategy. CLA was applied to solve the classical assignment problems. The computation results show that CLA can achieve the optimal solution with higher possibility and shorter running time.
文摘In order to overcome the shortcoming of the classical Hungarian algorithm that it can only solve the problems where the total cost is the sum of that of each job, an improved Hungarian algorithm is proposed and used to solve the assignment problem of serial-parallel systems. First of all, by replacing parallel jobs with virtual jobs, the proposed algorithm converts the serial-parallel system into a pure serial system, where the classical Hungarian algorithm can be used to generate a temporal assignment plan via optimization. Afterwards, the assignment plan is validated by checking whether the virtual jobs can be realized by real jobs through local searching. If the assignment plan is not valid, the converted system will be adapted by adjusting the parameters of virtual jobs, and then be optimized again. Through iterative searching, the valid optimal assignment plan can eventually be obtained.To evaluate the proposed algorithm, the valid optimal assignment plan is applied to labor allocation of a manufacturing system which is a typical serial-parallel system.
文摘Assignment of jobs to workers, contract to contractors undergoing a bidding process, assigning nurses to duty post, or time tabling for teachers in school and many more have become a growing concern to both management and sector leaders alike. Hungarian algorithm has been the most successful tool for solving such problems. The authors have proposed a heuristic method for solving assignment problems with less computing time in comparison with Hungarian algorithm that gives comparable results with an added advantage of easy implementation. The proposed heuristic method is used to compute some bench mark problems.
文摘This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly genetic, meaning that any decomposition method and different heuristics for the genetic operators can be considered. To validate the approach, the decomposition algorithm due to Newman was used and several crossover operators based on structural knowledge such as the cluster, separator and the cut were tested. The experimental results obtained on the most challenging Minimum Interference-FAP problems of CALMA instances are very promising and lead to interesting perspectives to be explored in the future.
文摘Competition based neural networks have been used to solve the generalized assignment problem andthe quadratic assignment problem.Both problems are very difficult and are ε approximation complete.Theneural network approach has yielded highly competitive performance and good performance for thequadratic assignment problem.These neural networks are guaranteed to produce feasible solutions.
基金supported by the National Natural Science Foundation of China(61673209,71971115)。
文摘The dynamic weapon target assignment(DWTA)problem is of great significance in modern air combat.However,DWTA is a highly complex constrained multi-objective combinatorial optimization problem.An improved elitist non-dominated sorting genetic algorithm-II(NSGA-II)called the non-dominated shuffled frog leaping algorithm(NSFLA)is proposed to maximize damage to enemy targets and minimize the self-threat in air combat constraints.In NSFLA,the shuffled frog leaping algorithm(SFLA)is introduced to NSGA-II to replace the inside evolutionary scheme of the genetic algorithm(GA),displaying low optimization speed and heterogeneous space search defects.Two improvements have also been raised to promote the internal optimization performance of SFLA.Firstly,the local evolution scheme,a novel crossover mechanism,ensures that each individual participates in updating instead of only the worst ones,which can expand the diversity of the population.Secondly,a discrete adaptive mutation algorithm based on the function change rate is applied to balance the global and local search.Finally,the scheme is verified in various air combat scenarios.The results show that the proposed NSFLA has apparent advantages in solution quality and efficiency,especially in many aircraft and the dynamic air combat environment.
文摘This paper investigates the dynamical behaviour of network traffic flow. Assume that trip rates may be influenced by the level of service on the network and travellers are willing to take a faster route. A discrete dynamical model for the day-to-day adjustment process of route choice is presented. The model is then applied to a simple network for analysing the day-to-day behaviours of network flow. It finds that equilibrium is arrived if network flow consists of travellers not very sensitive to the differences of travel cost. Oscillations and chaos of network traffic flow are also found when travellers are sensitive to the travel cost and travel demand in a simple network.
文摘Traditional Hungarian method can only solve standard assignment problems, while can not solve competition assignment problems. This article emphatically discussed the difference between standard assignment problems and competition assignment problems. The kinds of competition assignment problem algorithms based on Hungarian method and the solutions of them were studied.
基金The National Natural Science Foundationof China (70473037)
文摘A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity, and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a real- wofld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was ￥ 1 591276 one week and the running time was no more than 4 rain, which shows that the model and algorithm are fairly good for domestic airline.
文摘In this paper, we address one of the issues in the frequency assignment problem for cellular mobile networks in which we intend to minimize the interference levels when assigning frequencies from a limited frequency spectrum. In order to satisfy the increasing demand in such cellular mobile networks, we use a hybrid approach consisting of a Particle Swarm Optimization(PSO) combined with a Tabu Search(TS) algorithm. This approach takes both advantages of PSO efficiency in global optimization and TS in avoiding the premature convergence that would lead PSO to stagnate in a local minimum. Moreover, we propose a new efficient, simple, and inexpensive model for storing and evaluating solution's assignment. The purpose of this model reduces the solution's storage volume as well as the computations required to evaluate thesesolutions in comparison with the classical model. Our simulation results on the most known benchmarking instances prove the effectiveness of our proposed algorithm in comparison with previous related works in terms of convergence rate, the number of iterations, the solution storage volume and the running time required to converge to the optimal solution.
文摘Recently, Yadaiah and Haragopal published in the American Journal of Operations Research a new approach to solving the unbalanced assignment problem. They also provide a numerical example which they solve with their approach and get a cost of 1550 which they claim is optimum. This approach might be of interest;however, their approach does not guarantee the optimal solution. In this short paper, we will show that solving this same example from the Yadaiah and Haragopal paper by using a simple textbook formulation to balance the problem and then solve it with the classic Hungarian method of Kuhn yields the true optimal solution with a cost of 1520.
文摘Solving the absent assignment problem of the shortest time limit in a weighted bipartite graph with the minimal weighted k-matching algorithm is unsuitable for situations in which large numbers of problems need to be addressed by large numbers of parties. This paper simplifies the algorithm of searching for the even alternating path that contains a maximal element using the minimal weighted k-matching theorem and intercept graph. A program for solving the maximal efficiency assignment problem was compiled. As a case study, the program was used to solve the assignment problem of water piping repair in the case of a large number of companies and broken pipes, and the validity of the program was verified.
基金the results of the research project funded by the National Natural Science Foundation of China under Grant No.61971176in part by the Applied Basic Research Program of Wuhan City under grand 2017010201010117。
文摘Cell association is a significant research issue in future mobile communication systems due to the unacceptably large computational time of traditional schemes.This article proposes a polynomial-time cell association scheme which not only completes the association in polynomial time but also fits for a generic optimization objective function.On the one hand,traditional cell association as a non-deterministic polynomial(NP)hard problem with a generic utility function is heuristically transformed into a 2-dimensional assignment optimization and solved by a certain polynomial-time algorithm,which significantly saves computational time.On the other hand,the scheme jointly considers utility maximization and load balancing among multiple base stations(BSs)by maintaining an experience pool storing a set of weighting factor values and their corresponding performances.When an association optimization is required,a suitable weighting factor value is taken from the pool to calculate a long square utility matrix and a certain polynomial-time algorithm will be applied for the association.Comparing with several representative schemes,the proposed scheme achieves large system capacity and high fairness within a relatively short computational time.
基金supported by the National Natural Science Foundation of China(71401106)the Innovation Program of Shanghai Municipal Education Commission(14YZ090)+4 种基金the Shanghai Natural Science Foundation(14ZR1418700)the Shanghai First-class Academic Discipline Project(S1201YLXK)the Hujiang Foundation of China(A14006)the grant S2009/esp-1594 from the Comunidad de Madrid(Spain)the grant MTM2012-36163-C06-06 from the Spanish government
文摘The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.
基金supported by the National Natural Science Foundation of China(61170161)the Natural Science Foundation of S handong (ZR2009GM002)the Technology Projects of Shandong University (J09LG01)
文摘A new troubleshooting algorithm for solving assignment problem based on existing algorithms is proposed, and an analysis on the related theory is given. By applying the new troubleshooting algorithm to the Lagrange relaxation algorithm of the multi-dimensional assignment problem of data association for multi-passive-sensor multi-target location systems, and comparing the simulation results with that of the Hungarian algorithm which is the classical optimal solving algorithm, and the multi-layer ordersearching algorithm which is a sub-optimal solving algorithm, the performance and applying conditions of the new algorithm are summarized. Theory analysis and simulation results prove the effectiveness and superiority of the new algorithm.
文摘In this paper we carried out a probabilistic analysis for a machine repair system with a general service-time distribution by means of generalized Markov renewal processes. Some formulas for the steady-state performance measures. such as the distribution of queue sizes, average queue length, degree of repairman utilization and so on. are then derived. Finally, the machine repair model and a multiple critcria decision-making method are applied to study machine assignment problem with a general service-time distribution to determine the optimum number of machines being serviced by one repairman.
文摘In this paper, we first consider the position restriction scheduling problems on a single machine. The problems have been solved in certain special cases, especially for those obtained by restricting the processing time pj = 1. We introduce the bipartite matching algorithm to provide some polynomial-time algorithms to solve them. Then we further consider a problem on unrelated processors.
文摘System reliability optimization problem of multi-source multi-sink flow network is defined by searching the optimal components that maximize the reliability and minimize the total assignment cost. Therefore, a genetic-based approach is proposed to solve the components assignment problem under budget constraint. The mathematical model of the optimization problem is presented and solved by the proposed genetic-based approach. The proposed approach is based on determining the optimal set of lower boundary points that maximize the system reliability such that the total assignment cost does not exceed the specified budget. Finally, to evaluate our approach, we applied it to various network examples with different numbers of available components;two-source two-sink network and three-source two-sink network.
文摘In this paper, we discuss a new approach for solving an unbalanced assignment problem. A Lexi-search algorithm is used to assign all the jobs to machines optimally. The results of new approach are compared with existing approaches, and this approach outperforms other methods. Finally, numerical example (Table 1) has been given to show the efficiency of the proposed methodology.
