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.

On the “Onion Husk” Algorithm for Approximate Solution of the Traveling Salesman Problem

The paper describes some implementation aspects of an algorithm for approximate solution of the traveling salesman problem based on the construction of convex closed contours on the initial set of points (“cities”) and their subsequent combination into a closed path (the so-called contour algorithm or “onion husk” algorithm). A number of heuristics related to the different stages of the algorithm are considered, and various variants of the algorithm based on these heuristics are analyzed. Sets of randomly generated points of different sizes (from 4 to 90 and from 500 to 10,000) were used to test the algorithms. The numerical results obtained are compared with the results of two well-known combinatorial optimization algorithms, namely the algorithm based on the branch and bound method and the simulated annealing algorithm. .

Optimal subcarrier allocation for cognitive radio with multi-user OFDM and distributed antenna

The subcarrier allocation problem in cognitive radio（CR）networks with multi-user orthogonal frequency-division multiplexing（OFDM）and distributed antenna is analyzed and modeled for the flat fading channel and the frequency selective channel,where the constraint on the secondary user（SU）to protect the primary user（PU）is that the total throughput of each PU must be above the given threshold instead of the ＂interference temperature＂.According to the features of different types of channels,the optimal subcarrier allocation schemes are proposed to pursue efficiency（or maximal throughput）,using the branch and bound algorithm and the 0-1 implicit enumeration algorithm.Furthermore,considering the tradeoff between efficiency and fairness,the optimal subcarrier allocation schemes with fairness are proposed in different fading channels,using the pegging algorithm.Extensive simulation results illustrate the significant performance improvement of the proposed subcarrier allocation schemes compared with the existing ones in different scenarios.

An Integrated Tool for Power/Ground Network Design, Optimization,and Verification for Cell Based VLSIs

A CAD tool based on a group of efficient algorithms to verify,design,and optimize power/ground networks for standard cell model is presented.Nonlinear programming techniques,branch and bound algorithms and incomplete Cholesky decomposition conjugate gradient method (ICCG) are the three main parts of our work.Users can choose nonlinear programming method or branch and bound algorithm to satisfy their different requirements of precision and speed.The experimental results prove that the algorithms can run very fast with lower wiring resources consumption.As a result,the CAD tool based on these algorithms is able to cope with large-scale circuits.

Dominance rules for single machine schedule with sequence dependent setup and due date

Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz＇ s branch and bound scheme are developed including the dominance rules where the objective is to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.

Intelligent test case generation based on branch and bound

Path-oriented test case generation is in essence a constraint satisfaction problem （CSP） solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound （BB） is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms.

Maximum-likelihood detection based on branch and bound algorithm for MIMO systems

Maximum likelihood detection for MIMO systems can be formulated as an integer quadratic programming problem. In this paper, we introduce depth-first branch and bound algorithm with variable dichotomy into MIMO detection. More nodes may be pruned with this structure. At each stage of the branch and bound algorithm, active set algorithm is adopted to solve the dual subproblem. In order to reduce the complexity further, the Cholesky factorization update is presented to solve the linear system at each iteration of active set algorithm efficiently. By relaxing the pruning conditions, we also present the quasi branch and bound algorithm which implements a good tradeoff between performance and complexity. Numerical results show that the complexity of MIMO detection based on branch and bound algorithm is very low, especially in low SNR and large constellations.

A Branch and Bound Algorithm for the Protein Folding Problem in the HP Lattice Model

A branch and bound algorithm is proposed for the two-dimensional protein folding problem in the HP lattice model. In this algorithm, the benefit of each possible location of hydrophobic monomers is evaluated and only promising nodes are kept for further branching at each level. The proposed algorithm is compared with other well-known methods for 10 benchmark sequences with lengths ranging from 20 to 100 monomers. The results indicate that our method is a very efficient and promising tool for the protein folding problem.

Multi-objective optimization in a finite time thermodynamic method for dish-Stirling by branch and bound method and MOPSO algorithm

There are various analyses for a solar system with the dish-Stirling technology.One of those analyses is the finite time thermodynamic analysis by which the total power of the system can be obtained by calculating the process time.In this study,the convection and radiation heat transfer losses from collector surface,the conduction heat transfer between hot and cold cylinders,and cold side heat exchanger have been considered.During this investigation,four objective functions have been optimized simultaneously,including power,efficiency,entropy,and economic factors.In addition to the fourobjective optimization,three-objective,two-objective,and single-objective optimizations have been done on the dish-Stirling model.The algorithm of multi-objective particle swarm optimization(MO P S O)with post-expression of preferences is used for multi-objective optimizations while the branch and bound algorithm with pre-expression of preferences is used for single-objective and multi-objective optimizations.In the case of multi-objective optimizations with post-expression of preferences,Pareto optimal front are obtained,afterward by implementing the fuzzy,LINMAP,and TOPSIS decision making algorithms,the single optimum results can be achieved.The comparison of the results shows the benefits of MOPSO in optimizing dish Stirling finite time thermodynamic equations.

Research on Guaranteed Scheduling Algorithms

Guaranteed scheduling is necessary for hard real time systems, because each process of them must meet their deadline, or a serious consequence will result.In this paper we discuss two guaranteed schedule algorithms:backtracking and branch and bound,introduce the process to find the optimal solution by both methods,propose the concept of logical node and physical node.Through some experiments for different process sets,we have made comparisons between the two algorithms in branch nodes,comparing time,topology of the search tree,memory size needed,etc.

Discrete differential evolution algorithm for integer linear bilevel programming problems

A discrete differential evolution algorithm combined with the branch and bound method is developed to solve the integer linear bilevel programming problems, in which both upper level and lower level variables are forced to be integer. An integer coding for upper level variables is adopted, and then a discrete differential evolution algorithm with an improved feasibility-based comparison is developed to directly explore the integer solution at the upper level. For a given upper level integer variable, the lower level integer programming problem is solved by the existing branch and bound algorithm to obtain the optimal integer solution at the lower level. In the same framework of the algorithm, two other constraint handling methods, i.e. the penalty function method and the feasibility-based comparison method are also tested. The experimental results demonstrate that the discrete differential evolution algorithm with different constraint handling methods is effective in finding the global optimal integer solutions, but the improved constraint handling method performs better than two compared constraint handling methods.

Exact Algorithm to Solve the Minimum Cost Multi-Constrained Multicast Routing Problem

The optimal solution of the multi-constrained QoS multicast routing problem is a tree-like hierarchical structure in the topology graph. This multicast route contains a feasible path from the source node to each of the destinations with respect to a set of QoS constraints while minimizing a cost function. Often, it is a tree. In other cases, the hierarchies can return several times to nodes and links of the topology graph. Similarly to Steiner problem, finding such a structure is an NP-hard problem. The usual tree and topology enumeration algorithms applied for the Steiner problem cannot be used to solve the addressed problem. In this paper, we propose an exact algorithm based on the Branch and Bound principle and improved by the Lookahead technique. We show relevant properties of the optimum hierarchy permitting efficient pruning of the search space. To our knowledge, our paper is the first to propose an exact algorithm for this non-trivial multi-constrained optimal multicast route computation. Simulations illustrate the efficiency of the proposed pruning operations. The analysis of the execution time shows that in simple topologies and with tight QoS constraints the exact algorithm requires relatively little execution time. With loose constraints the computation time cannot be tolerated even for off-line route computation. In these cases, the solution is close to a Steiner tree and heuristics can be applied. These results can serve as basis for the design of efficient, polynomial-time routing algorithms.

An Algorithm to Find K Shortest Path

In this figure, it finds a vertex to another vertex k shortest path algorithm. Provided there are n vertices and edges in the diagram. If the path loops, the time complexity of the algorithm is allowed O（w ＋ n log 2 n ＋ kw log 2 k）. If the request path does not contain the loop, the time complexity of the algorithm O（kn（w ＋ n log2 n）＋ kw log2 k）. The algorithm utilizes a simple extension of the Dijkstra algorithm determined the end of the length of the shortest path to the other vertices, and then, based on these data, branch and bound method to identify the required path. Experimental results show that the actual running time has relations with the structure of FIG.

An efficient distributed algorithm for game tree search

This paper presents a distributed game tree search algorithm called DDS. Based on communication overhead, st,orage requirement, speed up, and oiller factors, the performance of algorithm DDS* is analysed, and the number of nodes searched with SSS as well as a-b algorithm. The simulation test shows that. DDS* is an efficient and practical search algorithm.

OPTIMIZATION OF MULTIPLE-CHANNEL COOPERATIVE SPECTRUM SENSING WITH DATA FUSION RULE IN COGNITIVE RADIO NETWORKS

This paper focuses on multi-channel Cooperative Spectrum Sensing (CSS) where Secondary Users (SUs) are assigned to cooperatively sense multiple channels simultaneously. A multi-channel CSS optimization problem of joint spectrum sensing and SU assignment based on data fusion rule is formulated, which maximizes the total throughput of the Cognitive Radio Network (CRN) subject to the constraints of probabilities of detection and false alarm. To address the optimization problem, a Branch and Bound (BnB) algorithm and a greedy algorithm are proposed to obtain the optimal solutions. Simulation results are presented to demonstrate the effectiveness of our proposed algorithms and show that the throughput improvement is achieved through the joint design. It is also shown that the greedy algorithm with a low complexity achieves the comparable performance to the exhaustive algorithm.

A NEW GLOBAL OPTIMIZATION ALGORITHM FOR MIXED-INTEGER QUADRATICALLY CONSTRAINED QUADRATIC FRACTIONAL PROGRAMMING PROBLEM

The mixed-integer quadratically constrained quadratic fractional programming(MIQCQFP)problem often appears in various fields such as engineering practice,management science and network communication.However,most of the solutions to such problems are often designed for their unique circumstances.This paper puts forward a new global optimization algorithm for solving the problem MIQCQFP.We first convert the MIQCQFP into an equivalent generalized bilinear fractional programming(EIGBFP)problem with integer variables.Secondly,we linearly underestimate and linearly overestimate the quadratic functions in the numerator and the denominator respectively,and then give a linear fractional relaxation technique for EIGBFP on the basis of non-negative numerator.After that,combining rectangular adjustment-segmentation technique and midpointsampling strategy with the branch-and-bound procedure,an efficient algorithm for solving MIQCQFP globally is proposed.Finally,a series of test problems are given to illustrate the effectiveness,feasibility and other performance of this algorithm.

Optimization of observing sequence based on nominal trajectories of symmetric observing con guration

This paper presents the crucial method for obtaining our team's results in the 8th Global Trajectory Optimization Competition(GTOC8).Because the positions and velocities of spacecraft cannot be completely determined by one observation on one radio source,the branch and bound method for sequence optimization of multi-asteroid exploration cannot be directly applied here.To overcome this diculty,an optimization method for searching the observing sequence based on nominal low-thrust trajectories of the symmetric observing con guration is proposed.With the symmetric observing con guration,the normal vector of the triangle plane formed by the three spacecraft rotates in the ecliptic plane periodically and approximately points to the radio sources which are close to the ecliptic plane.All possible observing opportunities are selected and ranked according to the nominal trajectories designed by the symmetric observing con guration.First,the branch and bound method is employed to nd the optimal sequence of the radio source with thrice observations.Second,this method is also used to nd the optimal sequence of the left radio sources.The nominal trajectories are then corrected for accurate observations.The performance index of our result is 128,286,317.0 km which ranks the second place in GTOC8.

Global Optimization Method for Linear Multiplicative Programming

In this paper, a new global algorithm is presented to globally solve the linear multiplicative programming（LMP）. The problem（LMP） is firstly converted into an equivalent programming problem（LMP（H））by introducing p auxiliary variables. Then by exploiting structure of（LMP（H））, a linear relaxation programming（LP（H）） of（LMP（H）） is obtained with a problem（LMP） reduced to a sequence of linear programming problems. The algorithm is used to compute the lower bounds called the branch and bound search by solving linear relaxation programming problems（LP（H））. The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Some examples are given to illustrate the feasibility of the proposed algorithm.

Optimal Component Types for the Design of Construction Processes

Within the project preparation phase, experienced professionals manually map design information onto process information with the aim to develop realistic and practical schedules. Unfortunately, the mapping itself is neither part of any underlying data model nor is it supported by current scheduling tools. As a consequence the process of setting up the data model for a schedule is still not supported formally. Huhnt and Enge described a modelling technique that addresses the missing linkage between design and process information[1]. The approach makes use of so called component types. These are template sub-processes that describe the fabrication procedure of typical building components. Decomposing the building into com-ponents and assigning a component type to each component allows for formal support while scheduling. Depending on the decomposition of the building into components and the complexity of the involved component types the specification effort differs. The question about optimal component types arises: Which layout of building components and component types results in minimal specification effort? This paper presents a branch and bound algorithm to determine optimal component types. For a given schedule, which has been modelled based on component types, all possible decompositions into sub-processes are determined. During the decomposition process the encountered configurations are compared. Those with minimal specifica-tion effort are registered. Theoretical and practical examples are examined and discussed.

A Taxonomy of Exact Methods for Partial Max-SAT

Partial Maximum Boolean Satisfiability （Partial Max-SAT or PMSAT） is an optimization variant of Boolean satisfiability （SAT） problem, in which a variable assignment is required to satisfy all hard clauses and a maximum number of soft clauses in a Boolean formula. PMSAT is considered as an interesting encoding domain to many reaHife problems for which a solution is acceptable even if some constraints are violated. Amongst the problems that can be formulated as such are planning and scheduling. New insights into the study of PMSAT problem have been gained since the introduction of the Max-SAT evaluations in 2006. Indeed, several PMSAT exact solvers have been developed based mainly on the Davis- Putnam-Logemann-Loveland （DPLL） procedure and Branch and Bound （B^B） algorithms. In this paper, we investigate and analyze a number of exact methods for PMSAT. We propose a taxonomy of the main exact methods within a general framework that integrates their various techniques into a unified perspective. We show its effectiveness by using it to classify PMSAT exact solvers which participated in the 2007~2011 Max-SAT evaluations, emphasizing on the most promising research directions.