A generalized bottleneck assignment problem

A solution procedure is presented for a generalization of the standard bottleneck assignment problem in which a secondary criterion is automatically provided. A partitioning problem is modeled by this bottleneck problem to provide an example of its application.     

A multi-level bottleneck assignment approach to the bus drivers' rostering problem

The problem of finding a work assignment for drivers in a given time horizon, in such a way as to have an even distribution of the workload, is considered. This problem is formulated as a Multi-level Bottleneck Assignment Problem (MBA). The MBA problem is studied: it is shown that it is NP-complete and an asymptotically optimal algorithm is presented. Some computational results are illustrated which prove the efficiency of the algorithm.     

The approximability of three-dimensional assignment problems with bottleneck objective

We discuss two special cases of the three-dimensional bottleneck assignment problem where a certain underlying cost function satisfies the triangle inequality. We present polynomial time 2-approximation algorithms for the broadest class of these special cases, and we prove that (unless P = NP) this factor 2 is best possible even in the highly restricted setting of the Euclidean plane.     

Chance constrained bottleneck spanning tree problem

In this paper we consider a stochastic version of the bottleneck spanning tree in which edge costs are independent random variables. Our problem is to find an optimal spanning tree and optimal satisficing level of the chance constraint with respect to the bottleneck (maximum cost) edge of the spanning tree. The problem is first transformed into a deterministic equivalent problem. Then a subproblem in order to solve the problem is introduced and the close relation between these problems is clarified. Finally, based on the relation, polynomial time solution procedures to solve the problem are proposed under two special functions of satisficing level which are given as examples to be solved easily.     

On the bottleneck linear programming problem

In this paper, the results on primal methods for Bottleneck Linear Programming (BLP) problem are briefly surveyed, the primal method is presented and the degenerate case related to Bottleneck Transportation Problem (BTP) is explicitly considered. The algorithm is based on the idea of using auxiliary coefficients as is done by Garfinkel and Rao [6]. The modification presented for the BTP rectifies the defect in Hammer's method in the case of degenerate basic feasible solution. Illustrative numerical examples are also given.     

The stochastic bottleneck linear programming problem

In this paper we consider some stochastic bottleneck linear programming problems. We overview the solution methods in the literature. In the case when the coefficients of the objective functions are simple randomized, the minimum-risk approach will be used for solving these problems. We prove that, under some positivity conditions, these stochastic problems are reduced to certain deterministic bottleneck linear problems. An application of these problems to bottleneck spanning tree problems is given. Two simple numerical examples are presented. This paper was written when I.M. Stancu-Minasian was visiting the Instituto Complutense de Análisis Económico, in the Universidad Complutensen de Madrid, from October 1, 1997 to November 15, 1997 and from October 24, 1998 to November, 9, 1998, as invited researcher. He is grateful to the Institution.     

A personnel assignment problem

The following personnel assignment problem is considered. Let (T, ?) be a linearly ordered set where T is a set (of people), and let (P, ?) be a partially ordered set where P, a set of positions of two types, is of the same cardinality as T. Each person i in T is to be assigned to a position. A feasible assignment of personnel to positions is an embedding of (P, ?) in (T, ?). Given measures of each person's effectiveness in both types of positions, an optimal assignment maximizes the total measure of effectiveness. The general assignment problem is shown to be NP-complete. O(n log n) algorithms for two special cases of the problem are presented.     

Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem

The purpose of this paper is to present heuristics for the bottleneck wandering salesperson problem and the bottleneck vehicle routing problem with the triangle inequality that are guaranteed to produce solutions that have a cost no more than twice the optimum. These heuristics are all best possible in the sense that the existence of a heuristic that guarantees a better ratio would imply that PP = NP, and this is widely believed to be false.     

The bottleneck transportation problem with auxiliary resources

In this paper, we introduce a new extension of the bottleneck transportation problem where additionally auxiliary resources are needed to support the transports. A single commodity has to be sent from supply to demand nodes such that the total demand is satisfied and the time at which all units of the commodity have arrived at the demand nodes is minimized. We show that already the problem with a single demand node and a single auxiliary resource is NP-hard and consider some polynomially solvable special cases.     

The dynamic frequency assignment problem

In this paper, we consider a frequency assignment problem occurring in a military context. The main originality of the problem pertains to its dynamic dimension: new communications requiring frequency assignments need to be established throughout a battlefield deployment. The problem resolution framework decomposes into three phases: assignment of an initial kernel of communications, dynamic assignment of new communication links and a repair process when no assignment is possible. Different solution methods are proposed and extensive computational experiments are carried out on realistic instances.     

The elastic generalized assignment problem

The generalized assignment problem (GAP) has been studied by numerous researchers over the past 30 years or so. Simply stated, one must find a minimum-cost assignment of tasks to agents such that each task is assigned to exactly one agent and such that each agent's resource capacity is honoured. The problem is known to be NP-hard. In this paper, we study the elastic generalized assignment problem (EGAP). The elastic version of GAP allows agent resource capacity to be violated at additional cost. Another version allows undertime costs to be assessed as well if an agent's resource capacity is not used to its full extent. The EGAP is also NP-hard. We describe a special-purpose branch-and-bound algorithm that utilizes linear programming cuts, feasible solution generators, Lagrangean relaxation and subgradient optimization. We present computational results on a large collection of randomly generated ‘hard’ problems with up to 4000 binary variables.     

A multi-period machine assignment problem

In this paper, a multi-period assignment problem is studied that arises as part of a weekly planning problem at mail processing and distribution centers. These facilities contain a wide variety of automation equipment that is used to cancel, sort, and sequence the mail. The input to the problem is an equipment schedule that indicates the number of machines required for each job or operation during the day. This result is then post-processed by solving a multi-period assignment problem to determine the sequence of operations for each machine. Two criteria are used for this purpose. The first is to minimize the number of startups, and the second is to minimize the number of machines used per operation.The problem is modeled as a 0–1 integer program that can be solved in polynomial time when only the first criterion is considered. To find solutions in general, a two-stage heuristic is developed that always obtains the minimum number of startups, but not necessarily the minimum number of machines per operation. In a comparative study, high quality solutions were routinely provided by the heuristic in negligible time when compared to a commercial branch-and-bound code (Xpress). For most hard instances, the branch-and-bound code was not able to even find continuous solutions within acceptable time limits.     

Guaranteed performance heuristics for the bottleneck travelling salesman problem

We consider constant-performance, polynomial-time, nonexact algorithms for the minimax or bottleneck version of the Travelling Salesman Problem. It is first shown that no such algorithm can exist for problems with arbitrary costs unless P = NP. However, when costs are positive and satisfy the triangle inequality, we use results pertaining to the squares of biconnected graphs to produce a polynomial-time algorithm with worst-case bound 2 and show further that, unless P = NP, no polynomial alternative can improve on this value.     

A two-phase heuristic for the bottleneck k-hyperplane clustering problem

In the bottleneck hyperplane clustering problem, given n points in $\mathbb{R}^{d}$ and an integer k with 1≤k≤n, we wish to determine k hyperplanes and assign each point to a hyperplane so as to minimize the maximum Euclidean distance between each point and its assigned hyperplane. This mixed-integer nonlinear problem has several interesting applications but is computationally challenging due, among others, to the nonconvexity arising from the ? ₂-norm. After comparing several linear approximations to deal with the ? ₂-norm constraint, we propose a two-phase heuristic. First, an approximate solution is obtained by exploiting the ? _∞-approximation and the problem geometry, and then it is converted into an ? ₂-approximate solution. Computational experiments on realistic randomly generated instances and instances arising from piecewise affine maps show that our heuristic provides good quality solutions in a reasonable amount of time.     

On the online track assignment problem

This paper aims to start an analytical study of the computational complexity of some online shunting problems. We analyze the following problem. Consider a train station consisting of a set of parallel tracks. Each track can be approached from one side only or from both sides and the number of trains per track may be limited or not. The departure times of the trains are fixed according to a given time table. The problem is to assign a track to each train as soon as it arrives and such that it can leave the station on time without being blocked by any other train.We show that this problem can be modeled with online coloring of graphs. Depending on the constraints, the graphs can be overlap graphs (also known as circle graphs) or permutation graphs, and the coloring can be bounded or classical. This paper covers several combinations of these cases.