In the scheduling literature, it is often assumed that jobs arrive either simultaneously or individually. However, this assumption is invalid in most practical situations because jobs usually arrive in batches, e.g., ...
详细信息
ISBN:
(纸本)9781424426294
In the scheduling literature, it is often assumed that jobs arrive either simultaneously or individually. However, this assumption is invalid in most practical situations because jobs usually arrive in batches, e.g., the final testing house in the manufacturing of semiconductor. The concept of batch arrivals has been mentioned in some studies, but it has not been explored from an operational viewpoint. This paper first addresses an identical parallel machine problem with batch arrivals to minimize the total completion time. Since the problem is NP-hard, a heuristic based on binary integer program Is proposed. Computational results show that the proposed heuristic can efficiently obtain good solutions with an average percentage error of 0.41.
When dealing with machine scheduling problems, the number of available machines is usually treated as the only constrained resource. However, in many practical cases, additional resources such as operators, part holde...
详细信息
ISBN:
(纸本)9787121074370
When dealing with machine scheduling problems, the number of available machines is usually treated as the only constrained resource. However, in many practical cases, additional resources such as operators, part holders, or tools, are also needed during the operation and the amounts of these resources are generally limited. Therefore, one needs to put resource constraints into 'consideration in order to form feasible job schedules. In this study, the branch and bound method is applied on unrelated parallel machine scheduling problems with constrained resources. Two algorithms are developed to obtain the optimal solutions much that weighted completion time is minimized. The first algorithm is job oriented. That is, the search tree is constructed according to the sequential assignment of jobs on machines. The second algorithm, on the other hand, is resource oriented A variety of numerical examples are designed with different sizes and resource strength. Numerical experiments are conducted to evaluate the performance of the proposed algorithm. It is shown from our result that the resource-oriented branch and bound algorithm is more efficient in find the optimal solutions as the number of resource is significantly smaller than the number of jobs.
This paper presents an optimal phasor measurement units (PMUs) placement algorithm for the purpose of power system observability and also increasing the performance of secondary voltage control scheme. The optimal pla...
详细信息
ISBN:
(纸本)9781424416424
This paper presents an optimal phasor measurement units (PMUs) placement algorithm for the purpose of power system observability and also increasing the performance of secondary voltage control scheme. The optimal placement problem (OPP) is formulated such that to minimize the number of PMU installations subject to full network observability and monitoring pilot buses of the system to improve secondary voltage control performance. The branch and bound optimization method is adopted to solve the OPP problem which is suitable for problems with integer and boolean variables. Topology-based algorithm is used for observability analysis. Constraint functions considering adjacent zero-injection (ZI) buses are constructed using a novel hybrid topology transformation-nonlinear constraint method. The IEEE 14-bus, 30-bus, 57-bus and 118-bus standard test systems and New England 39-bus test system are used for simulation purposes.
Issues of computer network survivability have gained much attention in recent years since computer networks plays an important role in modern world. Many organizations, institutions, companies use computer networks as...
详细信息
Issues of computer network survivability have gained much attention in recent years since computer networks plays an important role in modern world. Many organizations, institutions, companies use computer networks as a basic tool for transmitting many kinds of information. Service disruptions in modern networks are expected to be significant because loss of services and traffic in high-speed fiber systems could cause a lot of damages including economic loses, political conflicts, human health problems. In this paper we focus on problems of survivable connection oriented network design. A new objective function LF for primary routes assignment applying the local-destination rerouting strategy is defined. Next, an optimization problem of primary routes assignment using the LF function is formulated. Moreover, a branch and bound algorithm for that problem is proposed. The theory and experimental results demonstrate the ability to apply the LF function to dynamic and static design of survivable connection oriented networks.
Nash Equilibrium is the solution of the Cournot Model considering the reaction functions provided that outputs are *** in practice,the outputs of some products are not *** improved branch and bound algorithm is propos...
详细信息
Nash Equilibrium is the solution of the Cournot Model considering the reaction functions provided that outputs are *** in practice,the outputs of some products are not *** improved branch and bound algorithm is proposed combining the Nash Equilibrium,considering the discontinuous *** proposed algorithm is different from the traditional algorithm where the respond functions would be converted into *** the improved algorithm is used to calculate the output of each manufacturer,the worst solution arising in the mid-process of calculation will be removed firstly,and then the final common integer solution of all manufactures will be the optimal *** procedure of the proposed algorithm is explicated in this *** example where two manufactures exist is studied,and the results validate the effectiveness of the method.
In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into su...
详细信息
In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision(NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method.
We propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles wh...
详细信息
We propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision (NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method.
This paper focuses on the problem of scheduling n independent jobs on m identical parallel machines for the objective of minimizing total tardiness of the jobs. We develop dominance properties and lower bounds, and de...
详细信息
This paper focuses on the problem of scheduling n independent jobs on m identical parallel machines for the objective of minimizing total tardiness of the jobs. We develop dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as upper bounds obtained from a heuristic algorithm. Computational experiments are performed on randomly generated test problems and results show that the algorithm solves problems with moderate sizes in a reasonable amount of computation time. (c) 2005 Elsevier B.V. All rights reserved.
In this paper, we consider a deterministic global optimization algorithm for solving a general linear sum of ratios (LFP). First, an equivalent optimization problem (LFP1) of LFP is derived by exploiting the character...
详细信息
In this paper, we consider a deterministic global optimization algorithm for solving a general linear sum of ratios (LFP). First, an equivalent optimization problem (LFP1) of LFP is derived by exploiting the characteristics of the constraints of LFP. By a new linearizing method the linearization relaxation function of the objective function of LFP1 is derived, then the linear relaxation programming (RLP) of LFP1 is constructed and the proposed branch and bound algorithm is convergent to the global minimum through the successive refinement of the linear relaxation of the feasible region of the objection function and the solutions of a series of RLP. And finally the numerical experiments are given to illustrate the feasibility of the proposed algorithm. (c) 2006 Elsevier Inc. All rights reserved.
Positional DNA sequencing by hybridization (PSBH) is a recently proposed enhancement of DNA sequencing by hybridization (SBH, potentially a powerful alternative to the DNA sequencing by gel electrophoresis). It has be...
详细信息
Positional DNA sequencing by hybridization (PSBH) is a recently proposed enhancement of DNA sequencing by hybridization (SBH, potentially a powerful alternative to the DNA sequencing by gel electrophoresis). It has been discussed in many papers and applied to large scale sequencing by hybridization. However, the computational part of PSBH reconstruction is a difficult problem, especially for the occurrence of hybridization errors. So far the problem has not been solved well. Taking PSBH as a combinatorial optimization problem, a novel reconstruction approach to PSBH is presented in this paper. The proposed approach accepts both the negative and positive errors and can greatly reduce ambiguities in the reconstruction of PSBH. The computational experiment shows that our algorithm works satisfactorily and correctly on the test data, especially for the positive errors and k-tuple repetitions. (c) 2006 Elsevier B.V. All rights reserved.
暂无评论