Resource Allocation Using Timed Petri Nets and Heuristic Search

Traditional models for project management have not adequately incorporated a number of factors that are important for resource allocation. This paper proposed a unified timed Petri net model in which scheduling and planning were collectively carried out to take full advantages of the flexibility of the FMS. Through the lens of system theory, two types of resources were distinguished: major role and auxiliary role, and the major role was used to construct the FMS' Petri net. The method simplified the Petri net's construction and gave a clear flow chart for scheduling. Hence, the auxiliary resource allocation could be easily carried out according to the schedule, which was proposed by heuristic search algorithm. At last, the efficacy of the Petri net model for online scheduling in a resource constrained environment was discussed.

Improved methods for scheduling flexible manufacturing systems based on Petri nets and heuristic search

This paper proposes and evaluates two improved Petri net （PN）-based hybrid search strategies and their applications to flexible manufacturing system （FMS） scheduling. The algorithms proposed in some previous papers, which combine PN simulation capabilities with A＊ heuristic search within the PN reachability graph,may not find an optimum solution even with an admissible heuristic function. To remedy the defects an improved heuristic search strategy is proposed, which adopts a different method for selecting the promising markings and reserves the admissibility of the algorithm. To speed up the search process, another algorithm is also proposed which invokes faster termination conditions and still guarantees that the solution found is optimum. The scheduling results are compared through a simple FMS between our algorithms and the previous methods. They are also applied and evaluated in a set of randomly-generated FMSs with such characteristics as multiple resources and alternative routes.

Hyper-Distributed Hyper-Parallel Implementation of Heuristic Search ofImplicit AND/OR Graph

This paper presents the hierarchic chaotic cellular networks for the hardware implementation of hyper-distributed hyper-parallel intelligent problem solving based on competitive wave propagation. By using the bifurcation and the synchronization of distributed chaotic dynamic systems, and by improving the Chua's circuit, the mechanism and the algorithms of heuristic search of an implicit AND/OR graph are realized in a hyper-distributed hyper-parallel environment. This paper's approach has many advantages in comparison with other traditional systolic structures based on symbolic logic algorithms.

A Fast Insertion Tabu Search with Conflict-Avoidance Heuristic for the Multisatellite Multimode Crosslink Scheduling Problem

An agile earth-observing satellite equipped with multimode cameras capable of transmitting observation data to other satellites is developed to rapidly respond to requests with multiple observation modes.This gives rise to the Multisatellite Multimode Crosslink Scheduling(MMCS)problem,which involves allocating observation requests to agile satellites,selecting appropriate timing and observation modes for the requests,and transmitting the data to the ground station via the satellite communication system.Herein,a mixed integer programming model is introduced to include all complex time and operation constraints.To solve the MMCS problem,a two-stage heuristic method,called Fast insertion Tabu Search with Conflict-avoidance(FTS-C)heuristic,is developed.In the first stage,a conflict-avoidance insertion algorithm is designed to generate a high-quality initial solution by considering the requests transmission and download.Further,the tabu search-based second stage optimizes the initial solution.Finally,an extensive empirical study based on a real-world situation demonstrates that FTS-C can generate a solution with higher quality in less time than other state-of-the-art algorithms and the CPLEX solver.

RESEARCH ON JUMPING SEQUENCE PLANNING ISSUES OF HOPPING ROBOTS

The wheeled or crawled robots often suffer from big obstacles or ditches, so a hopping robot needs to fit the tough landform in the field environments. In order to jump over obstacles rapidly, a jumping sequence must be generated based on the landform information from sensors or user input. The planning method for planar mobile robots is compared with that of hopping robots. Several factors can change the planning result. Adjusting these coefficients, a heuristic searching algorithm for the jumping sequence is developed on a simplified landform. Calculational result indicates that the algorithm can achieve safety and efficient control sequences for a desired goal.

Algorithms for Multicriteria Scheduling Problems to Minimize Maximum Late Work, Tardy, and Early

This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (Vmax), maximum tardy job, denoted by (Tmax), and maximum earliness (Emax). We propose several algorithms based on types of objectives function to be optimized when dealing with simultaneous minimization problems with and without weight and hierarchical minimization problems. The proposed Algorithm (3) is to find the set of efficient solutions for 1//F (Vmax, Tmax, Emax) and 1//(Vmax + Tmax + Emax). The Local Search Heuristic Methods (Descent Method (DM), Simulated Annealing (SA), Genetic Algorithm (GA), and the Tree Type Heuristics Method (TTHM) are applied to solve all suggested problems. Finally, the experimental results of Algorithm (3) are compared with the results of the Branch and Bound (BAB) method for optimal and Pareto optimal solutions for smaller instance sizes and compared to the Local Search Heuristic Methods for large instance sizes. These results ensure the efficiency of Algorithm (3) in a reasonable time.

MODELING OF ROBOT MANIPULATOR AND OBSTACLE AVOIDANCE

A robot intelligent path planning system RIPPS is developed, which can be utilized for a robot off line programming tool. The system consists of three parts: geometric modeler, kinematic modeler and path planer. The geometric modeler is used to construct the robot working environment cluttered with obstacles and the robot kinematic modeler to define robot manipulators by the input parameters. Giving robot start and the goal configurations, the path planer can produce a quasi optimal path. By transforming obstacles into the C space to form C obstacles, the path searching is performed in C space. The planning simulations are performed on a SGI workstation, the future research is to implement the planer on a commercial robot manipulators.

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.

APU-D* Lite: Attack Planning under Uncertainty Based on D* Lite

With serious cybersecurity situations and frequent network attacks,the demands for automated pentests continue to increase,and the key issue lies in attack planning.Considering the limited viewpoint of the attacker,attack planning under uncertainty is more suitable and practical for pentesting than is the traditional planning approach,but it also poses some challenges.To address the efficiency problem in uncertainty planning,we propose the APU-D*Lite algorithm in this paper.First,the pentest framework is mapped to the planning problem with the Planning Domain Definition Language(PDDL).Next,we develop the pentest information graph to organize network information and assess relevant exploitation actions,which helps to simplify the problem scale.Then,the APU-D*Lite algorithm is introduced based on the idea of incremental heuristic searching.This method plans for both hosts and actions,which meets the requirements of pentesting.With the pentest information graph as the input,the output is an alternating host and action sequence.In experiments,we use the attack success rate to represent the uncertainty level of the environment.The result shows that APU-D*Lite displays better reliability and efficiency than classical planning algorithms at different attack success rates.

Robust optimization for volume variation in timber processing

Volume variation is an uncertainty element which affects timber processing. We studied the volume variation of logs caused by quality defects in traditional timber processing and set up an optimization approach,using a robust optimization method. We used total number of acceptable boards produced to study the relationship between board thickness and raw material logs, using a heuristic search algorithm to control the variation of board volume to improve the output of boards, reduce the quantity of by-products, and lower production costs. The robust optimization method can effectively control the impact of volume variations in timber processing, reduce cutting waste as far as possible using incremental processing and increase profits, maximize the utilization ratio of timber, prevent waste in processing, cultivate the productive type of tree species and save forest resources.

New Heuristic Distributed Parallel Algorithms for Searching and Planning

This paper proposes new heuristic distributed parallel algorithms for search-ing and planning, which are based on the concepts of wave concurrent prop-agations and competitive activation mechanisms. These algorithms are char-acterized by simplicity and clearness of control strategies for searching, anddistinguished abilities in many aspects, such as high speed processing, widesuitability for searching AND/OR implicit graphs, and ease in hardware imple-mentation.

Grid-Based Path Planner Using Multivariant Optimization Algorithm

To solve the shortest path planning problems on grid-based map efficiently,a novel heuristic path planning approach based on an intelligent swarm optimization method called Multivariant Optimization Algorithm( MOA) and a modified indirect encoding scheme are proposed. In MOA,the solution space is iteratively searched through global exploration and local exploitation by intelligent searching individuals,who are named as atoms. MOA is employed to locate the shortest path through iterations of global path planning and local path refinements in the proposed path planning approach. In each iteration,a group of global atoms are employed to perform the global path planning aiming at finding some candidate paths rapidly and then a group of local atoms are allotted to each candidate path for refinement. Further,the traditional indirect encoding scheme is modified to reduce the possibility of constructing an infeasible path from an array. Comparative experiments against two other frequently use intelligent optimization approaches: Genetic Algorithm( GA) and Particle Swarm Optimization( PSO) are conducted on benchmark test problems of varying complexity to evaluate the performance of MOA. The results demonstrate that MOA outperforms GA and PSO in terms of optimality indicated by the length of the located path.

Application of Rollout Strategy to Test Points Selection for Integer-Coded Fault Wise Table

Test points selection for integer-coded fault wise table is a discrete optimization problem. The global minimum set of test points can only be guaranteed by an exhaustive search which is eompurationally expensive. In this paper, this problem is formulated as a heuristic depth-first graph search problem at first. The graph node expanding method and rules are given. Then, rollout strategies are applied, which can be combined with the heuristic graph search algorithms, in a computationally more efficient manner than the optimal strategies, to obtain solutions superior to those using the greedy heuristic algorithms. The proposed rollout-based test points selection algorithm is illustrated and tested using an analog circuit and a set of simulated integer-coded fault wise tables. Computa- tional results are shown, which suggest that the rollout strategy policies are significantly better than other strategies.

Mixture test strategy optimization for analog systems

Since analog systems play an essential role in modern equipment,test strategy optimization for analog systems has attracted extensive attention in both academia and industry.Although many methods exist for the implementation of effective test strategies,diagnosis for analog systems suffers from the impacts of various stresses due to sophisticated mechanism and variable operational conditions.Consequently,the generated solutions are impractical due to the systems’topology and influence of information redundancy.Additionally,independent tests operating sequentially on the generated strategies may increase the time consumption.To overcome the above weaknesses,we propose a novel approach called heuristic programming(HP)to generate a mixture of test strategies.The experimental results prove that HP and Rollout-HP access the strategy with fewer layers and lower cost consumption than state-of-the-art methods.Both HP and Rollout-HP provide more practical strategies than other methods.Additionally,the cost consumption of the strategy based on HP and Rollout-HP is improved compared with those of other methods because of the updating of the test cost and adaptation of mixture OR nodes.Hence,the proposed HP and Rollout-HP methods have high efficiency.

Predicting the effects of selected reservoir petrophysical properties on bottomhole pressure via three computational intelligence techniques

This study investigates the effects of selected petrophysical properties on predicting flowing well bottomhole pressure.To efficiently situate the essence of this investigation,genetic,imperialist competitive and whale optimization algorithms were used in predicting the bottomhole pressure of a reservoir using production data and some selected petrophysical properties as independent input variables.A total of 15,633 data sets were collected from Volvo field in Norway,and after screening the data,a total of 9161 data sets were used to develop apt computational intelligence models.The data were randomly divided into three different groups:training,validation,and testing data.Two case scenarios were considered in this study.The first scenario involved the prediction of flowing bottomhole pressure using only eleven independent variables,while the second scenario bothered on the prediction of the same flowing bottomhole pressure using the same independent variables and two selected petrophysical properties(porosity and permeability).Each of the two scenarios involved as implied in the first scenario,the use of three(3)heuristic search optimizers to determine optimal model architectures.The optimizers were allowed to choose the optimal number of layers(between 1 and 10),the optimal number of nodal points(between 10 and 100)for each layer and the optimal learning rate required per task/operation.the results,showed that the models were able to learn the problems well with the learning rate fixed from 0.001 to 0.0001,although this became successively slower as the leaning rate decreased.With the chosen model configuration,the results suggest that a moderate learning rate of 0.0001 results in good model performance on the trained and tested data sets.Comparing the three heuristic search optimizers based on minimum MSE,RMSE,MAE and highest coefficient of determination(R^(2))for the actual and predicted values,shows that the imperialist competitive algorithm optimizer predicted the flowing bottomhole pressure most accurately relative to the genetic and whale optimization algorithm optimizers.

COURSE TIMETABLING AT A TUNISIAN UNIVERSITY:A CASE STUDY

This paper deals with the Course Timetabling Problem at an institution in a Tunisian University. We introduce a heuristic procedure to construct a feasible timetable for all lectures and tutorials taken by different groups of each sub-section of any section. We describe the timetabling problem using a list of all specific hard and soft constraints. We formulate the problem as a set of linear constraints using two sets of binary variables corresponding to lectures and tutorials, respectively. This heuristic is illustrated with real data for a sub-section of the Faculty of Economics and Management Sciences of Sfax in Tunisia, and the resulting timetables are compared with those generated manually. The results of another full section have confirmed the good quality of the proposed heuristic when compared with the hand made solution.

Test sequencing problem arising at the design stage for reducing life cycle cost

Previous test sequencing algorithms only consider the execution cost of a test at the application stage. Due to the fact that the placement cost of some tests at the design stage is considerably high compared with the execution cost, the sequential diagnosis strategy obtained by previous methods is actually not optimal from the view of life cycle. In this paper, the test sequencing problem based on life cycle cost is presented. It is formulated as an optimization problem, which is non-deterministic polynomial-time hard （NP-hard）. An algorithm and a strategy to improve its computational efficiency are proposed. The formulation and algorithms are tested on various simulated systems and comparisons are made with the extant test sequencing methods. Application on a pump rotational speed control （PRSC） system of a spacecraft is studied in detail. Both the simulation results and the real-world case application results suggest that the solution proposed in this paper can significantly reduce the life cycle cost of a sequential fault diagnosis strategy.

Concurrent Competitive Wave Approach toHyper-Distributed Hyper-Parallel AIProcessing

This paper preseflts a new approach of the synchronous homogeneous concurrent propagation of competitive waves for the purpose of hyper-distributed hyper-parallel heuristic problem-solving. The concurrent algorithm, mechanism and their properties are given. In comparison with the traditional AI algorithms, the approach is featured by the knowledge-based problem-solving in the distributed parallel environment, the feasibility for hardware implementation and the various applications.

Asynchronous Heterogeneous Mechanism for Hyper-Distributed Hyper-Parallel Al Processing

This paper proposes an asynchronous heterogeneous propagation approach of concurrent competitive waves for hyper-distributed hyper-parallel heuris tic problem-solving. This approach is much more powerful than the synchronous homogeneous mechanisms and the asynchronous superimposition algorithms, and has universal validity and availability. The basic conception, concurrent algorithm and its properties are discussed. The theory and conclusions drawn in this paper are of essential importance for the hardware implementation of hyper-distributed hyper-parallel processing based on chaotic cellular networks.

Modeling and Solving Material Resources Allocation and Distribution with OR-Based and AI-Guided Method

ＭｏｄｅｌｉｎｇａｎｄＳｏｌｖｉｎｇＭａｔｅｒｉａｌＲｅｓｏｕｒｃｅｓＡｌｏｃａｔｉｏｎａｎｄＤｉｓｔｒｉｂｕｔｉｏｎｗｉｔｈＯＲ┐ＢａｓｅｄａｎｄＡＩ┐ＧｕｉｄｅｄＭｅｔｈｏｄ⒇ＣＨＥＮＸｕｅｇｕａｎｇ＊ＬＵＫｅＦＥＩＱｉＨｕａｚｈｏｎｇＵｎｉｖｅ...