To diagnose the feasibility of the solution of a job-shop scheduling problem（JSSP）,a test algorithm based on diagraph and heuristic search is developed and verified through a case study.Meanwhile,a new repair algori...To diagnose the feasibility of the solution of a job-shop scheduling problem（JSSP）,a test algorithm based on diagraph and heuristic search is developed and verified through a case study.Meanwhile,a new repair algorithm for modifying an infeasible solution of the JSSP to become a feasible solution is proposed for the general JSSP.The computational complexity of the test algorithm and the repair algorithm is both O（n） under the worst-case scenario,and O（2J＋M） for the repair algorithm under the best-case scenario.The repair algorithm is not limited to specific optimization methods,such as local tabu search,genetic algorithms and shifting bottleneck procedures for job shop scheduling,but applicable to generic infeasible solutions for the JSSP to achieve feasibility.展开更多
A multipath source self repair routing (MSSRR) algorithm for mobile ad hoc networks is proposed. By using multiple paths which can be repaired by themselves to transmit packets alternately, the network's load is b...A multipath source self repair routing (MSSRR) algorithm for mobile ad hoc networks is proposed. By using multiple paths which can be repaired by themselves to transmit packets alternately, the network's load is balanced, the link state in the network can be checked in time, the number of the times the route discovery mechanism starts is decreased. If only one route which will be broken can be used to transmit the packets, the route discovery mechanism is restarted.The algorithm is implemented on the basis of dynamic source routing (DSR). The effect of MSSRR on lifetime of the access from the source to the destination and the overhead is discussed. Compared with the performance of DSR,it can be seen that the algorithm can improve the performance of the network obviously and the overhead almost does not increase if the average hop count is larger.展开更多
Based on the uncertainty theory, this paper is devoted to the redundancy allocation problem in repairable parallel-series systems with uncertain factors, where the failure rate, repair rate and other relative coeffici...Based on the uncertainty theory, this paper is devoted to the redundancy allocation problem in repairable parallel-series systems with uncertain factors, where the failure rate, repair rate and other relative coefficients involved are considered as uncertain variables. The availability of the system and the corresponding designing cost are considered as two optimization objectives. A crisp multiobjective optimization formulation is presented on the basis of uncertainty theory to solve this resultant problem. For solving this problem efficiently, a new multiobjective artificial bee colony algorithm is proposed to search the Pareto efficient set, which introduces rank value and crowding distance in the greedy selection strategy, applies fast non-dominated sort procedure in the exploitation search and inserts tournament selection in the onlooker bee phase. It shows that the proposed algorithm outperforms NSGA-II greatly and can solve multiobjective redundancy allocation problem efficiently. Finally, a numerical example is provided to illustrate this approach.展开更多
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.展开更多
The dynamic capacitated location allocation problem in the military supportive network（DCLAP-MSN） is a representative of combinative optimization problems,and its optimization process is complicated.For this reason,...The dynamic capacitated location allocation problem in the military supportive network（DCLAP-MSN） is a representative of combinative optimization problems,and its optimization process is complicated.For this reason,a dynamic capacitated location allocation model is provided firstly.Then,a hybrid heuristic algorithm which combines genetic algorithm,repair algorithm of solutions and greedy search,is proposed as the solving method.The optimization performance is improved by effectively integrating the repair algorithm of solutions and greedy search with genetic optimization.The experiment results indicate that the proposed algorithm is a feasible and effective method for the problem.展开更多
A new reliability allocation model has been built for engine system, which is a repairable system, and consists of a large number of mechanical components. The cost and reliability are taken as objective function and ...A new reliability allocation model has been built for engine system, which is a repairable system, and consists of a large number of mechanical components. The cost and reliability are taken as objective function and constraint condition respectively. The parameters of components lifetime distribution are given as decision variables, and the component lifetimes are assumed to follow that Weibull distribution. The allocation is separated into two steps to reduce calculated amount of one allocation. Genetic algorithm and Monte Carlo method are applied to solve distribution parameters and system cost separately.展开更多
In the face of harsh natural environment applications such as earth-orbiting and deep space satellites, underwater sea vehicles, strong electromagnetic interference and temperature stress,the circuits faults appear ea...In the face of harsh natural environment applications such as earth-orbiting and deep space satellites, underwater sea vehicles, strong electromagnetic interference and temperature stress,the circuits faults appear easily. Circuit faults will inevitably lead to serious losses of availability or impeded mission success without self-repair over the mission duration. Traditional fault-repair methods based on redundant fault-tolerant technique are straightforward to implement, yet their area, power and weight cost can be excessive. Moreover they utilize all plug-in or component level circuits to realize redundant backup, such that their applicability is limited. Hence, a novel selfrepair technology based on evolvable hardware（EHW） and reparation balance technology（RBT） is proposed. Its cost is low, and fault self-repair of various circuits and devices can be realized through dynamic configuration. Making full use of the fault signals, correcting circuit can be found through EHW technique to realize the balance and compensation of the fault output-signals. In this paper, the self-repair model was analyzed which based on EHW and RBT technique, the specific self-repair strategy was studied, the corresponding self-repair circuit fault system was designed, and the typical faults were simulated and analyzed which combined with the actual electronic devices. Simulation results demonstrated that the proposed fault self-repair strategy was feasible. Compared to traditional techniques, fault self-repair based on EHW consumes fewer hardware resources, and the scope of fault self-repair was expanded significantly.展开更多
This paper presents a new hybrid genetic algorithm for the vertex cover problems in which scan-repair and local improvement techniques are used for local optimization. With the hybrid approach, genetic algorithms are ...This paper presents a new hybrid genetic algorithm for the vertex cover problems in which scan-repair and local improvement techniques are used for local optimization. With the hybrid approach, genetic algorithms are used to perform global exploration in a population, while neighborhood search methods are used to perform local exploitation around the chromosomes. The experimental results indicate that hybrid genetic algorithms can obtain solutions of excellent quality to the problem instances with different sizes. The pure genetic algorithms are outperformed by the neighborhood search heuristics procedures combined with genetic algorithms.展开更多
During the war,equipment is constantly being damaged with limited battlefield rush-repair time and power.Therefore,some military problems are presented in this paper.In order to get more fighting time for damaged equi...During the war,equipment is constantly being damaged with limited battlefield rush-repair time and power.Therefore,some military problems are presented in this paper.In order to get more fighting time for damaged equipment to participate in operation again as much as possible,three problems should be considered properly.The first problem is how to dynamically choose the most suitable damaged equipment for each repair group.The second one is how to divide tasks between different groups.The third one is how to determine execution sequence in the same group.A mathematical model is established to solve the dynamic battlefield rushrepair task scheduling problem(DBRTSP) in wartime.A variant genetic algorithm is designed to dynamically track the change of the optimal solution.A scheduling example is solved through Matlab.Results show that the proposed model is not only scientific and reasonable,but also convenient and efficient.展开更多
Since digital circuits have been widely and thoroughly applied in various fields, electronic systems are increasingly more complicated and require greater reliability. Faults may occur in electronic systems in complic...Since digital circuits have been widely and thoroughly applied in various fields, electronic systems are increasingly more complicated and require greater reliability. Faults may occur in electronic systems in complicated environments. If immediate field repairs are not made on the faults, electronic systems will not run normally, and this will lead to serious losses. The traditional method for improving system reliability based on redundant fault-tolerant technique has been unable to meet the requirements. Therefore, on the basis of(evolvable hardware)-based and(reparation balance technology)-based electronic circuit fault self-repair strategy proposed in our preliminary work, the optimal design of rectification circuits(RTCs) in electronic circuit fault self-repair based on global signal optimization is deeply researched in this paper. First of all, the basic theory of RTC optimal design based on global signal optimization is proposed. Secondly, relevant considerations and suitable ranges are analyzed. Then, the basic flow of RTC optimal design is researched. Eventually, a typical circuit is selected for simulation verification, and detailed simulated analysis is made on five circumstances that occur during RTC evolution. The simulation results prove that compared with the conventional design method based RTC, the global signal optimization design method based RTC is lower in hardware cost, faster in circuit evolution, higher in convergent precision, and higher in circuit evolution success rate. Therefore, the global signal optimization based RTC optimal design method applied in the electronic circuit fault self-repair technology is proven to be feasible, effective, and advantageous.展开更多
基金The US National Science Foundation (No. CMMI-0408390, CMMI-0644552)the Research Fellowship for International Young Scientists (No. 51050110143)+2 种基金the Fok Ying-Tong Education Foundation(No. 114024)the Natural Science Foundation of Jiangsu Province (No.BK2009015)the Postdoctoral Science Foundation of Jiangsu Province (No.0901005C)
文摘To diagnose the feasibility of the solution of a job-shop scheduling problem（JSSP）,a test algorithm based on diagraph and heuristic search is developed and verified through a case study.Meanwhile,a new repair algorithm for modifying an infeasible solution of the JSSP to become a feasible solution is proposed for the general JSSP.The computational complexity of the test algorithm and the repair algorithm is both O（n） under the worst-case scenario,and O（2J＋M） for the repair algorithm under the best-case scenario.The repair algorithm is not limited to specific optimization methods,such as local tabu search,genetic algorithms and shifting bottleneck procedures for job shop scheduling,but applicable to generic infeasible solutions for the JSSP to achieve feasibility.
文摘A multipath source self repair routing (MSSRR) algorithm for mobile ad hoc networks is proposed. By using multiple paths which can be repaired by themselves to transmit packets alternately, the network's load is balanced, the link state in the network can be checked in time, the number of the times the route discovery mechanism starts is decreased. If only one route which will be broken can be used to transmit the packets, the route discovery mechanism is restarted.The algorithm is implemented on the basis of dynamic source routing (DSR). The effect of MSSRR on lifetime of the access from the source to the destination and the overhead is discussed. Compared with the performance of DSR,it can be seen that the algorithm can improve the performance of the network obviously and the overhead almost does not increase if the average hop count is larger.
基金supported by National Natural Science Foundation of China (No. 71171199)Natural Science Foundation of Shaanxi Province of China (No. 2013JM1003)
文摘Based on the uncertainty theory, this paper is devoted to the redundancy allocation problem in repairable parallel-series systems with uncertain factors, where the failure rate, repair rate and other relative coefficients involved are considered as uncertain variables. The availability of the system and the corresponding designing cost are considered as two optimization objectives. A crisp multiobjective optimization formulation is presented on the basis of uncertainty theory to solve this resultant problem. For solving this problem efficiently, a new multiobjective artificial bee colony algorithm is proposed to search the Pareto efficient set, which introduces rank value and crowding distance in the greedy selection strategy, applies fast non-dominated sort procedure in the exploitation search and inserts tournament selection in the onlooker bee phase. It shows that the proposed algorithm outperforms NSGA-II greatly and can solve multiobjective redundancy allocation problem efficiently. Finally, a numerical example is provided to illustrate this approach.
文摘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.
基金supported by the National Natural Science Foundation of China (70971132)the Elite Plan Program of National University of Defense Technology
文摘The dynamic capacitated location allocation problem in the military supportive network（DCLAP-MSN） is a representative of combinative optimization problems,and its optimization process is complicated.For this reason,a dynamic capacitated location allocation model is provided firstly.Then,a hybrid heuristic algorithm which combines genetic algorithm,repair algorithm of solutions and greedy search,is proposed as the solving method.The optimization performance is improved by effectively integrating the repair algorithm of solutions and greedy search with genetic optimization.The experiment results indicate that the proposed algorithm is a feasible and effective method for the problem.
文摘A new reliability allocation model has been built for engine system, which is a repairable system, and consists of a large number of mechanical components. The cost and reliability are taken as objective function and constraint condition respectively. The parameters of components lifetime distribution are given as decision variables, and the component lifetimes are assumed to follow that Weibull distribution. The allocation is separated into two steps to reduce calculated amount of one allocation. Genetic algorithm and Monte Carlo method are applied to solve distribution parameters and system cost separately.
基金supported by the National Natural Science Foundation of China (Nos. 61271153, 61372039)
文摘In the face of harsh natural environment applications such as earth-orbiting and deep space satellites, underwater sea vehicles, strong electromagnetic interference and temperature stress,the circuits faults appear easily. Circuit faults will inevitably lead to serious losses of availability or impeded mission success without self-repair over the mission duration. Traditional fault-repair methods based on redundant fault-tolerant technique are straightforward to implement, yet their area, power and weight cost can be excessive. Moreover they utilize all plug-in or component level circuits to realize redundant backup, such that their applicability is limited. Hence, a novel selfrepair technology based on evolvable hardware（EHW） and reparation balance technology（RBT） is proposed. Its cost is low, and fault self-repair of various circuits and devices can be realized through dynamic configuration. Making full use of the fault signals, correcting circuit can be found through EHW technique to realize the balance and compensation of the fault output-signals. In this paper, the self-repair model was analyzed which based on EHW and RBT technique, the specific self-repair strategy was studied, the corresponding self-repair circuit fault system was designed, and the typical faults were simulated and analyzed which combined with the actual electronic devices. Simulation results demonstrated that the proposed fault self-repair strategy was feasible. Compared to traditional techniques, fault self-repair based on EHW consumes fewer hardware resources, and the scope of fault self-repair was expanded significantly.
基金This project was supported by the National Natural Science Foundation of China the Open Project Foundation of Comput-er Software New Technique National Key Laboratory of Nanjing University.
文摘This paper presents a new hybrid genetic algorithm for the vertex cover problems in which scan-repair and local improvement techniques are used for local optimization. With the hybrid approach, genetic algorithms are used to perform global exploration in a population, while neighborhood search methods are used to perform local exploitation around the chromosomes. The experimental results indicate that hybrid genetic algorithms can obtain solutions of excellent quality to the problem instances with different sizes. The pure genetic algorithms are outperformed by the neighborhood search heuristics procedures combined with genetic algorithms.
文摘During the war,equipment is constantly being damaged with limited battlefield rush-repair time and power.Therefore,some military problems are presented in this paper.In order to get more fighting time for damaged equipment to participate in operation again as much as possible,three problems should be considered properly.The first problem is how to dynamically choose the most suitable damaged equipment for each repair group.The second one is how to divide tasks between different groups.The third one is how to determine execution sequence in the same group.A mathematical model is established to solve the dynamic battlefield rushrepair task scheduling problem(DBRTSP) in wartime.A variant genetic algorithm is designed to dynamically track the change of the optimal solution.A scheduling example is solved through Matlab.Results show that the proposed model is not only scientific and reasonable,but also convenient and efficient.
基金supported by the National Natural Science Foundation of China (Nos. 61271153, 61372039)
文摘Since digital circuits have been widely and thoroughly applied in various fields, electronic systems are increasingly more complicated and require greater reliability. Faults may occur in electronic systems in complicated environments. If immediate field repairs are not made on the faults, electronic systems will not run normally, and this will lead to serious losses. The traditional method for improving system reliability based on redundant fault-tolerant technique has been unable to meet the requirements. Therefore, on the basis of(evolvable hardware)-based and(reparation balance technology)-based electronic circuit fault self-repair strategy proposed in our preliminary work, the optimal design of rectification circuits(RTCs) in electronic circuit fault self-repair based on global signal optimization is deeply researched in this paper. First of all, the basic theory of RTC optimal design based on global signal optimization is proposed. Secondly, relevant considerations and suitable ranges are analyzed. Then, the basic flow of RTC optimal design is researched. Eventually, a typical circuit is selected for simulation verification, and detailed simulated analysis is made on five circumstances that occur during RTC evolution. The simulation results prove that compared with the conventional design method based RTC, the global signal optimization design method based RTC is lower in hardware cost, faster in circuit evolution, higher in convergent precision, and higher in circuit evolution success rate. Therefore, the global signal optimization based RTC optimal design method applied in the electronic circuit fault self-repair technology is proven to be feasible, effective, and advantageous.
