Analysis of Petri net model and task planning heuristic algorithms for product reconfiguration

Reconfiguration planning is recognized as an important factor for reducing the cost of manufacturing reconfigurable products, and the associated main task is to generate a set of optimal or near-optimal reconfiguration sequences using some effect algorithms. A method is developed to generate a Petri net as the reconfiguration tree to represent two-state-transit of product, which solved the representation problem of reconfiguring interfaces replacement. Relating with this method, two heuristic algorithms are proposed to generate task sequences which considering economics to search reconfiguration paths effectively. At last, an objective evaluation is applied to compare these two heuristic algorithms to other ones. The developed reconfiguration task planning heuristic algorithms can generate better strategies and plans for reconfiguration. The research finds are exemplified with struts reconfiguration of reconfigurable parallel kinematics machine （RPKM）.

Heuristics Scheduling Algorithm on the Links Scheduling of Satellite-Ground Clock Synchronization and Ephemeris Uploading in COMPASS System

The execution process of satellite-ground clock synchronization and ephemeris uploading in the system is analyzed,as well as their characterized operation and their relationship.Based on the analysis of the scheduling goal and constraint character,a heuristics rule-based multi-stage link scheduling algorithm was put forward.The algorithm distinguishes the on-off-frontier satellites from the others and schedules them by turns.The paper presented the main flow as well as the detailed design of the rule.Finally based on the current COMPASS global system,some typical resources and constraints are selected to generate an instance.Then the comparison analysis between the heuristics scheduling algorithm and three other traditional scheduling strategies are carried out.The result shows the validity and reasonability of the multi-stage strategy.

Using Heuristics to the Controller Placement Problem in Software-Defined Multihop Wireless Networking

Solving the controller placement problem (CPP) in an SDN architecture with multiple controllers has a significant impact on control overhead in the network, especially in multihop wireless networks (MWNs). The generated control overhead consists of controller-device and inter-controller communications to discover the network topology, exchange configurations, and set up and modify flow tables in the control plane. However, due to the high complexity of the proposed optimization model to the CPP, heuristic algorithms have been reported to find near-optimal solutions faster for large-scale wired networks. In this paper, the objective is to extend those existing heuristic algorithms to solve a proposed optimization model to the CPP in software-defined multihop wireless networking (SDMWN).Our results demonstrate that using ranking degrees assigned to the possible controller placements, including the average distance to other devices as a degree or the connectivity degree of each placement, the extended heuristic algorithms are able to achieve the optimal solution in small-scale networks in terms of the generated control overhead and the number of controllers selected in the network. As a result, using extended heuristic algorithms, the average number of hops among devices and their assigned controllers as well as among controllers will be reduced. Moreover, these algorithms are able tolower the control overhead in large-scale networks and select fewer controllers compared to an extended algorithm that solves the CPP in SDMWN based on a randomly selected controller placement approach.

HEURISTIC PARTICLE SWARM OPTIMIZATION ALGORITHM FOR AIR COMBAT DECISION-MAKING ON CMTA

Combining the heuristic algorithm （HA） developed based on the specific knowledge of the cooperative multiple target attack （CMTA） tactics and the particle swarm optimization （PSO）, a heuristic particle swarm optimization （HPSO） algorithm is proposed to solve the decision-making （DM） problem. HA facilitates to search the local optimum in the neighborhood of a solution, while the PSO algorithm tends to explore the search space for possible solutions. Combining the advantages of HA and PSO, HPSO algorithms can find out the global optimum quickly and efficiently. It obtains the DM solution by seeking for the optimal assignment of missiles of friendly fighter aircrafts （FAs） to hostile FAs. Simulation results show that the proposed algorithm is superior to the general PSO algorithm and two GA based algorithms in searching for the best solution to the DM problem.

HEURISTIC STUDY OF FLOWSHOP SCHEDULING TO MINIMIZE MEAN FLOW TIME WITH LOT TRANSFER CONSIDERED

Lot scheduling problem with idle time transfer between processes to minimize mean flow time is very important because to minimize mean flow time is to minimize work in process. But the problem is NP hard and no polynomial algorithm exists to guarantee optimal solution. Based the analysis the mathematical structure of the problem, the paper presents a new heuristic algorithm. Computer simulation shows that the proposed heuristic algorithm performs well in terms of both quality of solution and execution speed.

Improved ant colony optimization algorithm for the traveling salesman problems

Ant colony optimization （ACO） is a new heuristic algo- rithm which has been proven a successful technique and applied to a number of combinatorial optimization problems. The traveling salesman problem （TSP） is among the most important combinato- rial problems. An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature con- vergence problem of the basic ACO algorithm on TSP. The main idea is to partition artificial ants into two groups： scout ants and common ants. The common ants work according to the search manner of basic ant colony algorithm, but scout ants have some differences from common ants, they calculate each route＇s muta- tion probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability. Simulation on TSP shows that the improved algorithm has high efficiency and robustness.

Dynamic Scheduling and Path Planning of Automated Guided Vehicles in Automatic Container Terminal

The uninterrupted operation of the quay crane(QC)ensures that the large container ship can depart port within laytime,which effectively reduces the handling cost for the container terminal and ship owners.The QC waiting caused by automated guided vehicles(AGVs)delay in the uncertain environment can be alleviated by dynamic scheduling optimization.A dynamic scheduling process is introduced in this paper to solve the AGV scheduling and path planning problems,in which the scheduling scheme determines the starting and ending nodes of paths,and the choice of paths between nodes affects the scheduling of subsequent AGVs.This work proposes a two-stage mixed integer optimization model to minimize the transportation cost of AGVs under the constraint of laytime.A dynamic optimization algorithm,including the improved rule-based heuristic algorithm and the integration of the Dijkstra algorithm and the Q-Learning algorithm,is designed to solve the optimal AGV scheduling and path schemes.A new conflict avoidance strategy based on graph theory is also proposed to reduce the probability of path conflicts between AGVs.Numerical experiments are conducted to demonstrate the effectiveness of the proposed model and algorithm over existing methods.

Scheduling algorithm of dual-armed cluster tools with residency time and reentrant constraints

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.

A Hybrid Genetic Algorithm for Reduct of Attributes in Decision System Based on Rough Set Theory

Knowledge reduction is an important issue when dealing with huge amounts of data. And it has been proved that computing the minimal reduct of decision system is NP-complete. By introducing heuristic information into genetic algorithm, we proposed a heuristic genetic algorithm. In the genetic algorithm, we constructed a new operator to maintaining the classification ability. The experiment shows that our algorithm is efficient and effective for minimal reduct, even for the special example that the simple heuristic algorithm can’t get the right result.

Heuristic algorithm for RCPSP with the objective of minimizing activities' cost

Resource-constrained project scheduling problem（RCPSP） is an important problem in research on project management. But there has been little attention paid to the objective of minimizing activities＇ cost with the resource constraints that is a critical sub-problem in partner selection of construction supply chain management because the capacities of the renewable resources supplied by the partners will effect on the project scheduling. Its mathematic model is presented firstly, and analysis on the characteristic of the problem shows that the objective function is non-regular and the problem is NP-complete following which the basic idea for solution is clarified. Based on a definition of preposing activity cost matrix, a heuristic algorithm is brought forward. Analyses on the complexity of the heuristics and the result of numerical studies show that the heuristic algorithm is feasible and relatively effective.

Model and algorithm for container ship stowage planning based on bin-packing problem

In a general case, container ship serves many different ports on each voyage. A stowage planning for container ship made at one port must take account of the influence on subsequent ports. So the complexity of stowage planning problem increases due to its multi-ports nature. This problem is NP-hard problem. In order to reduce the computational complexity, the problem is decomposed into two sub-problems in this paper. First, container ship stowage problem (CSSP) is regarded as 'packing problem', ship-bays on the board of vessel are regarded as bins, the number of slots at each bay are taken as capacities of bins, and containers with different characteristics (homogeneous containers group) are treated as items packed. At this stage, there are two objective functions, one is to minimize the number of bays packed by containers and the other is to minimize the number of overstows. Secondly, containers assigned to each bays at first stage are allocate to special slot, the objective functions are to minimize the metacentric height, heel and overstows.The taboo search heuristics algorithm are used to solve the subproblem. The main focus of this paper is on the first subproblem. A case certifies the feasibility of the model and algorithm.

Rolling optimization algorithm based on collision window for single machine scheduling problem

Focusing on the single machine scheduling problem which minimizes the total completion time in the presence of dynamic job arrivals, a rolling optimization scheduling algorithm is proposed based on the analysis of the character and structure of scheduling. An optimal scheduling strategy in collision window is presented. Performance evaluation of this algorithm is given. Simulation indicates that the proposed algorithm is better than other common heuristic algorithms on both the total performance and stability.

Rescue vehicle allocation problem based on optimal reliable path under uncertainty

Consideration of the travel time variation for rescue vehicles is significant in the field of emergency management research.Because of uncertain factors,such as the weather or OD(origin-destination)variations caused by traffic accidents,travel time is a random variable.In emergency situations,it is particularly necessary to determine the optimal reliable route of rescue vehicles from the perspective of uncertainty.This paper first proposes an optimal reliable path finding(ORPF)model for rescue vehicles,which considers the uncertainties of travel time,and link correlations.On this basis,it investigates how to optimize rescue vehicle allocation to minimize rescue time,taking into account travel time reliability under uncertain conditions.Because of the non-additive property of the objective function,this paper adopts a heuristic algorithm based on the K-shortest path algorithm,and inequality techniques to tackle the proposed modified integer programming model.Finally,the numerical experiments are presented to verify the accuracy and effectiveness of the proposed model and algorithm.The results show that ignoring travel time reliability may lead to an over-or under-estimation of the effective travel time of rescue vehicles on a particular path,and thereby an incorrect allocation scheme.

Designing an optimal stope layout for underground mining based on a heuristic algorithm

An optimal layout or three-dimensional spatial distribution of stopes guarantees the maximum profitability over life span of an underground mining operation.Thus,stope optimization is one of the key areas in underground mine planning practice.However,the computational complexity in developing an optimal stope layout has been a reason for limited availability of the algorithms offering solution to this problem.This article shares a new and efficient heuristic algorithm that considers a three-dimensional ore body model as an input,maximizes the economic value,and satisfies the physical mining and geotechnical constraints for generating an optimal stope layout.An implementation at a copper deposit demonstrates the applicability and robustness of the algorithm.A parallel processing based modification improving the performance of the original algorithm in terms of enormous computational time saving is also presented.

Optimization algorithm based on kinetic-molecular theory

Traditionally, the optimization algorithm based on physics principles has some shortcomings such as low population diversity and susceptibility to local extrema. A new optimization algorithm based on kinetic-molecular theory(KMTOA) is proposed. In the KMTOA three operators are designed: attraction, repulsion and wave. The attraction operator simulates the molecular attraction, with the molecules moving towards the optimal ones, which makes possible the optimization. The repulsion operator simulates the molecular repulsion, with the molecules diverging from the optimal ones. The wave operator simulates the thermal molecules moving irregularly, which enlarges the searching spaces and increases the population diversity and global searching ability. Experimental results indicate that KMTOA prevails over other algorithms in the robustness, solution quality, population diversity and convergence speed.

4-D Trajectory Prediction and Dynamic Planning of Aircraft Taxiing Considering Time and Fuel

Most of the traditional taxi path planning studies assume that the aircraft is in uniform speed,and the optimization goal is the shortest taxi time.Although it is easy to solve,it does not consider the changes in the speed profile of the aircraft when turning,and the shortest taxi time does not necessarily bring the best taxi fuel consumption.In this paper,the number of turns is considered,and the improved A*algorithm is used to obtain the P static paths with the shortest sum of the straight-line distance and the turning distance of the aircraft as the feasible taxi paths.By balancing taxi time and fuel consumption,a set of Pareto optimal speed profiles are generated for each preselected path to predict the 4-D trajectory of the aircraft.Based on the 4-D trajectory prediction results,the conflict by the occupied time window in the taxiing area is detected.For the conflict aircraft,based on the priority comparison,the waiting or changing path is selected to solve the taxiing conflict.Finally,the conflict free aircraft taxiing path is generated and the area occupation time window on the path is updated.The experimental results show that the total taxi distance and turn time of the aircraft are reduced,and the fuel consumption is reduced.The proposed method has high practical application value and is expected to be applied in real-time air traffic control decision-making in the future.

EA-DFPSO:An intelligent energy-efficient scheduling algorithm for mobile edge networks

Cloud data centers have become overwhelmed with data-intensive applications due to the limited computational capabilities of mobile terminals.Mobile edge computing is emerging as a potential paradigm to host application execution at the edge of networks to reduce transmission delays.Compute nodes are usually distributed in edge environments,enabling crucially efficient task scheduling among those nodes to achieve reduced processing time.Moreover,it is imperative to conserve edge server energy,enhancing their lifetimes.To this end,this paper proposes a novel task scheduling algorithm named Energy-aware Double-fitness Particle Swarm Optimization(EA-DFPSO)that is based on an improved particle swarm optimization algorithm for achieving energy efficiency in an edge computing environment along with minimal task execution time.The proposed EA-DFPSO algorithm applies a dual fitness function to search for an optimal tasks-scheduling scheme for saving edge server energy while maintaining service quality for tasks.Extensive experimentation demonstrates that our proposed EA-DFPSO algorithm outperforms the existing traditional scheduling algorithms to achieve reduced task completion time and conserve energy in an edge computing environment.

Attribute Reduction with Test Cost Constraint

In many machine learning applications,data are not free,and there is a test cost for each data item. For the economical reason,some existing works try to minimize the test cost and at the same time,preserve a particular property of a given decision system. In this paper,we point out that the test cost one can afford is limited in some applications. Hence,one has to sacrifice respective properties to keep the test cost under a budget. To formalize this issue,we define the test cost constraint attribute reduction problem,where the optimization objective is to minimize the conditional information entropy. This problem is an essential generalization of both the test-cost-sensitive attribute reduction problem and the 0-1 knapsack problem,therefore it is more challenging. We propose a heuristic algorithm based on the information gain and test costs to deal with the new problem. The algorithm is tested on four UCI（University of California-Irvine） datasets with various test cost settings. Experimental results indicate the appropriate setting of the only user-specified parameter λ.

Traffic assignment problem under tradable credit scheme in a bi-modal stochastic transportation network: A cumulative prospect theory approach

The traffic equilibrium assignment problem under tradable credit scheme(TCS) in a bi-modal stochastic transportation network is investigated in this paper. To describe traveler’s risk-taking behaviors under uncertainty, the cumulative prospect theory(CPT) is adopted. Travelers are assumed to choose the paths with the minimum perceived generalized path costs, consisting of time prospect value(PV) and monetary cost. At equilibrium with a given TCS, the endogenous reference points and credit price remain constant, and are consistent with the equilibrium flow pattern and the corresponding travel time distributions of road sub-network. To describe such an equilibrium state, the CPT-based stochastic user equilibrium(SUE) conditions can be formulated under TCS. An equivalent variational inequality(VI) model embedding a parameterized fixed point(FP) model is then established, with its properties analyzed theoretically. A heuristic solution algorithm is developed to solve the model, which contains two-layer iterations. The outer iteration is a bisection-based contraction method to find the equilibrium credit price, and the inner iteration is essentially the method of successive averages(MSA) to determine the corresponding CPT-based SUE network flow pattern. Numerical experiments are provided to validate the model and algorithm.

Selection of regression models for predicting strength and deformability properties of rocks using GA

Recently,many regression models have been presented for prediction of mechanical parameters of rocks regarding to rock index properties.Although statistical analysis is a common method for developing regression models,but still selection of suitable transformation of the independent variables in a regression model is diffcult.In this paper,a genetic algorithm(GA)has been employed as a heuristic search method for selection of best transformation of the independent variables(some index properties of rocks)in regression models for prediction of uniaxial compressive strength(UCS)and modulus of elasticity(E).Firstly,multiple linear regression(MLR)analysis was performed on a data set to establish predictive models.Then,two GA models were developed in which root mean squared error(RMSE)was defned as ftness function.Results have shown that GA models are more precise than MLR models and are able to explain the relation between the intrinsic strength/elasticity properties and index properties of rocks by simple formulation and accepted accuracy.