Search

This paper considers due date assignment and sequencing for multiple jobs in a single machine shop. The processing time of each job is assumed to be uncertain and is characterized by a mean and a variance with no knowledge of the entire distribution. The objective is to minimize the combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. The earliness and tardiness penalties and the penalty associated with long due date assignment are all expressed quadratic functions. Heuristic procedures are developed for the objective function. The due dates and sequences obtained by these procedures depend not only on means but also variances of the job processing times. Our numerical examples indicate that the variance information of job processing times can be useful for sequencing and due date assignment decisions. In addition, the performance of the procedures proposed in this paper are robust and stable with respect to job processing time distributions. Keywords: scheduling, sequencing, due date assignment, heuristics. [ABSTRACT FROM AUTHOR]

Let G be a undirected connected graph. Given a set of g groups each being a subset of V(G), tree routing and coloring is to produce g trees in G and assign a color to each of them in such a way that all vertices in every group are connected by one of produced trees and no two trees sharing a common edge are assigned the same color. In this paper we study how to find a tree routing and coloring that uses minimal number of colors, which finds an application of setting up multicast connections in optical networks. We first prove Ω(g1 - ε)-inapproximability of the problem even when G is a mesh, and then we propose some approximation algorithms with provable performance guarantees for general graphs and some special graphs as well. [ABSTRACT FROM AUTHOR]

We study the problem of embedding a directed hypergraph on a ring that has applications in optical network communications. The undirected version (MCHEC) has been extensively studied. It was shown that the undirected version was NP-complete. A polynomial time approximation scheme (PTAS) for the undirected version has been developed. In this paper, we design a polynomial time approximation scheme for the directed version. [ABSTRACT FROM AUTHOR]

The idea of active networks has been emerged in recent years to increase the processing power inside the network. The intermediate nodes such as routers will be able to host mobile agents and many management tasks can be handled using autonomous mobile agents inside the network. One of the important limitations, which should be considered in active networks, is the restricted processing power of active nodes. In this paper, we define an optimal location problem for monitoring mobile agents in a scalable active network as a p-median problem, which is indeed a kind of facility location problem. The agents are responsible to monitor and manage the performance of all of the network nodes such that the total monitoring traffic overhead is minimized. Then we proposed two methods of finding an appropriate sub set of intermediate nodes for hosting mobile agents. In our first method, we have not considered the limited processing power of active nodes, which host mobile agents. In our second method, we have solved the problem so that the processing loads of host nodes do not exceed a predefined threshold. Since p-median problems are NP-complete and the search space of these problems is very large, our methods are based on genetic algorithms. We have tested our two methods for finding mobile agents optimal locations on four network topologies with different number of nodes and compared the obtained location. By this comparison, we have shown the importance of considering processing load limitation for active nodes as a parameter in choosing them as hosts of mobile agents in a scalable active network. The proposed locations in our second method eliminates the probability of CPU overload in the active nodes hosting the mobile agents and reduces the processing time required for finding the optimal locations of mobile agents. Keywords: Active Networks, mobile agents, Performance Monitoring, P-Median Problem, Genetic Algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we develop a new and effective schedule algebra based algorithm to determine the K-best solutions of a knapsack problem with a single constraint. Computational experience with this algorithm is also reported and it is shown to dominate both the dynamic programming and branch and bound based procedures when applied to this problem. [ABSTRACT FROM AUTHOR]

Level of Repair Analysis (LORA) is a prescribed procedure for defence logistics support planning. For a complex engineering system containing perhaps thousands of assemblies, sub-assemblies, components, etc. organized into several levels of indenture and with a number of possible repair decisions, LORA seeks to determine an optimal provision of repair and maintenance facilities to minimize overall life-cycle costs. For a LORA problem with two levels of indenture with three possible repair decisions, which is of interest in UK and US military and which we call LORA-BR, Barros (1998) and Barros and Riley (2001) developed certain branch-and-bound heuristics. The surprising result of this paper is that LORA-BR is, in fact, polynomial-time solvable. To obtain this result, we formulate the general LORA problem as an optimization homomorphism problem on bipartite graphs, and reduce a generalization of LORA-BR, LORA-M, to the maximum weight independent set problem on a bipartite graph. We prove that the general LORA problem is NP-hard by using an important result on list homomorphisms of graphs. We introduce the minimum cost graph homomorphism problem and provide partial results. Finally, we show that our result for LORA-BR can be applied to prove that an extension of the maximum weight independent set problem on bipartite graphs is polynomial time solvable. [ABSTRACT FROM AUTHOR]

The Knapsack problem and integer programming are NP-complete problems. In this paper we show that the inverse problem of Knapsack problem can be solved with a pseudo-polynomial algorithm. We also show that the inverse problem of integer programming with fixed number of constraints is pseudo-polynomial. Keywords: Inverse problem, Knapsack problem, integer programming, pseudo-polynomial algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study the Minimum Range Assignment problem in static ad-hoc networks with arbitrary structure, where the transmission distances can violate triangle inequality. We consider two versions of the Minimum Range Assignment problem, where the communication graph has to fulfill either the h-strong connectivity condition (Min-Range(h-SC)) or the h-broadcast condition (Min-Range(h-B)). Both homogeneous and non-homogeneous cases are studied. By approximating arbitrary edge-weighted graphs by paths, we present probabilistic O(log n)-approximation algorithms for Min-Range(h-SC) and Min-Range(h-B), which improves the previous best ratios O(log n loglog n) and O(n2log n loglog n), respectively [21]. The result for Min-Range(h-B) matches the lower bound [20] for the case that triangle inequality for transmission distance holds (which is a special case of our model). Furthermore, we show that if the network fulfils certain property and the distance power gradient α is sufficiently small, the approximation ratio is improved to O((loglog n)α). [ABSTRACT FROM AUTHOR]

The field of supply chain management has been growing at a rapid pace in recent years, both as a research area and as a practical discipline. In this paper, we study the computational complexity of product covering problems in 3-tier supply chain models, and present natural complete problems for the classes W[3] and W[4] in parameterized complexity theory. This seems the first group of natural complete problems for higher levels in the parameterized intractability hierarchy (i.e., the W-hierarchy), and the first precise complexity characterizations of certain optimization problems in the research of supply chain management. Our results also derive strong computational lower bounds and inapproximability for these optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we propose principle factor analysis method to reduce the dimensions of a high dimensional random vector in calculating portfolio's Value at Risk. The theoretical foundation, algorithm and numerical example of the method are given. This method outperforms the principle component analysis method. Especially, the advantages of the method are marked, while the factors F's multicollinearity is serious. Keywords: principal factor analysis, value at risk, principal component analysis, multicollinearity. [ABSTRACT FROM AUTHOR]

Graph bandwidth minimization (GBM) is a classical and challenging problem in graph algorithms and combinatorial optimization. Most of existing researches on this problem have focused on unweighted graphs. In this paper, we study the bandwidth minimization problem of weighted caterpillars, and propose several algorithms for solving various types of caterpillars. More specifically, we show that the GBM problem of caterpillars with hair-length at most 2 and the GBM problem of star-shape caterpillars are NP-complete, and give a lower bound of the graph bandwidth for general weighted graphs. For caterpillars with hair-length at most 1, we present an O(n log n log (nwmax))-time algorithm to compute an optimal bandwidth layout, where n is the total number of vertices in the graph and wmax is the maximum edge weight. For caterpillars with hair-length at most k, we give a k-approximation algorithm. For arbitrary caterpillars and general graphs, we give a heuristic algorithm. Experiments show that the solutions obtained by our heuristic algorithm are roughly within a factor of log (2n) of the lower bound. [ABSTRACT FROM AUTHOR]

In this paper we study the set cover games when the elements are selfish agents. In this case, each element has a privately known valuation of receiving the service from the sets, i.e., being covered by some set. Each set is assumed to have a fixed cost. We develop several approximately efficient truthful mechanisms, each of which decides, after soliciting the declared bids by all elements, which elements will be covered, which sets will provide the coverage to these selected elements, and how much each element will be charged. For set cover games when both sets and elements are selfish agents, we show that a cross-monotonic payment-sharing scheme does not necessarily induce a truthful mechanism. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a manpower planning problem with single job type over a long planning horizon. Dynamic demands of jobs must be fulfilled by allocating enough number of regular and temporal workers and each regular worker has a minimal employment contract period. A cost objective is concerned where costs for workforce include salaries of regular and temporal workers, and recruitment and dismissal costs of regular workers. We first formulate the problem as a multi-period decision model. Then we derive several properties of the optimal solution and develop an improved dynamic programming algorithm with polynomial computational complexity. Finally, numerical results are presented to illustrate several managerial insights. Keywords: Manpower planning, dynamic program, minimal contract period, temporal labor. [ABSTRACT FROM AUTHOR]

The utilization of pseudo-random proportional rule to balance between the exploitation and exploration of the search process was shown in Ant Colony System (ACS) algorithm. In ACS, this rule is governed by a parameter so-called exploiting parameter which is always set to a constant value. Besides, all ACO-based algorithm either omit this rule or applying it with a fixed value of the exploiting parameter during the runtime of algorithms. In this paper, this rule is adopted with a simple dynamical updating technique for the value of that parameter. Moreover, experimental analysis of incorporating a technique of dynamical updating for the value of this parameter into some state-of-the-art Ant-based algorithms is carried out. Also computational results on Traveling Salesman Problem benchmark instances are represented which probably show that Ant-based implementations with local search procedures gain a better performance if the dynamical updating technique is used. Keywords: Ant Colony Optimization, Ant System, Combinatorial Optimization Problem, Traveling Salesman Problem. [ABSTRACT FROM AUTHOR]

This paper mainly focuses on a new continuous method for solving multiuser detection in CDMA using the NCP function. This approach is completely different from the relaxation method in the sense that it is an equivalent conversion. The resulting nonlinear programming problem of multiuser detection is then solved using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied, and numerical experiments show this method is very effective. Keywords: Max cut problem; Penalty function method; Convex function. [ABSTRACT FROM AUTHOR]

In this paper, we study how to, given a set of pre-routed requests in an all-optical network and a set of wavelengths available on each link, assign a subset of requests with maximal size such that no wavelength constraint on links is violated. While all previous studies on the wavelength assignment problem with the same objective assume the same set of wavelengths available on all links, our work does not make such an assumption. We first prove that this problem is NP-hard even in bus networks, and then propose some approximation algorithms for the problem with guaranteed performance ratios in networks with some special and general topologies. [ABSTRACT FROM AUTHOR]

Since the apparition of Simulated Annealing algorithm (SA) it has shown to be an efficient method to solve combinatorial optimization problems. Due to this, new algorithms based on two looped cycles (temperatures and Markov chain) have emerged, one of them have been called Threshold Accepting (TA). Classical algorithms based on TA usually use the same Markov chain length for each temperature cycle, these methods spend a lot of time at high temperatures where the Markov chain length is supposed to be small. In this paper we propose a method based on the neighborhood structure to get the Markov chain length in a dynamic way for each temperature cycle. We implemented two TA algorithms (classical or TACM and proposed or TADM) for SAT. Experimentation shows that the proposed method is more efficient than the classical one since it obtain the same quality of the final solution with less processing time. Keywords: Simulated Annealing, Threshold Accepting, Cooling Scheme, Dynamic Markov Chains, Combinatorial Optimization, Heuristic Optimization, SAT problem. [ABSTRACT FROM AUTHOR]

In this paper we study the computational problem of arbitrage in a frictional market with a finite number of bonds and finite and discrete times to maturity. Types of frictions under consideration include fixed and proportional transaction costs, bid-ask spreads, taxes, and upper bounds on the number of units for transaction. We obtain some negative result on computational difficulty in general for arbitrage under those frictions: It is NP-complete to identify whether there exists a cash-and-carry arbitrage transaction and it is NP-hard to find an optimal cash-and-carry arbitrage transaction. [ABSTRACT FROM AUTHOR]

Link-bandwidth utilization and flow information are obviously critical for numerous network management tasks. The problem of efficiently monitoring the network flowing based on flow-conservation could be reduced to Weak Vertex Cover problem, which is NP-hard. In this paper, using the primal-dual method, we give an approximation algorithm with approximation ratio 2 to solve the problem. It is a near-optimal algorithm as it is very difficult to get an approximation algorithm with approximation ratio lower than 2 for Weak Vertex Cover problem. The effectiveness of our monitoring algorithm is validated by simulations evaluation over a wide range of network topologies. The practices indicate that our work is valuable to solve Weak Vertex Cover problem and its application in network management. [ABSTRACT FROM AUTHOR]

Given a pair of non-negative integers m and n, S(m,n) denotes a square lattice graph with a vertex set {0,1,2,...,m - 1} × {0,1,2,...,n - 1}, where a pair of two vertices is adjacent if and only if the distance is equal to 1. A triangular lattice graph T(m,n) has a vertex set where , and an edge set consists of a pair of vertices with unit distance. Let Sk(m,n) and Tk(m,n) be the kth power of the graph S(m,n) and T(m,n), respectively. Given an undirected graph G = (V,E) and a non-negative vertex weight function , a multicoloring of G is an assignment of colors to V such that each vertex v ∈ V admits w(v) colors and every adjacent pair of two vertices does not share a common color. In this paper, we show necessary and sufficient conditions that [∀ m, theSk(m,n) is perfect] and/or [∀ m, Tk(m,n) is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (Sk(m,n),w) and (Tk(m,n),w). [ABSTRACT FROM AUTHOR]

Differentiated service (DiffServ) is a mechanism to provide the Quality of Service (QoS) with a certain performance guarantee. In this paper, we study how to design DiffServ multicast when the participants (i.e., relay links) are selfish. We assume that each link ei is associated with a cost coefficient ai such that the cost of ei to provide a multicast service with bandwidth demand x is ai · x. We first show that a previous approximation algorithm does not directly induce a truthful mechanism. We then give a new polynomial time 8-approximation algorithm to construct a DiffServ multicast tree. Based on this tree, we design a truthful mechanism for DiffServ multicast, i.e., we give a polynomial-time computable payment scheme to compensate all chosen relay links such that each link ei maximizes its profit when it reports its privately cost coefficient ai truthfully. Keywords: DiffServ, multicast, selfish agents, algorithm mechanism design, approximation algorithms. [ABSTRACT FROM AUTHOR]

There are many non-probabilistic factors that affect the financial markets. In this paper, the possibilistic mean-variance model of portfolio selection is presented under the assumption that the returns of assets are fuzzy numbers, which can better integrate the experts' knowledge and the managers' subjective opinions to compare with conventional probabilistic mean-variance methodology. The possibilistic efficient frontier is derived explicitly when short sales are not allowed on all risky assets and a risk-free asset. [ABSTRACT FROM AUTHOR]

A new method for information retrieval based on relative entropy with different smoothing methods has been presented in this paper. The method builds a query language model and document language models respectively for the query and the documents. We rank the documents according to the relative entropies of the estimated document language models with respect to the estimated query language model. While estimating a document language, the efficiency of the smoothing method is considered, we select three popular and relatively efficient methods to smooth the document language model. The feedback documents are used to estimate a query model by the approach that we assume that the feedback documents are generated by a combined model in which one component is the feedback document language model and the other is the collection language model. Experimental results show that the method is effective and performs better than the basic language modeling approach. [ABSTRACT FROM AUTHOR]

This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems. The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof method is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis. [ABSTRACT FROM AUTHOR]

In this paper, we present three energy efficient broadcast and multicast routing algorithms for wireless ad hoc networks. The first algorithm computes a broadcast tree whose energy consumption is within a factor 2 + 2 ln (n - 1) of the optimal. The second algorithm computes a multicast tree whose energy consumption is within a constant factor of the optimal.Our third algorithm, for a multicast request with a given duration, computes an optimal multicast tree such that the minimal remaining energy of nodes is maximized after the multicast session. This algorithm helps to maximize the lifetime of the network. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a class of stochastic age-dependent population dynamic system. Applying the theory of stochastic functional differential equation, using Gronwall's lemma and Barkholder-Davis-Gundy's lemma, Existence and uniqueness of strong solution are proved for a class of stochastic age-dependent population dynamic system on Hilbert space. In particular, as a direct consequence our main results extend some of those from ordinary age-dependent population dynamic system. [ABSTRACT FROM AUTHOR]

Facility Location Problems have always been studied with the assumption that the environment in the network is static and does not change over time. In practice, however, the environment is usually dynamic and we must consider the facility location in a global view. In this paper, we impose the following additional constraints on input facilities: the total number of facilities to be placed is not known in advance and a facility cannot be removed once it is placed. We solve this problem by presenting an algorithm to find a facility permutation such that any prefix of the permutation of facilities is near-optimal over any other facility subset. [ABSTRACT FROM AUTHOR]

In a real options and game-theoretic framework, this paper investigates the optimal timing of two asymmetric firms' R&D investment under uncertainty. There exist three types of equilibria that can occur in the choice of the R&D investment strategies, i.e. the preemptive, sequential and simultaneous equilibrium. The occurrence of a particular type of equilibrium is determined by the firms' relative payoff, which mainly depends on the level of operating cost asymmetry and first-mover advantage and the operating cost itself. We show that when the cost asymmetry and the first-mover advantage among firms are relatively small, two firms invest simultaneously. When the first-mover advantage is significant, the low-cost firm preempts the high-cost firm. In the situation where the asymmetry between firms becomes large enough, two firms invest sequentially. We also show that the lower the operating cost is, the more the incentive to become the leader has. So, with the operating cost decreasing, the possibility of simultaneous equilibrium and sequential equilibrium decreases, but that of preemptive equilibrium increases. Keywords: Optimal timing, R&D Investment, Real Options, Game Theory, Asymmetric Duopoly. [ABSTRACT FROM AUTHOR]

This paper deals with the riding behavior of commuters who take trains from a living place to a work place during morning rush hours. The total travel cost include early and late arrival penalties as well as carriage body capacity. An equivalent mathematical programming model which generates equilibrium riding behavior is presented. The number of actually chosen transit runs, passenger flow distributions, and fares resulted from three system configurations namely social optimum, monopoly by one company and duopoly competition, are investigated by numerical examples. [ABSTRACT FROM AUTHOR]

In this paper the first results on the Online Dial-A-Ride Problem with Time-Windows (ODARPTW for short) are presented. Requests for rides appearing over time consist of two points in a metric space, a source and a destination. Servers transport objects of requests from sources to destinations. Each request specifies a deadline. If a request is not be served by its deadline, it will be called off. The goal is to plan the motion of servers in an online way so that the maximum number of requests is met by their deadlines. We perform competitive analysis of two deterministic strategies for the problem with a single server in two cases separately, where the server has unit capacity and where the server has infinite capacity. The competitive ratios of the strategies are obtained. We also prove a lower bound on the competitive ratio of any deterministic algorithm of for a server with unit capacity and of for a server with infinite capacity, where T denotes the diameter of the metric space. [ABSTRACT FROM AUTHOR]

It is wel-known that Nash considered the n-person noncooperative game with each player having finite strategic set and proved the celebrated existence result of Nash equilibrium point (in mixed strategies). This paper investigates the n-person noncooperative game with each player having infinite strategic set. By considering these infinite strategic as complete metric spaces and based on a new finite equilibrium system, we obtain new existence result of Nash equilibrium. Then an algorithm is given to compute Nash equilibrium points and its convergence is proved. [ABSTRACT FROM AUTHOR]

In this paper we investigate two single machine scheduling problems. The first problem addresses a class of the two-stage scheduling problem in which the first stage is job production and the second stage is job delivery. For the case that jobs are processed on a single machine and delivered by a single vehicle to one customer area, with the objective of minimizing the time when all jobs are completed and delivered to the customer area and the vehicle returns to the machine, an approximation algorithm with a worst-case ratio of 5/3 is known and no approximation can have a worst-case of 3/2 unless P = NP. We present an improved approximation algorithm with a worst-case ratio of 53/35, which only leaves a gap of 1/70. The second problem is a single machine scheduling problem subject to a period of maintenance. The objective is to minimize the total completion time. The best known approximation algorithm has a worst-case ratio of 20/17. We present a polynomial time approximation scheme. [ABSTRACT FROM AUTHOR]

University timetabling problem is a very common and seemingly simple, but yet very difficult problem to solve in practice. While solution definitely exists (evidenced by the fact that we do hold classes), an automated optimal schedule is very difficult to derive at present. There were successful attempts to address this problem using heuristics search methods. However, until now, university timetabling is still largely done by hand, because a typical university setting requires numerous customized complicated constraints that are difficult to model or automate. In addition, there is a problem of certain constraints being inviolable, while others are merely desirable. This paper intends to address the university timetabling problem that is highly constrained using Artificial Immune System. Empirical study on course timetabling for the School of Computer Engineering (SCE), Nanyang Technological University (NTU), Singapore as well as the benchmark dataset provided by the Metaheuristic Network shows that our proposed approach gives better results than those obtained using the Genetic Algorithm (GA). [ABSTRACT FROM AUTHOR]

In this paper we study the on-line production order disposal problem considering preemption and abortion penalty. We discuss the cases when orders have uniform and nonuniform lengths. For the case of uniform order length, the GR strategy is proved to be -competitive, where ρ ≥ 0 is the coefficient of the punishment. For the case of nonuniform order lengths, GR is -competitive where λ is the ratio of length between the longest and shortest orders. When abortion penalty is not counted, the ER strategy is proposed and proved to be eλ + e + 1 -competitive, where e ≈ 2.718. The result is much better than that of GR. We show that ER is not competitive when abortion penalty is counted. [ABSTRACT FROM AUTHOR]

Competitive analysis for all investors in the Bahncard problem (a railway pass of the Deutsche Bundesbahn company) has received much attention in recent years. In contrast to this common approach, which selects the riskless outcome and achieves the optimal competitive ratio, this paper introduces a risk-reward competitive strategy to achieve flexibility. Namely, we extend the traditional competitive analysis to provide a framework in which the travellers can develop optimal trading strategies based on their risk tolerance and investing capability. We further present a surprisingly flexible competitive ratio of for the Bahncard problem, where t is the risk tolerance and β is the percentage of discount with respect to this strategy. Then substituting t = 1 into the above equation, we obtain the (2 - β)-competitive ratio which is the best attainable result presented by Fleischer. [ABSTRACT FROM AUTHOR]

In this paper we study an algorithm to find critical points of a lower semicontinuous nonconvex function. We use the Moreau regularization for a special type of functions belonging to the class of prox-regular functions which have very interesting algorithmic properties. We show that it is possible to generate an algorithm in order to obtain a critical point using the theory developed for the composite functions and also the results for the solutions of nonsmooth vectorial equations. We prove the convergence of the algorithm and some estimations of the convergence speed.I would like to thank to Prof. A. Jofré for advising this work. Partially supported by FONDAP-Matemáticas Aplicadas. Keywords: Variational Analysis, Moreau Approximation, Proximal Point Algorithm, Prox-Regularity, Nonsmooth Equations. [ABSTRACT FROM AUTHOR]