1,721,202 research outputs found
A Heuristic Approach to Batching and Scheduling a Single Machine to Minimize Setup Costs
No full textOn the bicriteria k-server problem
No full textIn this article we consider multicriteria formulations of classical online problems in which an algorithm must simultaneously perform well with respect to two different cost measures. Every strategy for serving a sequence of requests is characterized by a pair of costs and therefore there can be many different minimal or optimal incomparable solutions. The adversary is assumed to choose from one of these minimal strategies and the performance of the algorithm is measured with respect to the costs the adversary pays servicing the sequence according to its determined choice of strategy. We consider a parametric family of functions which includes all the possible selections for such strategies. Then, starting from a simple general method that combines any multicriteria instance into a single-criterion one, we provide a universal multicriteria algorithm that can be applied to different online problems. In the multicriteria k-server formulation with two different edge weightings, for each function class, such a universal algorithm achieves competitive ratios that are only an O(log W) multiplicative factor away from the corresponding determined lower bounds, where W is the maximum ratio between the two weights associated to each edge. We then extend our results to two specific functions, for which nearly optimal competitive algorithms are obtained by exploiting more knowledge of the selection properties. Finally, we show how to apply our framework to other multicriteria online problems sharing similar properties
Competitive Algorithms for the Bicriteria k-Server Problem
No full textIn this paper we consider the bicriteria formulation of the well-known online k-server problem where the cost of moving k servers
between given locations is evaluated simultaneously with respect to two different metrics. Every strategy for serving a sequence of
requests is thus characterized by a pair of costs, and an online algorithm is said to be (c1, c2)-competitive in the strong sense if it
is c1-competitive with respect to the first metric and c2-competitive with respect to the second one. We first prove a lower bound
on c1 and c2 that holds for any online bicriteria algorithm for the problem. We then propose an algorithm achieving asymptotically
optimal tradeoffs between the two competitive ratios. Finally, we show how to further decrease the competitive ratios when the two
metrics are induced by the distances in a complete graph and in a path, respectively, obtaining optimal results for particular cases
Optimal allocation plan for distribution centres of a frozen food company
No full textIn this paper, we analyse the distribution system of an Italian company operating in the ice cream and frozen food industry. In particular, we address the problem of optimally allocating products demand to distribution centres spread over the Italian territory and develop a mixed integer programming model. We present our computational experience in which the optimal solution is compared with the actual distribution policies and show how to use our model as a decision support tool for the company management
A Stackelberg knapsack game with weight control
No full textWe address a bilevel knapsack problem where a set of items with weights and profits is given. One player, the leader, may control the weights of a given subset of items. The second player, the follower, outputs the actual solution of the resulting knapsack instance, maximizing the overall profit. The leader receives as payoff the weights from those items of its associated subset that were included in the solution chosen by the follower.We analyze the leader's payoff maximization problem for three different solution strategies of the follower and discuss the complexity of the corresponding problems. In particular, we show that, when the follower adopts a greedy strategy, setting the optimal weight values is NP-hard. Also, it is NP-hard to provide a solution within a constant factor of the best possible solution. However, a MIP-formulation can be given. Moreover, the truncated greedy strategy allows an easy answer for the revision of weights. For the additional case, in which the follower faces a continuous (linear relaxation) version of the above problems, the optimal strategies can be fully characterized and computed in polynomial time. (C) 2019 Elsevier B.V. All rights reserved
Robust job-sequencing with an uncertain flexible maintenance activity
Full text linkIn this study, the problem of scheduling a set of jobs and one uncertain maintenance activity on a single machine, with the objective of minimizing the makespan is addressed. The maintenance activity has a given duration and must be executed within a given time window. Furthermore, duration and time window of the maintenance are uncertain, and can take different values which can be described by different scenarios. The problem is to determine a job sequence which performs well, in terms of makespan, independently on the possible variation of the data concerning the maintenance. A robust scheduling approach is used for the problem, in which four different measures of robustness are considered, namely, maximum absolute regret, maximum relative regret, worst-case scenario, and ordered weighted averaging. Complexity and approximation results are presented. In particular, we show that, for all the four robustness criteria, the problem is strongly NP-hard. A number of special cases are explored, and an exact pseudopolynomial algorithm based on dynamic programming is devised when the number of scenarios is fixed. Two Mixed Integer Programming (MIP) models are also presented for the general problem. Several computational experiments have been conducted to evaluate the efficiency and effectiveness of the MIP models and of the dynamic programming approach
The Uncertain Times of COVID Mass Vaccine Deliveries: from Start-up to Steady-State
No full textMass vaccination campaigns have been adopted throughout the world as a major tool to stop the spread of COVID or at least abate its lethal consequences. Smart vaccination strategies have been proposed to make the most efficient use of the scarce resources (e.g., medical and nursing staff) and achieve vaccination aims (i.e., vaccinating as many people as possible in the shortest possible time). However, smart strategies may fail if vaccine deliveries are erratic or do not exhibit even statistical regularity. In this paper, we perform a statistical analysis of up-to-date vaccine delivery data to uncover regularities and use them to draw a probabilistic model of vaccine deliveries that may help optimize and evaluate smart vaccination strategies. We find that for two out of three vaccine manufacturing companies, deliveries concentrate on one or at most two days over a week, though the actual day may be modelled by an arithmetic distribution
An approximate A(*) algorithm and its application to the SCS problem
No full textIn this paper we deal with algorithm A(*) and its application to the problem of finding the shortest common supersequence of a set of sequences. A(*) is a powerful search algorithm which may be used to carry out concurrently the construction of a network and the solution of a shortest path problem on it. We prove a general approximation property of A(*) which, by building a smaller network, allows us to find a solution with a given approximation ratio. This is particularly useful when dealing with large instances of some problem. We apply this approach to the solution of the shortest common supersequence problem and show its effectiveness. (C) 2002 Elsevier Science B.V. All rights reserved
- …
