Due to the NP-hardness of the two-sided assembly line balancing （TALB） problem, multiple constraints existing in real applications are less studied, especially when one task is involved with several constraints. In ...Due to the NP-hardness of the two-sided assembly line balancing （TALB） problem, multiple constraints existing in real applications are less studied, especially when one task is involved with several constraints. In this paper, an effective hybrid algorithm is proposed to address the TALB problem with multiple constraints （TALB-MC）. Considering the discrete attribute of TALB-MC and the continuous attribute of the standard teaching-learning-based optimization （TLBO） algorithm, the random-keys method is hired in task permutation representation, for the purpose of bridging the gap between them. Subsequently, a special mechanism for handling multiple constraints is developed. In the mechanism, the directions constraint of each task is ensured by the direction check and adjustment. The zoning constraints and the synchronism constraints are satisfied by teasing out the hidden correlations among constraints. The positional constraint is allowed to be violated to some extent in decoding and punished in cost fimction. Finally, with the TLBO seeking for the global optimum, the variable neighborhood search （VNS） is further hybridized to extend the local search space. The experimental results show that the proposed hybrid algorithm outperforms the late acceptance hill-climbing algorithm （LAHC） for TALB-MC in most cases, especially for large-size problems with multiple constraints, and demonstrates well balance between the exploration and the exploitation. This research proposes an effective and efficient algorithm for solving TALB-MC problem by hybridizing the TLBO and VNS.展开更多
Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed sy...Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed systems. In general, multi-constrained path selection with or without optimization is a NP-complete problem that can not be exactly solved in polynomial time. Hence, accurate constraints-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The expected impact of such a constrained-based routing algorithm has resulted in the proposal of numerous heuristics and a few exact QoS algorithms. This paper aims to give a thorough, concise and fair evaluation of the most important multiple constraint-based QoS multicast routing algorithms known today, and it provides a descriptive overview and simulation results of these multi-constrained routing algorithms.展开更多
New approaches for facility distribution in chemical plants are proposed including an improved non-overlapping constraint based on projection relationships of facilities and a novel toxic gas dispersion constraint. In...New approaches for facility distribution in chemical plants are proposed including an improved non-overlapping constraint based on projection relationships of facilities and a novel toxic gas dispersion constraint. In consideration of the large number of variables in the plant layout model, our new method can significantly reduce the number of variables with their own projection relationships. Also, as toxic gas dispersion is a usual incident in a chemical plant, a simple approach to describe the gas leakage is proposed, which can clearly represent the constraints of potential emission source and sitting facilities. For solving the plant layout model, an improved genetic algorithm (GA) based on infeasible solution fix technique is proposed, which improves the globe search ability of GA. The case study and experiment show that a better layout plan can be obtained with our method, and the safety factors such as gas dispersion and minimum distances can be well handled in the solution.展开更多
Underwater acoustic channels are recognized for being one of the most difficult propagation media due to considerable difficulties such as： multipath, ambient noise, time-frequency selective fading. The exploitation ...Underwater acoustic channels are recognized for being one of the most difficult propagation media due to considerable difficulties such as： multipath, ambient noise, time-frequency selective fading. The exploitation of sparsity contained in underwater acoustic channels provides a potential solution to improve the performance of underwater acoustic channel estimation. Compared with the classic 10 and 11 norm constraint LMS algorithms, the p-norm-like （Ip） constraint LMS algorithm proposed in our previous investigation exhibits better sparsity exploitation performance at the presence of channel variations, as it enables the adaptability to the sparseness by tuning of p parameter. However, the decimal exponential calculation associated with the p-norm-like constraint LMS algorithm poses considerable limitations in practical application. In this paper, a simplified variant of the p-norm-like constraint LMS was proposed with the employment of Newton iteration m to approximate the decimal exponential calculation. Num simulations and the experimental results obtained in physical shallow water channels demonstrate the effectiveness of the proposed method compared to traditional norm constraint LMS algorithms.展开更多
Smooth constraint is important in linear inversion, but it is difficult to apply directly to model parameters in genetic algorithms. If the model parameters are smoothed in iteration, the diversity of models will be g...Smooth constraint is important in linear inversion, but it is difficult to apply directly to model parameters in genetic algorithms. If the model parameters are smoothed in iteration, the diversity of models will be greatly suppressed and all the models in population will tend to equal in a few iterations, so the optimal solution meeting requirement can not be obtained. In this paper, an indirect smooth constraint technique is introduced to genetic inversion. In this method, the new models produced in iteration are smoothed, then used as theoretical models in calculation of misfit function, but in process of iteration only the original models are used in order to keep the diversity of models. The technique is effective in inversion of surface wave and receiver function. Using this technique, we invert the phase velocity of Raleigh wave in the Tibetan Plateau, revealing the horizontal variation of S wave velocity structure near the center of the Tibetan Plateau. The results show that the S wave velocity in the north is relatively lower than that in the south. For most paths there is a lower velocity zone with 12-25 km thick at the depth of 15-40 km. The lower velocity zone in upper mantle is located below the depth of 100 km, and the thickness is usually 40-80 km, but for a few paths reach to 100 km thick. Among the area of Ando, Maqi and Ushu stations, there is an obvious lower velocity zone with the lowest velocity of 4.2-4.3 km/s at the depth of 90-230 km. Based on the S wave velocity structures of different paths and former data, we infer that the subduction of the Indian Plate is delimited nearby the Yarlung Zangbo suture zone.展开更多
To solve the scheduling problem of dual-armed cluster tools for wafer fabrications with residency time and reentrant constraints,a heuristic scheduling algorithm was developed.Firstly,on the basis of formulating sched...To solve the scheduling problem of dual-armed cluster tools for wafer fabrications with residency time and reentrant constraints,a heuristic scheduling algorithm was developed.Firstly,on the basis of formulating scheduling problems domain of dual-armed cluster tools,a non-integer programming model was set up with a minimizing objective function of the makespan.Combining characteristics of residency time and reentrant constraints,a scheduling algorithm of searching the optimal operation path of dual-armed transport module was presented under many kinds of robotic scheduling paths for dual-armed cluster tools.Finally,the experiments were designed to evaluate the proposed algorithm.The results show that the proposed algorithm is feasible and efficient for obtaining an optimal scheduling solution of dual-armed cluster tools with residency time and reentrant constraints.展开更多
Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding(VNE) is a key issue in net...Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding(VNE) is a key issue in network virtualization. VNE is NP-hard and former VNE algorithms are mostly heuristic in the literature.VNE exact algorithms have been developed in recent years. However, the constraints of exact VNE are only node capacity and link bandwidth.Based on these, this paper presents an exact VNE algorithm, ILP-LC, which is based on Integer Linear Programming(ILP), for embedding virtual network request with location constraints. This novel algorithm is aiming at mapping virtual network request(VNR) successfully as many as possible and consuming less substrate resources.The topology of each VNR is randomly generated by Waxman model. Simulation results show that the proposed ILP-LC algorithm outperforms the typical heuristic algorithms in terms of the VNR acceptance ratio, at least 15%.展开更多
To improve the productivity of cluster tools in semiconductor fabrications,on the basis of stating scheduling problems,a try and error-based scheduling algorithm was proposed with residency time constraints and an obj...To improve the productivity of cluster tools in semiconductor fabrications,on the basis of stating scheduling problems,a try and error-based scheduling algorithm was proposed with residency time constraints and an objective of minimizing Makespan for the wafer jobs in cluster tools.Firstly,mathematical formulations of scheduling problems were presented by using assumptions and definitions of a scheduling domain.Resource conflicts were analyzed in the built scheduling model,and policies to solve resource conflicts were built.A scheduling algorithm was developed.Finally,the performances of the proposed algorithm were evaluated and compared with those of other methods by simulations.Experiment results indicate that the proposed algorithm is effective and practical in solving the scheduling problem of the cluster tools.展开更多
Motivated by the projects constrained by space capacity and resource transporting time, a project scheduling probIem with capacity constraint was modeled. A hybrid algorithm is proposed, which uses the ideas of bi-lev...Motivated by the projects constrained by space capacity and resource transporting time, a project scheduling probIem with capacity constraint was modeled. A hybrid algorithm is proposed, which uses the ideas of bi-level scheduling and project decomposition technology, and the genetic algorithm and tabu search is combined. Topological reordering technology is used to improve the efficiency of evaluation. Simulation results show the proposed algorithm can obtain satisfied scheduling results in acceptable time.展开更多
Aimed at improving the insufficient search ability of constraint differential evolution with single constraint handling technique when solving complex optimization problem, this paper proposes a constraint differentia...Aimed at improving the insufficient search ability of constraint differential evolution with single constraint handling technique when solving complex optimization problem, this paper proposes a constraint differential evolution algorithm?based on ensemble of constraint handling techniques and multi-population?framework, called ECMPDE. First, handling three improved variants of differential evolution algorithms are dynamically matched with two constraint handling techniques through the constraint allocation mechanism. Each combination includes three variants with corresponding constraint handling technique?and these combinations are in the set. Second, the population is divided into three smaller subpopulations and one larger reward subpopulation. Then a combination with three constraint algorithms is randomly selected from the set, and the three constraint algorithms are run in three sub-populations respectively. According to the improvement of fitness value, the optimal constraint?algorithm is selected to run on the reward sub-population, which can share?information and close cooperation among populations. In order to verify the effectiveness of the proposed algorithm, 12 standard constraint optimization problems?and 10 engineering constraint optimization problems are tested. The experimental results show that ECMPDE is an effective algorithm for solving constraint optimization problems.展开更多
This paper develops an integrating algorithm for fully rheonomous affine constraints and gives theoretical analysis of the algorithm for the completely integrable case. First, some preliminaries on the fully rheonomou...This paper develops an integrating algorithm for fully rheonomous affine constraints and gives theoretical analysis of the algorithm for the completely integrable case. First, some preliminaries on the fully rheonomous affine constraints are shown. Next, an integrating algorithm that calculates independent first integrals is derived. In addition, the existence of an inverse function utilized in the algorithm is investigated. Then, an example is shown in order to evaluate the effectiveness of the proposed method. By using the proposed integrating algorithm, we can easily calculate independent first integrals for given constraints, and hence it can be utilized for various research fields.展开更多
In the traffic equilibrium problem, we introduce capacity constraints of arcs, extend Beckmann’s formula to include these constraints, and give an algorithm for traffic equilibrium flows with capacity constraints on ...In the traffic equilibrium problem, we introduce capacity constraints of arcs, extend Beckmann’s formula to include these constraints, and give an algorithm for traffic equilibrium flows with capacity constraints on arcs. Using an example, we illustrate the application of the algorithm and show that Beckmann’s formula is a sufficient condition only, not a necessary condition, for traffic equilibrium with capacity constraints of arcs.展开更多
Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerf...Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning problems.In the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution space.Finding solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fiuctuation far from convergence.Here we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating process.For the specific example of model RB(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost.Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.展开更多
The dense and accurate measurement of 3D texture is helpful in evaluating the pavement function.To form dense mandatory constraints and improve matching accuracy,the traditional binocular reconstruction technology was...The dense and accurate measurement of 3D texture is helpful in evaluating the pavement function.To form dense mandatory constraints and improve matching accuracy,the traditional binocular reconstruction technology was improved threefold.First,a single moving laser line was introduced to carry out global scanning constraints on the target,which would well overcome the difficulty of installing and recognizing excessive laser lines.Second,four kinds of improved algorithms,namely,disparity replacement,superposition synthesis,subregion segmentation,and subregion segmentation centroid enhancement,were established based on different constraint mechanism.Last,the improved binocular reconstruction test device was developed to realize the dual functions of 3D texture measurement and precision self-evaluation.Results show that compared with traditional algorithms,the introduction of a single laser line scanning constraint is helpful in improving the measurement’s accuracy.Among various improved algorithms,the improvement effect of the subregion segmentation centroid enhancement method is the best.It has a good effect on both overall measurement and single pointmeasurement,which can be considered to be used in pavement function evaluation.展开更多
In this paper, we describe a successive approximation and smooth sequential quadratic programming （SQP） method for mathematical programs with nonlinear complementarity constraints （MPCC）. We introduce a class of s...In this paper, we describe a successive approximation and smooth sequential quadratic programming （SQP） method for mathematical programs with nonlinear complementarity constraints （MPCC）. We introduce a class of smooth programs to approximate the MPCC. Using an 11 penalty function, the line search assures global convergence, while the superlinear convergence rate is shown under the strictly complementary and second-order sufficient conditions. Moreover, we prove that the current iterated point is an exact stationary point of the mathematical programs with equilibrium constraints （MPEC） when the algorithm terminates finitely.展开更多
Shape and size optimization with frequency constraints is a highly nonlinear problem withmixed design variables,non-convex search space,and multiple local optima.Therefore,a hybrid sine cosine firefly algorithm(HSCFA)...Shape and size optimization with frequency constraints is a highly nonlinear problem withmixed design variables,non-convex search space,and multiple local optima.Therefore,a hybrid sine cosine firefly algorithm(HSCFA)is proposed to acquire more accurate solutions with less finite element analysis.The full attraction model of firefly algorithm(FA)is analyzed,and the factors that affect its computational efficiency and accuracy are revealed.A modified FA with simplified attraction model and adaptive parameter of sine cosine algorithm(SCA)is proposed to reduce the computational complexity and enhance the convergence rate.Then,the population is classified,and different populations are updated by modified FA and SCA respectively.Besides,the random search strategy based on Lévy flight is adopted to update the stagnant or infeasible solutions to enhance the population diversity.Elitist selection technique is applied to save the promising solutions and further improve the convergence rate.Moreover,the adaptive penalty function is employed to deal with the constraints.Finally,the performance of HSCFA is demonstrated through the numerical examples with nonstructural masses and frequency constraints.The results show that HSCFA is an efficient and competitive tool for shape and size optimization problems with frequency constraints.展开更多
It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling proble...It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.展开更多
In order to improve the scheduling efficiency of photolithography,bottleneck process of wafer fabrications in the semiconductor industry,an effective estimation of distribution algorithm is proposed for scheduling pro...In order to improve the scheduling efficiency of photolithography,bottleneck process of wafer fabrications in the semiconductor industry,an effective estimation of distribution algorithm is proposed for scheduling problems of parallel litho machines with reticle constraints,where multiple reticles are available for each reticle type.First,the scheduling problem domain of parallel litho machines is described with reticle constraints and mathematical programming formulations are put forward with the objective of minimizing total weighted completion time.Second,estimation of distribution algorithm is developed with a decoding scheme specially designed to deal with the reticle constraints.Third,an insert-based local search with the first move strategy is introduced to enhance the local exploitation ability of the algorithm.Finally,simulation experiments and analysis demonstrate the effectiveness of the proposed algorithm.展开更多
In this paper, integrability conditions and an integrating algorithm of fully rheonomous affine constraints (FRACs) for the partially integrable case are studied. First, some preliminaries on the FRACs are illustrated...In this paper, integrability conditions and an integrating algorithm of fully rheonomous affine constraints (FRACs) for the partially integrable case are studied. First, some preliminaries on the FRACs are illustrated. Next, necessary and sufficient conditions on the partially integrable case for the FRACs are derived. Then, an integrating algorithm to calculate independent first integrals of the FRACs for the partially integrable case is derived. Moreover, the existence of an inverse function utilized in the algorithm is proven. After that, an example is presented for evaluation of the effectiveness of the proposed method. As a result, it turns out that the proposed integrating algorithm can easily calculate independent first integrals for given partially integrable FRACs, and thus this new algorithm is expected to be applied to various research fields.展开更多
The scheduling of construction equipment is a means to realize network planning.With the large-scale and low-cost requirements of engineering construction,the cooperation among members of the engineering supply chain ...The scheduling of construction equipment is a means to realize network planning.With the large-scale and low-cost requirements of engineering construction,the cooperation among members of the engineering supply chain has become very important,and effective coordination of project plans at all levels to optimize the resource management and scheduling of a project is helpful to reduce project duration and cost.In this paper,under the milestone constraint conditions,the scheduling problems of multiple construction devices in the same sequence of operation were described and hypothesized mathematically,and the scheduling models of multiple equipment were established.The Palmer algorithm,CDS algorithm and Gupta algorithm were respectively used to solve the optimal scheduling of construction equipment to achieve the optimization of the construction period.The optimization scheduling of a single construction device and multiple construction devices was solved by using sequencing theory under milestone constraint,and these methods can obtain reasonable results,which has important guiding significance for the scheduling of construction equipment.展开更多
基金Supported by National Natural Science Foundation of China(Grant Nos.51275366,50875190,51305311)Specialized Research Fund for the Doctoral Program of Higher Education of China(Grant No.20134219110002)
文摘Due to the NP-hardness of the two-sided assembly line balancing （TALB） problem, multiple constraints existing in real applications are less studied, especially when one task is involved with several constraints. In this paper, an effective hybrid algorithm is proposed to address the TALB problem with multiple constraints （TALB-MC）. Considering the discrete attribute of TALB-MC and the continuous attribute of the standard teaching-learning-based optimization （TLBO） algorithm, the random-keys method is hired in task permutation representation, for the purpose of bridging the gap between them. Subsequently, a special mechanism for handling multiple constraints is developed. In the mechanism, the directions constraint of each task is ensured by the direction check and adjustment. The zoning constraints and the synchronism constraints are satisfied by teasing out the hidden correlations among constraints. The positional constraint is allowed to be violated to some extent in decoding and punished in cost fimction. Finally, with the TLBO seeking for the global optimum, the variable neighborhood search （VNS） is further hybridized to extend the local search space. The experimental results show that the proposed hybrid algorithm outperforms the late acceptance hill-climbing algorithm （LAHC） for TALB-MC in most cases, especially for large-size problems with multiple constraints, and demonstrates well balance between the exploration and the exploitation. This research proposes an effective and efficient algorithm for solving TALB-MC problem by hybridizing the TLBO and VNS.
文摘Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed systems. In general, multi-constrained path selection with or without optimization is a NP-complete problem that can not be exactly solved in polynomial time. Hence, accurate constraints-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The expected impact of such a constrained-based routing algorithm has resulted in the proposal of numerous heuristics and a few exact QoS algorithms. This paper aims to give a thorough, concise and fair evaluation of the most important multiple constraint-based QoS multicast routing algorithms known today, and it provides a descriptive overview and simulation results of these multi-constrained routing algorithms.
基金Supported by the National Natural Science Foundation of China （61074153, 61104131）, and the Fundamental Research Funds for Central Universities of China （ZY1111, JD1104）.
文摘New approaches for facility distribution in chemical plants are proposed including an improved non-overlapping constraint based on projection relationships of facilities and a novel toxic gas dispersion constraint. In consideration of the large number of variables in the plant layout model, our new method can significantly reduce the number of variables with their own projection relationships. Also, as toxic gas dispersion is a usual incident in a chemical plant, a simple approach to describe the gas leakage is proposed, which can clearly represent the constraints of potential emission source and sitting facilities. For solving the plant layout model, an improved genetic algorithm (GA) based on infeasible solution fix technique is proposed, which improves the globe search ability of GA. The case study and experiment show that a better layout plan can be obtained with our method, and the safety factors such as gas dispersion and minimum distances can be well handled in the solution.
基金Supported by the National Natural Science Foundation of China （No.11274259） and the Specialized Research Foundation for the Doctoral Program of Higher Education of China （No.20120121110030）.
文摘Underwater acoustic channels are recognized for being one of the most difficult propagation media due to considerable difficulties such as： multipath, ambient noise, time-frequency selective fading. The exploitation of sparsity contained in underwater acoustic channels provides a potential solution to improve the performance of underwater acoustic channel estimation. Compared with the classic 10 and 11 norm constraint LMS algorithms, the p-norm-like （Ip） constraint LMS algorithm proposed in our previous investigation exhibits better sparsity exploitation performance at the presence of channel variations, as it enables the adaptability to the sparseness by tuning of p parameter. However, the decimal exponential calculation associated with the p-norm-like constraint LMS algorithm poses considerable limitations in practical application. In this paper, a simplified variant of the p-norm-like constraint LMS was proposed with the employment of Newton iteration m to approximate the decimal exponential calculation. Num simulations and the experimental results obtained in physical shallow water channels demonstrate the effectiveness of the proposed method compared to traditional norm constraint LMS algorithms.
基金State Natural Science Foundation (49874021).Contribution No. 01FE2002, Institute of Geophysics, China Seismological Bureau.
文摘Smooth constraint is important in linear inversion, but it is difficult to apply directly to model parameters in genetic algorithms. If the model parameters are smoothed in iteration, the diversity of models will be greatly suppressed and all the models in population will tend to equal in a few iterations, so the optimal solution meeting requirement can not be obtained. In this paper, an indirect smooth constraint technique is introduced to genetic inversion. In this method, the new models produced in iteration are smoothed, then used as theoretical models in calculation of misfit function, but in process of iteration only the original models are used in order to keep the diversity of models. The technique is effective in inversion of surface wave and receiver function. Using this technique, we invert the phase velocity of Raleigh wave in the Tibetan Plateau, revealing the horizontal variation of S wave velocity structure near the center of the Tibetan Plateau. The results show that the S wave velocity in the north is relatively lower than that in the south. For most paths there is a lower velocity zone with 12-25 km thick at the depth of 15-40 km. The lower velocity zone in upper mantle is located below the depth of 100 km, and the thickness is usually 40-80 km, but for a few paths reach to 100 km thick. Among the area of Ando, Maqi and Ushu stations, there is an obvious lower velocity zone with the lowest velocity of 4.2-4.3 km/s at the depth of 90-230 km. Based on the S wave velocity structures of different paths and former data, we infer that the subduction of the Indian Plate is delimited nearby the Yarlung Zangbo suture zone.
基金Projects(7107111561273035)supported by the National Natural Science Foundation of China
文摘To solve the scheduling problem of dual-armed cluster tools for wafer fabrications with residency time and reentrant constraints,a heuristic scheduling algorithm was developed.Firstly,on the basis of formulating scheduling problems domain of dual-armed cluster tools,a non-integer programming model was set up with a minimizing objective function of the makespan.Combining characteristics of residency time and reentrant constraints,a scheduling algorithm of searching the optimal operation path of dual-armed transport module was presented under many kinds of robotic scheduling paths for dual-armed cluster tools.Finally,the experiments were designed to evaluate the proposed algorithm.The results show that the proposed algorithm is feasible and efficient for obtaining an optimal scheduling solution of dual-armed cluster tools with residency time and reentrant constraints.
基金supported by the National Basic Research Program of China(973 Program)under Grant 2013CB329005
文摘Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding(VNE) is a key issue in network virtualization. VNE is NP-hard and former VNE algorithms are mostly heuristic in the literature.VNE exact algorithms have been developed in recent years. However, the constraints of exact VNE are only node capacity and link bandwidth.Based on these, this paper presents an exact VNE algorithm, ILP-LC, which is based on Integer Linear Programming(ILP), for embedding virtual network request with location constraints. This novel algorithm is aiming at mapping virtual network request(VNR) successfully as many as possible and consuming less substrate resources.The topology of each VNR is randomly generated by Waxman model. Simulation results show that the proposed ILP-LC algorithm outperforms the typical heuristic algorithms in terms of the VNR acceptance ratio, at least 15%.
基金Projects(71071115,60574054) supported by the National Natural Science Foundation of China
文摘To improve the productivity of cluster tools in semiconductor fabrications,on the basis of stating scheduling problems,a try and error-based scheduling algorithm was proposed with residency time constraints and an objective of minimizing Makespan for the wafer jobs in cluster tools.Firstly,mathematical formulations of scheduling problems were presented by using assumptions and definitions of a scheduling domain.Resource conflicts were analyzed in the built scheduling model,and policies to solve resource conflicts were built.A scheduling algorithm was developed.Finally,the performances of the proposed algorithm were evaluated and compared with those of other methods by simulations.Experiment results indicate that the proposed algorithm is effective and practical in solving the scheduling problem of the cluster tools.
基金the National Basic Research Program (973 Program) (2002CB312200)
文摘Motivated by the projects constrained by space capacity and resource transporting time, a project scheduling probIem with capacity constraint was modeled. A hybrid algorithm is proposed, which uses the ideas of bi-level scheduling and project decomposition technology, and the genetic algorithm and tabu search is combined. Topological reordering technology is used to improve the efficiency of evaluation. Simulation results show the proposed algorithm can obtain satisfied scheduling results in acceptable time.
文摘Aimed at improving the insufficient search ability of constraint differential evolution with single constraint handling technique when solving complex optimization problem, this paper proposes a constraint differential evolution algorithm?based on ensemble of constraint handling techniques and multi-population?framework, called ECMPDE. First, handling three improved variants of differential evolution algorithms are dynamically matched with two constraint handling techniques through the constraint allocation mechanism. Each combination includes three variants with corresponding constraint handling technique?and these combinations are in the set. Second, the population is divided into three smaller subpopulations and one larger reward subpopulation. Then a combination with three constraint algorithms is randomly selected from the set, and the three constraint algorithms are run in three sub-populations respectively. According to the improvement of fitness value, the optimal constraint?algorithm is selected to run on the reward sub-population, which can share?information and close cooperation among populations. In order to verify the effectiveness of the proposed algorithm, 12 standard constraint optimization problems?and 10 engineering constraint optimization problems are tested. The experimental results show that ECMPDE is an effective algorithm for solving constraint optimization problems.
文摘This paper develops an integrating algorithm for fully rheonomous affine constraints and gives theoretical analysis of the algorithm for the completely integrable case. First, some preliminaries on the fully rheonomous affine constraints are shown. Next, an integrating algorithm that calculates independent first integrals is derived. In addition, the existence of an inverse function utilized in the algorithm is investigated. Then, an example is shown in order to evaluate the effectiveness of the proposed method. By using the proposed integrating algorithm, we can easily calculate independent first integrals for given constraints, and hence it can be utilized for various research fields.
文摘In the traffic equilibrium problem, we introduce capacity constraints of arcs, extend Beckmann’s formula to include these constraints, and give an algorithm for traffic equilibrium flows with capacity constraints on arcs. Using an example, we illustrate the application of the algorithm and show that Beckmann’s formula is a sufficient condition only, not a necessary condition, for traffic equilibrium with capacity constraints of arcs.
基金supported by Guangdong Major Project of Basic and Applied Basic Research No.2020B0301030008Science and Technology Program of Guangzhou No.2019050001+2 种基金the Chinese Academy of Sciences Grant QYZDJ-SSWSYS018the National Natural Science Foundation of China(Grant No.12171479)supported by the National Natural Science Foundation of China(Grant Nos.11301339 and 11491240108)。
文摘Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning problems.In the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution space.Finding solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fiuctuation far from convergence.Here we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating process.For the specific example of model RB(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost.Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.
基金supported by National Natural Science Foundation of China (52178422)Doctoral Research Foundation of Hubei University of Arts and Science (2059047)National College Students’Innovation and Entrepreneurship Training Program (202210519021).
文摘The dense and accurate measurement of 3D texture is helpful in evaluating the pavement function.To form dense mandatory constraints and improve matching accuracy,the traditional binocular reconstruction technology was improved threefold.First,a single moving laser line was introduced to carry out global scanning constraints on the target,which would well overcome the difficulty of installing and recognizing excessive laser lines.Second,four kinds of improved algorithms,namely,disparity replacement,superposition synthesis,subregion segmentation,and subregion segmentation centroid enhancement,were established based on different constraint mechanism.Last,the improved binocular reconstruction test device was developed to realize the dual functions of 3D texture measurement and precision self-evaluation.Results show that compared with traditional algorithms,the introduction of a single laser line scanning constraint is helpful in improving the measurement’s accuracy.Among various improved algorithms,the improvement effect of the subregion segmentation centroid enhancement method is the best.It has a good effect on both overall measurement and single pointmeasurement,which can be considered to be used in pavement function evaluation.
基金supported by the National Natural Science Foundation of China (Nos.10501009,10771040)the Natural Science Foundation of Guangxi Province of China (Nos.0728206,0640001)the China Postdoctoral Science Foundation (No.20070410228)
文摘In this paper, we describe a successive approximation and smooth sequential quadratic programming （SQP） method for mathematical programs with nonlinear complementarity constraints （MPCC）. We introduce a class of smooth programs to approximate the MPCC. Using an 11 penalty function, the line search assures global convergence, while the superlinear convergence rate is shown under the strictly complementary and second-order sufficient conditions. Moreover, we prove that the current iterated point is an exact stationary point of the mathematical programs with equilibrium constraints （MPEC） when the algorithm terminates finitely.
基金supported by the NationalNatural Science Foundation of China(No.11672098).
文摘Shape and size optimization with frequency constraints is a highly nonlinear problem withmixed design variables,non-convex search space,and multiple local optima.Therefore,a hybrid sine cosine firefly algorithm(HSCFA)is proposed to acquire more accurate solutions with less finite element analysis.The full attraction model of firefly algorithm(FA)is analyzed,and the factors that affect its computational efficiency and accuracy are revealed.A modified FA with simplified attraction model and adaptive parameter of sine cosine algorithm(SCA)is proposed to reduce the computational complexity and enhance the convergence rate.Then,the population is classified,and different populations are updated by modified FA and SCA respectively.Besides,the random search strategy based on Lévy flight is adopted to update the stagnant or infeasible solutions to enhance the population diversity.Elitist selection technique is applied to save the promising solutions and further improve the convergence rate.Moreover,the adaptive penalty function is employed to deal with the constraints.Finally,the performance of HSCFA is demonstrated through the numerical examples with nonstructural masses and frequency constraints.The results show that HSCFA is an efficient and competitive tool for shape and size optimization problems with frequency constraints.
文摘It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.
基金Supported by the National High Technology Research and Development Programme of China(No.2009AA043000)the National Natural Science Foundation of China(No.61273035,71471135)
文摘In order to improve the scheduling efficiency of photolithography,bottleneck process of wafer fabrications in the semiconductor industry,an effective estimation of distribution algorithm is proposed for scheduling problems of parallel litho machines with reticle constraints,where multiple reticles are available for each reticle type.First,the scheduling problem domain of parallel litho machines is described with reticle constraints and mathematical programming formulations are put forward with the objective of minimizing total weighted completion time.Second,estimation of distribution algorithm is developed with a decoding scheme specially designed to deal with the reticle constraints.Third,an insert-based local search with the first move strategy is introduced to enhance the local exploitation ability of the algorithm.Finally,simulation experiments and analysis demonstrate the effectiveness of the proposed algorithm.
文摘In this paper, integrability conditions and an integrating algorithm of fully rheonomous affine constraints (FRACs) for the partially integrable case are studied. First, some preliminaries on the FRACs are illustrated. Next, necessary and sufficient conditions on the partially integrable case for the FRACs are derived. Then, an integrating algorithm to calculate independent first integrals of the FRACs for the partially integrable case is derived. Moreover, the existence of an inverse function utilized in the algorithm is proven. After that, an example is presented for evaluation of the effectiveness of the proposed method. As a result, it turns out that the proposed integrating algorithm can easily calculate independent first integrals for given partially integrable FRACs, and thus this new algorithm is expected to be applied to various research fields.
文摘The scheduling of construction equipment is a means to realize network planning.With the large-scale and low-cost requirements of engineering construction,the cooperation among members of the engineering supply chain has become very important,and effective coordination of project plans at all levels to optimize the resource management and scheduling of a project is helpful to reduce project duration and cost.In this paper,under the milestone constraint conditions,the scheduling problems of multiple construction devices in the same sequence of operation were described and hypothesized mathematically,and the scheduling models of multiple equipment were established.The Palmer algorithm,CDS algorithm and Gupta algorithm were respectively used to solve the optimal scheduling of construction equipment to achieve the optimization of the construction period.The optimization scheduling of a single construction device and multiple construction devices was solved by using sequencing theory under milestone constraint,and these methods can obtain reasonable results,which has important guiding significance for the scheduling of construction equipment.
