Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems

A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.

OPTIMALITY CONDITIONS AND DUALITY RESULTS FOR NONSMOOTH VECTOR OPTIMIZATION PROBLEMS WITH THE MULTIPLE INTERVAL-VALUED OBJECTIVE FUNCTION

In this paper, both Fritz John and Karush-Kuhn-Tucker necessary optimality conditions are established for a （weakly） LU-efficient solution in the considered nonsmooth multiobjective programming problem with the multiple interval-objective function. Further, the sufficient optimality conditions for a （weakly） LU-efficient solution and several duality results in Mond-Weir sense are proved under assumptions that the functions constituting the considered nondifferentiable multiobjective programming problem with the multiple interval- objective function are convex.

Numerical Comparison Research on the Solution of Stress Intensity Factors of Multiple Crack Problems

A newly developed approach without crack surface discretization for modeling 2D solids with large number of cracks in linear elastic fracture mechanics is proposed with the eigen crack opening displacement (COD) boundary integral equations in this paper. The eigen COD is defined as a crack in an infinite domain under fictitious traction acting on the crack surface. Respect to the computational accuracies and efficiencies, the multiple crack problems in finite and infinite plates are solved and compared numerically using three different kinds of boundary integral equations (BIEs): 1) the dual BIEs require crack surface discretization;2) the BIEs with numerical Green’s functions (NGF) without crack surface discretization, but have to solve a complementary matrix;3) the eigen crack opening displacement (COD) BIEs in the present paper. With the concept of eigen COD, the multiple crack problems can be solved by using a conventional displacement discontinuity boundary integral equation in an iterative fashion with a small size of system matrix as that in the NGF approach, but without troubles to determine the complementary matrix. Solution of the stress intensity factors of multiple crack problems is solved and compared in some numerical examples using the above three computational algorithms. Numerical results clearly demonstrate the numerical models of eigen COD BIEs have much higher efficiency, providing a newly numerical technique for multiple crack problems. Not only the accuracy and efficiency of computation can be guaranteed, but also the overall properties and local details can be obtained. In conclusion, the numerical models of eigen COD BIEs realize the simulations for multiple crack problems with large quantity of cracks.

High order multiplication perturbation method for singular perturbation problems

This paper presents a high order multiplication perturbation method for sin- gularly perturbed two-point boundary value problems with the boundary layer at one end. By the theory of singular perturbations, the singularly perturbed two-point boundary value problems are first transformed into the singularly perturbed initial value problems. With the variable coefficient dimensional expanding, the non-homogeneous ordinary dif- ferential equations （ODEs） are transformed into the homogeneous ODEs, which are then solved by the high order multiplication perturbation method. Some linear and nonlinear numerical examples show that the proposed method has high precision.

Collision-free Scheduling of Multi-bridge Machining Systems： A Colored Traveling Salesman Problem-based Approach

Multi-bridge machining systems(MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially overlapping workspaces.Their scheduling problems can be abstracted into a serial-colored travelling salesman problem in which each salesman has some exclusive cities and some cities shared with its neighbor(s). To solve it, we develop a greedy algorithm that selects a neighboring city satisfying proximity. The algorithm allows a salesman to select randomly its shared cities and runs accordingly many times. It can thus be used to solve job scheduling problems for MBMS. Subsequently, a collision-free scheduling method is proposed to address both job scheduling and collision resolution issues of MBMS. It is an extension of the greedy algorithm by introducing time window constraints and a collision resolution mechanism. Thus, the augmented greedy algorithm can try its best to select stepwise a job for an individual machine such that no time overlaps exist between it and the job sequence of the neighboring machine dealt in the corresponding overlapping workspace; and remove such a time overlap only when it is inevitable. Finally, we conduct a case study of a large triplebridge waterjet cutting system by applying the proposed method.

K-DSA for the multiple traveling salesman problem

Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering method to divide all cities into several categories based on the center of various samples;the large-scale MTSP is divided into multiple separate traveling salesman problems(TSPs),and the TSP is solved through the DSA.The proposed algorithm adopts a solution strategy of clustering first and then carrying out,which can not only greatly reduce the search space of the algorithm but also make the search space more fully explored so that the optimal solution of the problem can be more quickly obtained.The experimental results from solving several test cases in the TSPLIB database show that compared with other related intelligent algorithms,the K-DSA has good solving performance and computational efficiency in MTSPs of different scales,especially with large-scale MTSP and when the convergence speed is faster;thus,the advantages of this algorithm are more obvious compared to other algorithms.

Multi-target tracking algorithm of boost-phase ballistic missile defense

Considering the problem of multiple ballistic missiles tracking of boost-phase ballistic missile defense, a boost-phase tracking algorithm based on multiple hypotheses tracking （MHT） concept is proposed. This paper focuses on the tracking algo- rithm for hypothesis generation, hypothesis probability calculation, hypotheses reduction and pruning and other sectors. From an engineering point of view, a technique called the linear assignment problem （LAP） used in the implementation of M-best feasible hypotheses generation, the number of the hypotheses is relatively small compared with the total number that may exist in each scan, also the N-scan back pruning is used, the algorithm＇s efficiency and practicality have been improved. Monte Carlo simulation results show that the proposed algorithm can track the boost phase of multiple ballistic missiles and it has a good tracking performance compared with joint probability data association （JPDA）.

Generalized multiple time windows model based parallel machine scheduling for TDRSS

The scheduling efficiency of the tracking and data relay satellite system（TDRSS）is strictly limited by the scheduling degrees of freedom（DoF）,including time DoF defined by jobs＇ flexible time windows and spatial DoF brought by multiple servable tracking and data relay satellites（TDRSs）.In this paper,ageneralized multiple time windows（GMTW）model is proposed to fully exploit the time and spatial DoF.Then,the improvements of service capability and job-completion probability based on the GMTW are theoretically proved.Further,an asymmetric path-relinking（APR）based heuristic job scheduling framework is presented to maximize the usage of DoF provided by the GMTW.Simulation results show that by using our proposal 11%improvement of average jobcompletion probability can be obtained.Meanwhile,the computing time of the time-to-target can be shorten to 1/9 of the GRASP.

SEMI-DEFINITE RELAXATION ALGORITHM OF MULTIPLE KNAPSACK PROBLEM

The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity Ci.The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .

Learning-Based Metaheuristic Approach for Home Healthcare Optimization Problem

This research focuses on the home health care optimization problem that involves staff routing and scheduling problems.The considered problem is an extension of multiple travelling salesman problem.It consists of finding the shortest path for a set of caregivers visiting a set of patients at their homes in order to perform various tasks during a given horizon.Thus,a mixed-integer linear programming model is proposed to minimize the overall service time performed by all caregivers while respecting the workload balancing constraint.Nevertheless,when the time horizon become large,practical-sized instances become very difficult to solve in a reasonable computational time.Therefore,a new Learning Genetic Algorithm for mTSP(LGA-mTSP)is proposed to solve the problem.LGA-mTSP is composed of a new genetic algorithm for mTSP,combined with a learning approach,called learning curves.Learning refers to that caregivers’productivity increases as they gain more experience.Learning curves approach is considered as a way to save time and costs.Simulation results show the efficiency of the proposed approach and the impact of learning curve strategy to reduce service times.

Multiplicity Results for a Fourth-Order Boundary Value Problem

This paper deals with multiplicity results for nonlinear elastic equations of the type wheree∈L￣2(0,1),g:[0,1]×R×R→R is a bounded contimuous function.and the pair(α,β)satisfiesand

Solving Low-Density Multiple Subset Sum Problems with SVP Oracle

It is well known that almost all subset sum problems with density less than 0.9408… can be solved in polynomial time with an SVP oracle that can find a shortest vector in a special lattice.In this paper,the authors show that a similar result holds for the k-multiple subset sum problem which has k subset sum problems with exactly the same solution.Specially,for the single subset sum problem(k=1),a modified lattice is introduced to make the proposed analysis much simpler and the bound for the success probability tighter than before.Moreover,some extended versions of the multiple subset sum problem are also considered.

GPS： a constraint-based gene position procurement in chromosome for solving large-scale multiobjective multiple knapsack problems

The multiple knapsack problem （MKP） forms a base for resolving many real-life problems. This has also been considered with multiple objectives in genetic algorithms （GAs） for proving its efficiency. GAs use self- adaptability to effectively solve complex problems with constraints, but in certain cases, self-adaptability fails by converging toward an infeasible region. This pitfall can be resolved by using different existing repairing techniques; however, this cannot assure convergence toward attaining the optimal solution. To overcome this issue, gene position-based suppression （GPS） has been modeled and embedded as a new phase in a classical GA. This phase works on the genes of a newly generated individual after the recombination phase to retain the solution vector within its feasible region and to im- prove the solution vector to attain the optimal solution. Genes holding the highest expressibility are reserved into a subset, as the best genes identified from the current individuals by re- placing the weaker genes from the subset. This subset is used by the next generated individual to improve the solution vec- tor and to retain the best genes of the individuals. Each gene＇s positional point and its genotype exposure for each region in an environment are used to fit the best unique genes. Further, suppression of expression in conflicting gene＇s relies on the requirement toward the level of exposure in the environment or in eliminating the duplicate genes from the environment.The MKP benchmark instances from the OR-library are taken for the experiment to test the new model. The outcome por- trays that GPS in a classical GA is superior in most of the cases compared to the other existing repairing techniques.

MULTIPLE PARAMETERS IDENTIFICATION PROBLEMS IN RESISTIVITY WELL-LOGGING

In petroleum exploitation, the main aim of resistivity well-logging is to determine the resistivity of the layers by measuring the potential on the electrodes. This mathematical problem can be described as an inverse problem for the elliptic equivalued surface boundary value problem. In this paper, the author gets the expression of the derivative functions of the potential on the electrodes with respect to the resistivity of the layers. This allows us to solve the identification problem of the resistivity of the layers.

A Distributed Cooperative Dynamic Task Planning Algorithm for Multiple Satellites Based on Multi-agent Hybrid Learning

Traditionally, heuristic re-planning algorithms are used to tackle the problem of dynamic task planning for multiple satellites. However, the traditional heuristic strategies depend on the concrete tasks, which often affect the result’s optimality. Noticing that the historical information of cooperative task planning will impact the latter planning results, we propose a hybrid learning algorithm for dynamic multi-satellite task planning, which is based on the multi-agent reinforcement learning of policy iteration and the transfer learning. The reinforcement learning strategy of each satellite is described with neural networks. The policy neural network individuals with the best topological structure and weights are found by applying co-evolutionary search iteratively. To avoid the failure of the historical learning caused by the randomly occurring observation requests, a novel approach is proposed to balance the quality and efficiency of the task planning, which converts the historical learning strategy to the current initial learning strategy by applying the transfer learning algorithm. The simulations and analysis show the feasibility and adaptability of the proposed approach especially for the situation with randomly occurring observation requests.

Efficient Multi-Tenant Virtual Machine Allocation in Cloud Data Centers

Virtual Machine（VM） allocation for multiple tenants is an important and challenging problem to provide efficient infrastructure services in cloud data centers. Tenants run applications on their allocated VMs, and the network distance between a tenant＇s VMs may considerably impact the tenant＇s Quality of Service（Qo S）. In this study, we define and formulate the multi-tenant VM allocation problem in cloud data centers, considering the VM requirements of different tenants, and introducing the allocation goal of minimizing the sum of the VMs＇ network diameters of all tenants. Then, we propose a Layered Progressive resource allocation algorithm for multi-tenant cloud data centers based on the Multiple Knapsack Problem（LP-MKP）. The LP-MKP algorithm uses a multi-stage layered progressive method for multi-tenant VM allocation and efficiently handles unprocessed tenants at each stage. This reduces resource fragmentation in cloud data centers, decreases the differences in the Qo S among tenants, and improves tenants＇ overall Qo S in cloud data centers. We perform experiments to evaluate the LP-MKP algorithm and demonstrate that it can provide significant gains over other allocation algorithms.

Solving Resource-constrained Multiple Project Scheduling Problem Using Timed Colored Petri Nets

To solve the resource-constrained multiple project scheduling problem(RCMPSP) more effectively,a method based on timed colored Petri net(TCPN) was proposed.In this methodology,firstly a novel mapping mechanism between traditional network diagram such as CPM(critical path method)/PERT(program evaluation and review technique) and TCPN was presented.Then a primary TCPN(PTCPN) for solving RCMPSP was modeled based on the proposed mapping mechanism.Meanwhile,the object PTCPN was used to simulate the multiple projects scheduling and to find the approximately optimal value of RCMPSP.Finally,the performance of the proposed approach for solving RCMPSP was validated by executing a mould manufacturing example.

A GLOBALLY CONVERGENT ALGORITHM FOR THE EUCLIDEAN MULTIPLICITY LOCATION PROBLEM

The Euclidean single facility location problem (ESFL) and the Euclidean multiplicity lo-cation problem (EMFL) are two special nonsmooth convex programming problems which haveattracted a largr literature. For the ESFL problem. there are algorithms which converge bothglobally and quadratically For the EMFL problem, there are some quadratically convergentalgorithms. but for global convergencel they all need nontrivial assumptions on the problem.In this paper, we present an algorithm for EMFL. With no assumption on the problem, it isproved that from any initial point, this algorithm generates a sequence of points which convergesto the closed convex set of optimal solutions of EMFL.

Multiplicity and Uniqueness of Positive Solutions for Nonhomogeneous Semilinear Elliptic Equation with Critical Exponent

In this paper,we consider the following problem {-Δu（x）＋u（x）=λ（u^p（x）＋h（x））,x∈R^N,u（x）∈h^1（R^N）,u（x）〉0,x∈R^N,（＊）where λ 〉 0 is a parameter,p =（N＋2）/（N—2）.We will prove that there exists a positive constant 0 〈 A＊ 〈 ＋00such that（＊） has a minimal positive solution for λ∈（0,λ＊）,no solution for λ 〉 λ＊,a unique solution for λ = λ＊.Furthermore,（＊） possesses at least two positive solutions when λ∈（0,λ＊） and 3 ≤ N ≤ 5.For N ≥ 6,under some monotonicity conditions of h we show that there exists a constant 0 〈λ＊＊ 〈 λ＊ such that problem（＊）possesses a unique solution for λ∈（0,λ＊＊）.

Reducing problem of multiplication operators on Bergman space

THE L_a^2(D) refers to Bergman space on D, where D is the unit disk on the complex plane. Using the super-isometric dilation technique, we obtain the following results. Proposition 1. The multiplication operator M_φ on Bergman space L_a^2 (D) is unitarily equivalent to the compression of the direct sum of 2N-1 copies of Bergman shift, where φ is a Blaschke product of order N (【∞).