In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtime optimal schedules, called LD algorithm, has a simple worst-case performance bound: (5m-2)/(4m-1) , where m is the number of machines. We study structure of potential minimal counterexamples to this conjecture and … Read more
We treat uncertain linear programming problems by utilizing the notion of weighted analytic centers and notions from the area of multi-criteria decision making. In addition to many practical advantages, due to the flexibility of our approach, we are able to prove that the robust optimal solutions generated by our algorithms are at least as desirable … Read more
We study the Minimax Regret Uncapacitated Lot Sizing (MRULS) model, where the production cost function and the demand are subject to uncertainty. We propose a polynomial time algorithm which solves the MRULS model in O(n^6) time. We improve this running time to O(n^5) when only the demand is uncertain, and to O(n^4) when only the … Read more
We consider the Train Timetabling Problem (TTP) in a railway node (i.e. a set of stations in an urban area interconnected by tracks), which calls for determining the best schedule for a given set of trains during a given time horizon, while satisfying several track operational constraints. In particular, we consider the context of a … Read more
This paper develops a robust optimization based decision-making framework using a nonparametric perturbation of a reference utility function. The perturbation preserves the risk-aversion property but solves the problem of ambiguity and inconsistency in eliciting the reference utility function. We study the topology of the perturbation, and show that in the decision-making framework the price of … Read more
Given a telecommunication network, modeled by a graph with capacities, we are interested in comparing the behavior and usefulness of two information propagation schemes, namely multicast and network coding, when the aforementioned network is subject to single arc failure. We consider the case with a single source node and a set of terminal nodes. The … Read more
The Internet is currently mostly exploited as a means to perform massive digital content distribution. Such a usage profile was not specifically taken into account while initially designing the architecture of the network: as a matter of fact, the Internet was instead conceived around the concept of host-to-host communications between two remote machines. To solve … Read more
We study the minimum concave cost flow problem over a two-dimensional grid network (CFG), where one dimension represents time ($1\le t\le T$) and the other dimension represents echelons ($1\le l\le L$). The concave function over each arc is given by a value oracle. We give a polynomial-time algorithm for finding the optimal solution when the … Read more
This paper develops some mathematical models arising in psychology and some other areas of behavioral sciences that are formalized via general preferences with variable ordering structures. Our considerations are based on the recent “variational rationality approach” that unifies numerous theories in different branches of behavioral sciences by using, in particular, worthwhile change and stay dynamics … Read more
We consider a cooperative game defined by an economic lot sizing problem with concave ordering costs over a finite time horizon, in which each player faces demand for a single product in each period and coalitions can pool orders. We show how to compute a dynamic cost allocation in the strong sequential core of this … Read more