Two heuristic procedures for a one-warehouse multi-retailer system are developed. Based on the accuracy desired, the first heuristic evaluates a specified number of points. The relative error is within a bound that ap...
详细信息
Two heuristic procedures for a one-warehouse multi-retailer system are developed. Based on the accuracy desired, the first heuristic evaluates a specified number of points. The relative error is within a bound that approaches 1/(root 2 In 2) - 1 approximate to 2.014%. The complexity of the heuristic is O(n) for a fixed number of evaluations. Although our bound only approaches the one of Roundy (1985), when only a small number of points are evaluated, our method is faster. We show that the bound for our procedure and two bounds proposed by Roundy (1985) are tight. The second heuristic pertains to a class of policies called stationary interval policies. For this class of policies, we develop a fully polynomial-time approximation scheme where the relative error is within epsilon > 0, and the computational effort increases as a linear function of 1/root epsilon. Computational experiments show that these heuristics perform well in practice.
Results from source location in the form of single cover problems in static networks are reviewed and extended by new results for the most general problem with arbitrary demands and costs. The matroidal structure of t...
详细信息
Results from source location in the form of single cover problems in static networks are reviewed and extended by new results for the most general problem with arbitrary demands and costs. The matroidal structure of the single covers is established and used in a new and simple validity proof of the dual greedy algorithm for static single cover problems. Moreover, a primal greedy algorithm is derived which uses a new procedure to find the collection of all minimal deficient sets. For static plural cover problems on trees two linear-time algorithms to solve simultaneous and non-simultaneous problems with uniform costs are presented;for the simultaneous scenario with non-uniform costs, a pseudo-polynomial algorithm is proposed which can be turned into a fully polynomial-time approximation scheme. In contrast to its static counterpart, the single cover problem in dynamic, i.e., time-varying networks is shown to be strongly NP-hard. For special cases of the network topology polynomial algorithms are presented.
Often the problem of determining an optimal or approximate production schedule in a company can be reduced to the problem of solving a scheduling problem on a bottleneck machine. However, even the majority of the resu...
详细信息
Often the problem of determining an optimal or approximate production schedule in a company can be reduced to the problem of solving a scheduling problem on a bottleneck machine. However, even the majority of the resulting single-machine scheduling problems are NP-hard from a computational point of view and, therefore, it is difficult to solve large instances of such problems exactly. In this paper, we consider five such single-machine problems, where a dynamic programming algorithm of pseudo-polynomial complexity exists. The running time of such an algorithm can often be improved by so-called graphical algorithms which do not need to consider all states in a dynamic programming algorithm separately. Based on such graphical algorithms, we present fully polynomial-time approximation schemes (FPTASes) for five single-machine total tardiness problems. The new FPTASes have the best running time among the known approximationschemes for these problems. The presented approach is rather general and can be applied to many other scheduling and combinatorial optimisation problems as well.
Advances in virtualization technologies and edge computing have inspired a new paradigm for Internet-of-Things (IoT) application development. By breaking a monolithic application into loosely coupled microservices, gr...
详细信息
ISBN:
(纸本)9781728105154
Advances in virtualization technologies and edge computing have inspired a new paradigm for Internet-of-Things (IoT) application development. By breaking a monolithic application into loosely coupled microservices, great gain can be achieved in performance, flexibility and robustness. In this paper, we study the important problem of load balancing across IoT microservice instances. A key difficulty in this problem is the interdependencies among microservices: the load on a successor microservice instance directly depends on the load distributed from its predecessor microservice instances. We propose a graph-based model for describing the load dependencies among microservices. Based on the model, we first propose a basic formulation for load balancing, which can be solved optimally in polynomialtime. The basic model neglects the quality-of-service (QoS) of the IoT application. We then propose a QoS-aware load balancing model, based on a novel abstraction that captures a realization of the application's internal logic. The QoS-aware load balancing problem is NP-hard. We propose a fully polynomial-time approximation scheme for the QoS-aware problem. We show through simulation experiments that our proposed algorithm achieves enhanced QoS compared to heuristic solutions.
This paper addresses the problem of controlling a large set of agents, each with a quadratic utility function depending on individual combinatorial choices, and all sharing an affine constraint on available resources....
详细信息
ISBN:
(纸本)9781728157429
This paper addresses the problem of controlling a large set of agents, each with a quadratic utility function depending on individual combinatorial choices, and all sharing an affine constraint on available resources. Such a problem is formulated as an integer mono-constrained bounded quadratic knapsack problem. Differently from the centralized approaches typically proposed in the related literature, we present a new decentralized algorithm to solve the problem approximately in polynomialtime by decomposing it into a finite series of sub-problems. We assume a minimal communication structure through the presence of a central coordinator that ensures the information exchange between agents. The proposed solution relies on a decentralized control algorithm that combines discrete dynamic programming with additive decomposition and value functions approximation. The optimality and complexity of the presented strategy are discussed, highlighting that the algorithm constitutes a fullypolynomialapproximationscheme. Numerical experiments are presented to show the effectiveness of the approach in the optimal resolution of largescale instances.
This paper considers single machine scheduling with an availability constraint and rejection. It is assumed that the machine is not available for processing during a given time interval. A job is either rejected, in w...
详细信息
This paper considers single machine scheduling with an availability constraint and rejection. It is assumed that the machine is not available for processing during a given time interval. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the machine. The objective is to minimize the sum of the weighted total completion time of the accepted jobs and the total rejection penalty of the rejected jobs. For this NP-hard problem, we present a pseudo-polynomial dynamic programming algorithm and a fully polynomial-time approximation scheme (FPTAS).
We consider the NP-hard m - parallel two-stage flowshop problem, abbreviated as the ( m , 2 ) -PFS problem, where we need to schedule n jobs to m parallel identical two-stage flowshops in order to minimize the makespa...
详细信息
We consider the NP-hard m - parallel two-stage flowshop problem, abbreviated as the ( m , 2 ) -PFS problem, where we need to schedule n jobs to m parallel identical two-stage flowshops in order to minimize the makespan, i.e. the maximum completion time of all the jobs on the m flowshops. The ( m , 2 ) -PFS problem can be decomposed into two subproblems: to assign the n jobs to the m parallel flowshops, and for each flowshop to schedule the jobs assigned to the flowshop. We first present a pseudo-polynomialtime dynamic programming algorithm to solve the ( m , 2 ) -PFS problem optimally, for any fixed m , based on an earlier idea for solving the ( 2 , 2 ) -PFS problem. Using the dynamic programming algorithm as a subroutine, we design a fully polynomial-time approximation scheme (FPTAS) for the ( m , 2 ) -PFS problem.
暂无评论