FMS scheduling based on timed Petri Net model and reactive graph search

This paper presents a new scheduling method for manufacturing system based on the Timed Petri Net model and a reactive fast graph search algorithm. The following two typical problems are addressed in this paper. (1) Minimization of the maximum completion time. (2) Minimization of the total tardiness. As for the problem (1), a new search algorithm which combines the RTA^∗ and a rule-based supervisor is proposed. As for problem (2), the original Petri Net model is converted to its reverse model and the algorithm developed for the problem (1) is applied, regarding the due date as the starting time in the reverse model. Some numerical experiments are carried out to demonstrate usefulness of our algorithm.     

Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem

We consider the problem of maintaining a dynamic ordered set of n integers in a universe U under the operations of insertion, deletion and predecessor queries. The computation model used is a unit-cost RAM, with a word length of w bits, and the universe size is |U|=2^w. We present a data structure that uses O(|U|/log|U|+n) space, performs all the operations in O(loglog|U|) time and needs O(loglog|U|/logloglog|U|) structural changes per update operation. The data structure is a simplified version of the van Emde Boas' tree introducing, in its construction and functioning, new concepts, which help to keep the important information for searching along the path of the tree, in a more compact and organized way.     

Simplest optimal cutting patterns for equal rectangles

This paper presents branch-and-bound algorithms that can guarantee the simplest optimal cutting patterns of equal rectangles. An existing linear algorithm determines the global upper bound exactly. The branching process ends when a branch of a lower bound equal to the global upper bound is found.     

Banach空间二阶周期边值问题解的存在性

利用一些比较结果，讨论了Banach空间中二阶周期边值问题解的存在性，获得了若干解的存在性与唯一性结果。     

Multiplicity results for positive solutions of some semi-positone three-point boundary value problems

In this paper, some multiplicity results for positive solutions of some singular semi-positone three-point boundary value problem be obtained by using the fixed point index method.     

Existence of two solutions of m-point boundary value problem for second order dynamic equations on time scales

In this paper, by means of a new twin fixed-point theorem in a cone, the existence of at least two positive solutions of m-point boundary value problem for second order dynamic equations on time scales is considered.     

Improved bounds for some nonstandard problems in generalized heat conduction

We consider the Maxwell-Cattaneo system of equations for generalized heat conduction where the temperature and heat flux satisfy a nonstandard auxiliary condition which prescribes a combination of their values initially and at a later time. We obtain L₂ bounds for the temperature and heat flux by means of Lagrange identities. These bounds extend the range of validity for the parameter in the nonstandard condition under a constraint on the coefficients in the differential equations.     

A two-stage parallel branch and bound algorithm for mixed integer programs

Mixed integer programming (MIP) models are extensively usedto aid strategic and tactical decision making in many businesssectors. Solving MIP models is a computationally intensive processand there is a need to develop solution approaches that enablelarger models to be solved within acceptable timeframes. Inthis paper, we describe the implementation of a two-stage parallelbranch and bound (PB & B) algorithm for MIP. In stage 1of the algorithm, a multiple heuristic search is implementedin which a number of alternative search trees are investigatedusing a forest search in the hope of finding a good solutionquickly. In stage 2, the search is reorganized so that the branchesof a chosen tree are investigated in parallel. A new heuristicis introduced, based on a best projection criterion, which evaluatesalternative B & B trees in order to choose one for investigationin stage 2 of the algorithm. The heuristic also serves as away of implementing a quality load balancing scheme for stage2 of the algorithm. The results of experimental investigationsare reported for a range of models taken from the MIPLIB libraryof benchmark problems.     

Convergence estimates of Galerkin-wavelet solutions to a Cauchy problem for a class of periodic pseudodifferential equations

A class of Cauchy problems for interesting complicated periodic pseudodifferential equations is considered. By the Galerkin-wavelet method and with weak solutions one can find sufficient conditions to establish convergence estimates of weak Galerkin-wavelet solutions to a Cauchy problem for this class of equations.

     

Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem

In this work, the NP-hard maximum clique problem on graphs is considered. Starting from basic greedy heuristics, modifications and improvements are proposed and combined in a two-phase heuristic procedure. In the first phase an improved greedy procedure is applied starting from each node of the graph; on the basis of the results of this phase a reduced subset of nodes is selected and an adaptive greedy algorithm is repeatedly started to build cliques around such nodes. In each restart the selection of nodes is biased by the maximal clique generated in the previous execution. Computational results are reported on the DIMACS benchmarks suite. Remarkably, the two-phase procedure successfully solves the difficult Brockington-Culberson instances, and is generally competitive with state-of-the-art much more complex heuristics.