1,721,138 research outputs found
The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines
No full textIn this paper we consider the nonsimultaneous multiprocessor scheduling problem, or NMSP for short. The NMSP is a makespan minimization scheduling problem which involves the nonpreemptive assignment of independent jobs on m parallel machines with different starting times. It is well known that the longest processing time (LPT) algorithm and the modified LPT(MLPT) algorithm yield schedules with makespans bounded by 3/2 - 1/2m and 4/3 times the optimum makespan, respectively. In this paper, we show that the best known worst-case performance bound, 4/3 of the MLPT, is tight by constructing a worst-case example. Then, we employ the bin-packing heuristic algorithm called the MULTIFIT to solve the NMSP and shaw that the makespan of the schedule generated by the MULTIFIT algorithm is bounded by 9/7 + 2(-k) times the optimum makespan, where k is the selected number of the major iterations in the MULTIFIT. This worst-case bound of the MULTIFIT algorithm is, so far, the best bound for the NMSP and the tightness of the bound is still an open question. (C) 1999 Elsevier Science B.V. All rights reserved.X1114sciescopu
Order consolidation for hierarchical product lines
No full textWe consider the batch production of hierarchical product lines in raw material industry where the whole or parts of multiple customer orders may be consolidated and processed in the same batch if their product specifications are compatible. The objective of the problem is to find maximum possible number of batches completely filled up to their capacity. The compatibility relationship among product specifications is represented by a graph called the compatibility graph. If the compatibility graph is an arbitrary graph, the problem is proven to be NP-hard and belongs to Max SNP-hard class. We develop an optimum algorithm for an important subclass of the problem where the graph is a quasi-threshold graph which in fact is the case for producing hierarchical product lines that are often found in raw materials industry.X110sciescopu
Parallel machines scheduling with machine shutdowns
No full textWe study the nonpreemptive parallel machines scheduling problem where some of the machines are planned to be shutdown. We apply LPT algorithm to the problem and analyze its performance. Our analysis shows that the makespan of the LPT schedule is bounded by twice the optimum makespan if no more than half of the machines are allowed to be shutdown simultaneously. We also show that this bound is tight by constructing a worst-case example. (C) 1998 Elsevier Science Ltd. All rights reserved.X1131sciescopu
A heuristic method for self-healing ring design in a single-homing cluster
No full textIn this paper, we consider a SONET (Synchronous Optical NETwork) USHR (Uni-directional Self-Healing Ring) design problem for a single-homing cluster, i.e., a cluster with a single designated hub. The problem is formulated as a nonlinear integer programming problem and a branch and bound heuristic method based on the Lagrangian relaxation and subgradient optimization technique is proposed to handle the problem. In solving any ring design problem, we should deal with two different aspects of the ring design, namely, the ring routing aspect and the ring loading aspect. Both of these two aspects are well integrated and represented in our model. Such an integrated formulation has not been proposed in the existing literature mainly due to its computationally intractable complexity. In order to cope with such complexity, a preprocessing technique for reducing the complexity and several branch and bound strategies are proposed. The efficiency of the proposed method is tested through computational experiments. For the computational experiments, test problems are generated using the data obtained from the actual topologies in Seoul, Korea. The computational experiments show that the proposed method yields near-optimum designs within reasonable computation time.X113sciescopu
Order consolidation for batch processing
No full textWe consider the batch processing of orders where either whole or part of a single order or a specific pair of different orders may be grouped in a batch with a fixed capacity. The problem can be modelled by a graph G = (V,E), where each node v is an element of V corresponds to an order, its weight w(v) corresponds to the amount of ordered quantity and a pair of orders, say u and v may be grouped in a batch if there exists the edge (u,v) is an element of E. The objective is to maximize the number of batches filled up to its capacity lambda . In this paper, we prove that the problem is NP-hard and, moreover, that no PTAS exists unless P = NP. Then, an optimal algorithm is developed with running time O(|V|log |V|) for the special case when G is a tree.X1189sciescopu
A subset sum approach to coil selection for slitting
No full textOptimizing coil slitting operation requires not only the generation of efficient slitting patterns but also the selection of coils to be slit by each pattern. When the coils to be slit are not identical, the optimal coil selection can be quite a cumbersome task. In this paper, we consider the problem of selecting coils to be slit by a given particular slitting pattern when the available coils are not identical. The objective of our problem is to maximize the customer order fulfillment while minimizing the slitting loss and overproduction. We adopt and modify a dynamic programming scheme for the subset sum problem to develop an optimal pseudo-polynomial time algorithm for the problem and demonstrate that the algorithm is fast enough for solving realistic problem instances.11sciescopu
HADRONIC AXION WINDOW AND THE BIG-BANG NUCLEOSYNTHESIS
No full textHadronic axions with the decay constant f(a) congruent-to 10(6) GeV may fulfil all astrophysical and laboratory constraints discussed so far. In this paper, we reexamine the possibility of the hadronic axion window while taking into account the uncertainties of some parameters describing low energy axion dynamics. It is found that f(a) in the range 3 X 10(5)-3 X 10(6) GeV can not be excluded by existing arguments. We then examine the implication of this hadronic axion window for the big-bang nucleosynthesis (NS) by evaluating the energy density of thermal axions at the nucleosynthesis epoch. Our analysis yields (rho(a)/rho(nu))NS=0.4-0.5 which exceeds slightly the current best bound (rho(a)/rho(nu))NS less-than-or-equal-to 0.3
Heuristics for automated knowledge source integration and service composition
No full textThe NP-hard component set identification problem is a combinatorial problem arising in the context of knowledge discovery, information integration, and knowledge source/service composition. Considering a granular knowledge domain consisting of a large number of individual bits and pieces of domain knowledge (properties) and a large number of knowledge sources and services that provide mappings between sets of properties, the objective of the component set identification problem is to select a minimum cost combination of knowledge sources that can provide a joint mapping from a given set of initially available properties (initial knowledge) to a set of initially unknown proper-ties (target knowledge). We provide a general framework for heuristics and consider construction heuristics that are followed by local improvement heuristics. Computational results are reported on randomly generated problem instances. (C) 2006 Published by Elsevier Ltd.X11914sciescopu
HEURISTIC ALGORITHMS FOR BUFFER ALLOCATION IN A PRODUCTION LINE WITH UNRELIABLE MACHINES
No full textEfficient heuristic algorithms are developed for the buffer allocation in a production line so as to maximize the throughput. We focus on the unbalanced production line in which the mean processing time of each machine is not identical. The optimal buffer allocation problem is formulated as a multi-dimensional non-linear search problem with a linear resource constraint such that total capacity available is finite. The concept of standard and non-standard exchange vectors are introduced to develop two different versions of the algorithm. Since the objective function representing the throughput is not differentiable, we suggest the pseudo-gradient for obtaining improving directions. Numerical experiments show that the proposed algorithms work well even for the larger problems that could not have been handled as yet.X1135sciescopu
A two-dimensional vector packing model for the efficient use of coil cassettes
No full textWe consider the problem of efficiently packing steel products, known as coils, into special containers, called cassettes for shipping. The objective is to minimize the number of cassettes used for packing all the given coils where each cassette has capacity limits on both total payload weight and size. We model this problem as a two-dimensional vector packing problem and propose a heuristic. We also analyze the worst-case performance of the proposed algorithm under a special condition which, in fact, holds for the particular real-world case that we handled. Our computational experiment with real production data shows that the proposed algorithm performs quite satisfactorily in practice. (C) 2004 Published by Elsevier Ltd.X119sciescopu
- …
