Search

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.

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.

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.

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.

This work addresses a multi agent allocation problem in which multiple departments compete for shares of a company budget. Each department has its own portfolio of projects with given expected profits and costs and selects an optimal subset of its projects consuming its assigned budget share. Besides considering the total profit of the company a central decision maker should also take fairness issues into account. Thus, we introduce an equity criterion based on maximin fairness. The resulting trade-off between total profit and fairness indicators is studied in this contribution. To this purpose a bicriteria ILP model is presented where one of the objectives is the maximization of the overall profit and the other is the maximization of the minimum budget allocated to one of the departments. We perform an experimental analysis showing a nearly perfect linear anticorrelation between profit and fairness index values.

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to minimize the total weight of their solution sets. The latter are built according to a sequential procedure consisting in a fixed number of rounds. In every round each agent submits one item that may be included in its solution set. We study two natural rules to decide which item between the two will be included. We address the problem from a strategic point of view, that is finding the best moves for one agent against the opponent, in two distinct scenarios. We consider preventive or minimax strategies, optimizing the objective of the agent in the worst case, and best-response strategies, where the items submitted by the opponent are known in advance in each round.

The perspective relaxation (PR) is a general approach for constructing tight approximations to mixed-integer nonlinear programs (MINLP) with semicontinuous variables. The PR of a MINLP can be formulated either as a mixed-integer second-order cone program (MI-SOCP), provided that the original objective function is SOCP-representable, or as a semi-infinite MINLP. In this paper, we show that under some further assumptions (rather restrictive, but satisfied in several practical applications), the PR of a mixed-integer quadratic program (MIQP) can also be reformulated as a piecewise-quadratic program (QP), ultimately yielding a QP relaxation of roughly the same size of the standard continuous relaxation. Furthermore, if the original problem has some exploitable structure, then this structure is typically preserved in the reformulation, thus allowing the construction of specialized approaches for solving the PR. We report on implementing these ideas on two MIQPs with appropriate structure: a sensor placement problem and a quadratic-cost (single-commodity) network design problem.

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to maximize the total weight of their winning sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item for possible inclusion in its winning set. We study two natural rules to decide the winner of each round.For both rules we deal with the problem from different perspectives. From a centralized point of view, we investigate (i) the structure and the number of efficient (i.e. Pareto optimal) solutions, (ii) the complexity of finding such solutions, (iii) the best–worst ratio, i.e. the ratio between the efficient solution with largest and smallest total weight, and (iv) existence of Nash equilibria.Finally, we address the problem from a single agent perspective. We consider preventive or maximin strategies, optimizing the objective of the agent in the worst case, and best response strategies, where the items submitted by the other agent are known in advance either in each round (on-line) or for the whole game (off-line).

We address the exact resolution of a Mixed Integer Non Linear Programming model where resources can be activated in order to satisfy a demand (a covering constraint) while minimizing total cost. For each resource, there is a fixed activation cost and a variable cost, expressed by means of latency functions. We prove that this problem is $${\mathcal {N} \mathcal {P}}$$ -hard even for linear latency functions. A branch and bound algorithm is devised, having two important features. First, a dual bound (equal to that obtained by continuous relaxation) can be computed very efficiently at each node of the enumeration tree. Second, to break symmetries resulting in improved efficiency, the branching scheme is n-ary (instead of binary). These features lead to a successful comparison against two popular commercial and open-source solvers, CPLEX and Bonmin.

We consider the problem of scheduling n tasks subject to chain-precedence constraints on two identical machines with the objective of minimizing the makespan. The problem is known to be strongly NP-hard. Here, we prove that it is binary NP-hard even with three chains. Furthermore, we characterize the complexity of this case by presenting a pseudopolynomial time algorithm and a fully polynomial time approximation scheme.

In this paper, we address a deterministic scheduling problem in which two agents compete for the usage of a single machine. Each agent decides on a fixed order to submit its tasks to an external coordination subject, who sequences them according to a known priority rule. We consider the problem from different perspectives. First, we characterize the set of Pareto-optimal schedules in terms of size and computational complexity. We then address the problem from the single-agent point-of-view, that is, we consider the problem of deciding how to submit one agent's tasks only taking into account its own objective function against the other agent, the opponent. In this regard, we consider two different settings depending on the information available to the agents: In one setting, the considered agent knows in advance all information about the submission sequence of the opponent; and in the second setting (as in minimax strategies in game theory), the agent has no information on the opponent strategy and wants to devise a strategy that minimizes its solution cost in the worst possible case. Finally, we assess the performance of some classical single-agent sequencing rules in the two-agent setting.

We consider a game of two agents competing to add items into a solution set. Each agent owns a set of weighted items and seeks to maximize the sum of their weights in the solution set. In each round each agent submits one item for inclusion in the solution. We study two natural rules to decide the winner of each round: Rule 1 picks among the two submitted items the item with larger weight, Rule 2 the item with smaller weight. The winning item is put into the solution set, the losing item is discarded. For both rules we study the structure and the number of efficient solutions, i.e. Pareto optimal solutions. For Rule 1 they can be characterized easily, while the corresponding decision problem is NP-complete under Rule 2. We also show that there exist no Nash equlibria. Furthermore, we study the best-worst ratio, i.e. the ratio between the efficient solution with largest and smallest total weight, and show that it is bounded by two for Rule 1 but can be arbitrarily high for Rule 2. Finally, we consider preventive or maximin strategies, which maximize the objective function of one agent in the worst case, and best response strategies for one agent, if the items submitted by the other agent are known before either in each round (on-line) or for the whole game (off-line).

We consider the job shop scheduling problem with tvm jobs. We consider a broad class of non-regular, quasi-convex functions of the completion time of the two jobs. We show that the optimal solution, for this class of objective functions, can be computed in O(rlogr + logH) time, where r is the number of operation pairs using the same machine, and H is the maximum operation processing time. This paper deals with the job shop problem when two jobs have to be performed in the shop. The most efficient solution algorithm for this problem is Brucker's algorithm (4), which addresses the case in which the objective is the minimization of the makespan. Sotskov (7) has given a polynomial algorithm for the more general case in which one wants to minimize an arbitrary regular (i.e., nondecreasing) objective function in the completion times of the two jobs. In this paper we extend this analysis to include quasi-convex, nonregular objective functions. Unlike classical results on the job shop with two jobs, the optimal schedule may not be semi-active. Both the sum and the maximum of these two objective functions are considered as performance criteria. Our approach consists in first finding a set of nondominated solutions, i.e., schedules which are Paretooptimal from the viewpoint of the two jobs, and then searching for an overall optimum among these solutions. Both steps are carried out in polynomial time, as long as all processing times are integers.

We consider the scenario where two users compete to perform their respective jobs on a common set of resources. The job for each user has a due-date and the cost function associated with the due-date is quasi-convex (i.e., it has a single local minimum). We characterize the set of nondominated schedules over which the users may negotiate and develop a polynomial algorithm to find this nondominated set.

In this paper we address a deterministic scheduling problem in which two agents compete for the usage of a single machine. The agents submit their tasks in successive steps to an external coordinator, who sequences them according to a known priority rule. We introduce the problem for three different shop configurations, namely when the agents' parts are transferred to the machine through two distinct linear conveyor belts, when they are transferred through circular conveyor belts, and when parts can be freely picked from the two agents' buffer. We consider the problem from different perspectives. First, we look at the problem from a centralized point of view as a bicriteria optimization problem and characterize the set of Pareto optimal solutions from the computational complexity perspective. Then, we address the problem from one agent's point of view. In particular, we propose algorithms suggesting to an agent how to sequence its own tasks in order to optimize its own objective function, regardless of the other agents objectives.

A set of n nonpreemptive tasks are to be scheduled on m dedicated machines in order to minimize the overall makespan. Precedence constraints among the tasks, deterministic processing times and processing machine of each task are given. We present lower bounds of the minimum makespan and heuristic algorithms for two relevant cases in manufacturing applications, namely when the precedence constraints form a comb or a caterpillar. Promising preliminary computational tests are also reported proving the efficiency and effectiveness of the proposed solution algorithm.

We address the problem of assigning operations to flexible machines in a manufacturing system in order to minimize handling costs associated to transferring parts between machines. We model this problem as a special discrete optimisation - related to minimum cut - problem on a graph. We use different mathematical programming tools, based on (i) relaxations of integer programming formulations or (ii) combinatorial models of the problem, to provide underestimations of its solution values. The latter ones are useful in exact solution algorithms based on enumeration schemes, like branch and bound or branch and cut. Extensive simulation experiments are carried out to test the performances of different lower bounds on the optimal solution values of our problem and of one more general variant (called metric labelling problem) which is well known in the literature.

A set of n nonpreemptive tasks are to be scheduled on m parallel dedicated machines with a regular criterion. Chain precedence constraints among the tasks, deterministic processing times and processing machine of each task are given. We present computational complexity results and solution algorithms for some special cases. When the precedence relations among the tasks are given by two chains, we provide efficient solution algorithms for the minimization of the weighted sum of task completion times and the number of tardy jobs. Moreover, we show that when minimizing the sum of non-decreasing functions of the completion times of the tasks, a pseudopolynomial time algorithm and a fully polynomial time approximation scheme (FPTAS) exist. Indeed, when the objective is the minimization of the weighted number of tardy jobs or total weighted tardiness the problem is NP-hard in the ordinary sense. Finally, we consider slightly more general precedence structures and show that, even when the precedence constraints form a comb, makespan minimization problem turns out to be strongly NP-hard.

We consider a job-shop scheduling problem with n jobs and the constraint that at most p

This article addresses the problem of allocating users to radio resources in the downlink of an OFDMA cellular system. We consider a classical multicellular environment with a realistic interference model and a margin adaptive approach, i.e., we aim at minimizing total transmission power while maintaining a certain given rate for each user. We discuss computational complexity issues of the resulting model and present a heuristic approach that finds optima under suitable conditions or reasonably good solutions in the general case. Computational experiments show the effectiveness of the proposed heuristic in a comparison with both a commercial state-of-the-art optimization solver and other approaches from the literature. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011 © 2011 Wiley Periodicals, Inc.

In this paper we address a particular generalisation of the Assignment Problem (AP) in a Multi-Agent setting, where distributed agents share common resources. We consider the problem of determining Pareto-optimal solutions that satisfy a fairness criterion (equilibrium). We show that the solution obtained is equivalent to a Kalai-Smorodinsky solution of a suitably defined bargaining problem and characterise the computational complexity of finding such an equilibrium. Additionally, we propose an exact solution algorithm based on a branch-and-bound scheme that exploits bounds obtained by suitably rounding the solutions of the corresponding linear relaxation, and give the results of extensive computational experiments.

We consider the scheduling problems arising when several agents, each owning a set of nonpreemptive jobs, compete to perform their respective jobs on one shared processing resource. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The cost functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs and total weighted completion time. The different combinations of the cost functions of each agent lead to various problems, whose computational complexity is analysed in this paper. In particular, we investigate the problem of finding schedules whose cost for each agent does not exceed a given bound for each agent.

In the layout design phase of a cellular manufacturing system, the objective is to group parts into families having similar characteristics and to identify dedicated sets of machines (cells) to process the different families while minimizing intercell material flows. In the proposed iterative approach (i) a cell formation problem is solved through machine-pair similarity coefficients (optimisation phase), (ii) for the cell configuration obtained, a simulation is performed and performance indicators levels are measured (simulation phase) and (iii) similarity coefficients are re-defined through suitable feedback indicators (feedback phase).

We consider the scheduling problems arising when two agents, each with a set of nonpreemptive jobs, compete to perform their respective jobs on a common processing resource. Each agent wants to minimize a certain objective function, which depends on the completion times of its jobs only. The objective functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs, and total weighted completion times. We obtain different scenarios, depending on the objective function of each agent, and on the structure of the processing system (single machine or shop). For each scenario, we address the complexity of various problems, namely, finding the optimal solution for one agent with a constraint on the other agent's cost function, finding single nondominated schedules (i.e., such that a better schedule for one of the two agents necessarily results in a worse schedule for the other agent), and generating all nondominated schedules.

A districting problem is formulated as a network partitioning model where each link has one weight to denote travel time and another weight to denote workload. The objective of the problem is to minimize the maximum diameter of the districts while equalizing the workload among the districts. The case of tree networks is addressed and efficient algorithms are developed when the network is to be partitioned into two or three districts. c 2002 Wiley Periodicals, Inc. Naval

This work partially reports the results of a study aiming at the design and analysis of the performance of a multi-cab metropolitan transportation system. In our model we investigate a particular multi-vehicle many-to-many dynamic request dial-a-ride problem. We present a heuristic algorithm for this problem and some preliminary results. The algorithm is based on iteratively solving a single-vehicle subproblem at optimality: a pretty efficient dynamic programming routine has been devised for this purpose.

In this paper, we consider the problem of assigning operations to an ordered sequence of non-identical workstations, observing precedence relationships and cycle time restrictions. The objective is to minimize the cost of the workstations. We first present a dynamic programming algorithm, and introduce several fathoming rules in order to reduce the number of states in the dynamic program. A characterization of a wide class of polynomially solvable instances is given, and computational results are reported.

The material flow management of flexible assembly systems requires to assign a set of operations to a set of machines, and to connect machines by a transportation network, such that a number of constraints is satisfied and some efficiency index is optimized Aim of the paper is to give a general framework to formulate and model, in a formal way, different subproblems arising from embedding an assembly process on different configurations of a flexible production system. We analyze several wide used architectures and material flow policies, and point out some useful properties to design decision rules and evaluate the corresponding optimality bounds. The paper also investigates the computational complexity of various subcases of the problem.

In its basic form the management control of a flexible production system requires to assign a set of operations to a set of machines, and to connect machines by a transportation network, such that a number of constraints is satisfied and some efficiency index is optimized. The aim of the work is to give a general framework to formulate and model, in a formal way, different subproblems arising from embedding an assembly process on different configurations of a flexible production system. Because of the complexity of the overall problem, it is useful to have simple and well structured layouts and procedures that help the design and operation of flexible systems. These layouts and procedures induce additional constraints, due to the products' and the process' features. The paper also investigates the complexity of various subcases of the problem.