Search

Mass 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.

The insurgence of the COVID pandemic calls for mass vaccination campaigns worldwide. Pharmaceutical companies struggle to ramp up their production to meet the demand for vaccines but cannot always guarantee a perfectly regular delivery schedule. On the other hand, governments must devise plans to have most of their population vaccinated in the shortest possible time and have the vaccine booster administered after a precise time interval. The combination of delivery uncertainties and those time requirements may make such planning difficult. In this paper, we propose several heuristic strategies to meet those requirements in the face of delivery uncertainties. The outcome of those strategies is a daily vaccination plan that suggests how many initial doses and boosters can be administered each day. We compare the results with the optimal plan obtained through linear programming, which however assumes that we know in advance the whole delivery schedule. As for performance metrics, we consider both the vaccination time (which has to be as low as possible) and the balance between vaccination capacities over time (which has to be as uniform as possible). The strategies achieving the best trade-off between those competing requirements turn out to be the q-days ahead strategies, which put aside doses to guarantee that we do not run out of stock on just the next q days. Increasing the look-ahead period, i.e. q, allows to achieve a lower number of out-of-stock days, though worsening the other performance indicators.

We 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.

The insurgence of COVID-19 requires fast mass vaccination, hampered by scarce availability and uncertain supply of vaccine doses and a tight schedule for boosters. In this paper, we analyze planning strategies for the vaccination campaign to vaccinate as many people as possible while meeting the booster schedule. We compare a conservative strategy and q-days-ahead strategies against the clairvoyant strategy. The conservative strategy achieves the best trade-off between utilization and compliance with the booster schedule. Q-days-ahead strategies with q < 7 provide a larger utilization but run out of stock in over 30% of days.

Allocating the overall budget to projects is a major decision for an organization. Taking that decision by looking at the overall profit only may result in an unfair treatment of departments, with some departments overloaded and others underemployed (and dissatisfied). We consider an alternative approach, where the budget allocation is accomplished by aiming at fairness as well as profit. We adopt a knapsack-type Integer Linear Programming formulation to optimize both quality indicators of budget allocation, employing a fairly wide selection of fairness measures. The resulting optimization routines are applied to a representative selection of instances generated through Monte Carlo simulation. We show that high levels of fairness can be achieved for realistic scenarios with only a moderate loss of profit. Large companies appear to be able to achieve a better trade-off between fairness and profit. Striving for fairness also leads to funding more projects, thus increasing the usage level of the organization's human and material resources.

We address a single machine scheduling problem arising in a last mile delivery setting for a food company. The same problem finds obvious applications also in the context of internal manufacturing logistics. A set of food orders are placed by the customers and are to be fulfilled by the company. Each order comprises a delivery point and an ideal delivery time An order is considered on time if it is delivered within a certain given time interval around the ideal delivery time. All food is prepared in a single production facility (restaurant) and immediately carried to the customers by a single courier, who may dispatch one or two different orders in a single trip. Since late deliveries correspond to canceled orders and an economic loss for the company, it is of interest to schedule orders so that the number of late orders is minimized. We model the resulting decision problem as a special single machine scheduling problem and propose different mixed integer programs to solve it. Their performance is assessed through a computational study on a set of test instances derived by our real-world application.

In this work we consider a bilevel knapsack problem, in which one player, the follower, decides on the optimal utilization of a bounded resource. The second player, the leader, can offer incentives, or shared profits, so that the follower chooses options attractive also for the leader. Formally, each of the two players is associated with a subset of the knapsack items. The leader may offer profits for its items as incentives to the follower, before the follower selects a subset of all items in order to maximize its overall profit. The leader receives as pay-off only the profits from those of its items that are included by the follower in the overall knapsack solution. This pay-off is then reduced by the profits offered to the follower. The resulting setting is a Stackelberg strategic game. The leader has to resolve the trade-off between offering high profits as incentives to the follower and offering low profits to gain high pay-offs.We analyze the problem for the case in which the follower solves the resulting knapsack problem to optimality and obtain a number of strong complexity results. Then we invoke a common assumption of the literature, namely that the follower’s computing power is bounded. Under this condition, we study several natural Greedy-type heuristics applied by the follower. The solution structure and complexity of the resulting problems are investigated and solution strategies are derived, in particular an Integer Linear Programming (ILP) model, but also pseudopolynomial and polynomial algorithms, when possible.

This paper considers single-machine scheduling problems in which a given solution, i.e., an ordered set of jobs, has to be improved as much as possible by re-sequencing the jobs. The need for rescheduling may arise in different contexts, e.g., due to changes in the job data or because of the local objective in a stage of a supply chain that is not aligned with the given sequence. A common production setting entails the movement of jobs (or parts) on a conveyor. This is reflected in our model by facilitating the re-sequencing of jobs via a buffer of limited capacity accessible by a LIFO policy. We consider the classical objective functions of total weighted completion time, maximum lateness and (weighted) number of late jobs and study their complexity. For three of these problems, we present strictly polynomial-time dynamic programming algorithms, while for the case of minimizing the weighted number of late jobs NP-hardness is proven and a pseudo-polynomial algorithm is given.

Flows over time problems consider finding optimal dynamic flows over a network where capacities and transit times on arcs are given. In this paper we study a multicommodity flow over time problem in which no storage of flow at nodes is allowed and solutions are restricted to loopless flow-paths. We propose an exact algorithm based on a column generation approach for a path-based linear programming model and present the results of a preliminary computational study.

We study the problem faced by a decision maker who wants to allocate a scarce resource among several agents in order to maximize the total utility. An optimal solution may present a very unbalanced allocation of the resource to the agents and hence be perceived as unfair. On the other hand balanced allocations may be far from the optimum. In this paper we are interested in assessing the quality of fair solutions, i.e., in measuring the system efficiency loss under a fair allocation compared to the one that maximizes the total utility. This indicator is called the Price of Fairness and we study it under three different definitions of fairness, namely maximin, Kalai–Smorodinski and proportional fairness. Our results are twofold. We first formalize a number of properties holding for any general multi-agent problem without any special assumptions on the agent utilities. Then we introduce an allocation problem, in which each agent can consume the available bounded resource in given discrete quantities (items). The utility of each agent is given by the sum of these quantities (weights of allocated items). We distinguish two cases depending on whether disjoint sets or a shared set of items is available to the agents. Clearly, the maximization of the total utility is given by a Subset Sum Problem. For the resulting Fair Subset Sum Problem, in the case of two agents, we provide upper and lower bounds on the Price of Fairness as functions of an upper bound on the items size.

We investigate the concept of price of fairness in resource allocation and apply it to two-agent single-machine scheduling problems, in which two agents, each having a set of jobs, compete for use of a single machine to execute their jobs. We consider the situation where one agent aims at minimizing the total of the completion times of his jobs, while the other seeks to minimize the maximum tardiness with respect to a common due date for her jobs. We first explore and propose a definition of utility, then we study both max-min and proportionally fair solutions, providing a tight bound on the price of fairness for each notion of fairness. We extend our study further to the problem in which both agents wish to minimize the total of the completion times of their own jobs.

In this paper, we address a problem arising in a manufacturing environment concerning the joint scheduling of multiple jobs and a maintenance activity on a single machine. Such activity must be processed within a given time window and its non-deterministic duration takes values in a given interval. We seek job schedules which are robust to any possible changes in the maintenance activity duration. We consider makespan and total completion time objectives under four different robustness criteria. We discuss a few properties and the complexity of finding robust schedules for the resulting eight problem scenarios. For the case of total completion time objective and maximum absolute regret criterion, we design and test exact and heuristic algorithms. The results of an extensive computational campaign, performed for assessing the performance of the proposed solution approaches, are reported.

In this work, we address the problem of scheduling a set of n non-preemptive tasks on m dedicated machines in order to minimise the makespan. For each task deterministic processing times and a specific processing machine are given, moreover a set of precedence constraints among the tasks are known. We present a heuristic and some lower bounds on the minimum makespan for a relevant case in manufacturing applications, namely when the precedence constraints form a caterpillar graph. A caterpillar is a directed tree consisting of a single directed path and leaf nodes each of which is incident to the directed path by exactly one incoming arc. A number of computational experiments are also performed in order to test the performance of the proposed solution algorithm.

In this work we address a class of deterministic scheduling problems in which k agents compete for the usage of a single machine. The agents have their own objective functions and submit their tasks in successive steps to an external coordination subject, who sequences them by selecting the shortest task in each step. We look at the problem in two different settings and consider different combinations of cost functions. In a centralized perspective, generalizing previous results for the case with $$k=2$$ agents, we characterize the set of Pareto efficient solutions as for a classical multicriteria optimization problems. On one hand we determine the number of Pareto efficient solutions and on the other hand we study the computational complexity of the associated decision problem. Then, we consider the problem from a single agent perspective. In particular, we provide a worst-case analysis on the performance of two natural heuristic algorithms, SPT and WSPT, that suggest to an agent how to sequence its own tasks when its objective is makespan, sum of completion times, or sum of weighted completion times.

This contribution deals with a two-level discrete decision problem, a so-called Stackelberg strategic game: A Subset Sum setting is addressed with a set $N$ of items with given integer weights. One distinguished player, the leader, may alter the weights of the items in a given subset $L\subset N$, and a second player, the follower, selects a solution $A\subseteq N$ in order to utilize a bounded resource in the best possible way. Finally, the leader receives a payoff from those items of its subset $L$ that were included in the overall solution $A$, chosen by the follower. We assume that the follower applies a publicly known, simple, heuristic algorithm to determine its solution set, which avoids having to solve NP-hard problems. Two variants of the problem are considered, depending on whether the leader is able to control (i.e., change) the weights of its items (i) in the objective function or (ii) in the bounded resource constraint. The leader's objective is the maximization of the overall weight reduction, for the first variant, or the maximization of the weight increase for the latter one. In both variants there is a trade-off for each item between the contribution value to the leader's objective and the chance of being included in the follower's solution set. We analyze the leader's pricing problem for a natural greedy strategy of the follower and discuss the complexity of the corresponding problems. We show that setting the optimal weight values for the leader is, in general, NP-hard. It is even NP-hard to provide a solution within a constant factor of the best possible solution. Exact algorithms, based on dynamic programming and running in pseudopolynomial time, are provided. The additional cases, in which the follower faces a continuous (linear relaxation) version of the above problems, are shown to be straightforward to solve., Comment: 13 pages, 1 figure

In several scheduling applications, one may be required to revise a pre-determined plan in order to meet a certain objective. This may happen if changes in the scenario predicted beforehand occur (e.g., due to disruptions, breakdowns, data values different from the expected ones). In this case costly reorganization of the current solution impose a limit on the allowed number of modifications. In our work, we address a single-machine scheduling problem where we need to alter a given (original) solution, by re-sequencing jobs with constraints on the number and type of allowed job shifts. For different objectives and rearrangement types, we propose mathematical programming models and possible solution approaches.

Mergers between mobile network operators involve merging their respective networks. Though this may represent a chance to optimize the network structure, merging may not represent the cost-optimal solution. In this paper, we compare two different evolution paths, where the networks to be merged are separately upgraded to cover the whole traffic demand or a single network is optimized as the result of the merger (Build vs Merge). Our preliminary analyses show that the Merge approach may lead to 50% higher costs, due in particular to the high costs borne to switch off redundant access points. Any Build vs Merge decision should therefore consider the sunk costs due to the inherited networks, as well as the possible benefits associated to a merger.

We address a class of deterministic scheduling problems in which two agents compete for the usage of a single machine. The agents have their own objective functions and submit in each round an arbitrary, unprocessed task from their buffer for possible selection. In each round the shortest of the two submitted tasks is chosen and processed on the machine.We consider the problems under two distinct perspectives: First, we look at them from a centralized point of view as bicriteria optimization problems and try to characterize the set of Pareto optimal solutions. Then, the problems are viewed under the perspective of a single agent. In particular, we measure the worst-case performance of classical priority rules compared to an optimal strategy. Finally, we consider minimax strategies, i.e. algorithms optimizing the objective of one agent in the worst case.

Flows over time problems relate to finding optimal flows over a capacitated network where transit times on network arcs are explicitly considered. In this article, we study the problem of determining a minimum cost origin-destination path where the cost and the travel time of each arc depend on the time taken to travel from the origin to that particular arc along the path. We provide computational complexity results for this problem and an exact solution algorithm based on an enumeration scheme on the corresponding time expanded network. Finally, we show the efficiency of our approach through a number of experimental tests. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 23–32 2017.