A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion

In this paper we discuss a minmax regret version of the single-machine scheduling problem with the total flow time criterion. Uncertain processing times are modeled by closed intervals. We show that if the deterministic problem is polynomially solvable, then its minmax regret version is approximable within 2.     

Computing and minimizing the relative regret in combinatorial optimization with interval data

We consider combinatorial optimization problems with uncertain parameters of the objective function, where for each uncertain parameter an interval estimate is known. It is required to find a solution that minimizes the worst-case relative regret. For minmax relative regret versions of some subset-type problems, where feasible solutions are subsets of a finite ground set and the objective function represents the total weight of elements of a feasible solution, and for the minmax relative regret version of the problem of scheduling n jobs on a single machine to minimize the total completion time, we present a number of structural, algorithmic, and complexity results. Many of the results are based on generalizing and extending ideas and approaches from absolute regret minimization to the relative regret case.     

On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data

The general problem of minimizing the maximal regret in combinatorial optimization problems with interval costs is considered. Some results are proven that allow to obtain a fully polynomial time approximation scheme (FPTAS) for the problem under the assumption that a pseudopolynomial algorithm is given.     

A 2-approximation for minmax regret problems via a mid-point scenario optimal solution

In this note, a 2-approximation method for minmax regret optimization problems is developed which extends the work of Kasperski and Zielinski [A. Kasperski, P. Zielinski, An approximation algorithm for interval data minmax regret combinatorial optimization problems, Information Processing Letters 97 (2006) 177-180] from finite to compact constraint sets.     

Some tractable instances of interval data minmax regret problems

In this paper, we provide polynomial and pseudopolynomial algorithms for classes of particular instances of interval data minmax regret graph problems. These classes are defined using a parameter that measures the distance from well-known solvable instances. Tractable cases occur when the parameter is bounded by a constant.     

The minmax regret gradual covering location problem on a network with incomplete information of demand weights

The gradual covering location problem seeks to establish facilities on a network so as to maximize the total demand covered, allowing partial coverage. We focus on the gradual covering location problem when the demand weights associated with nodes of the network are random variables whose probability distributions are unknown. Using only information on the range of these random variables, this study is aimed at finding the “minmax regret” location that minimizes the worst-case coverage loss. We show that under some conditions, the problem is equivalent to known location problems (e.g. the minmax regret median problem). Polynomial time algorithms are developed for the problem on a general network with linear coverage decay functions.     

Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights

This paper deals with a general combinatorial optimization problem in which closed intervals and fuzzy intervals model uncertain element weights. The notion of a deviation interval is introduced, which allows us to characterize the optimality and the robustness of solutions and elements. The problem of computing deviation intervals is addressed and some new complexity results in this field are provided. Possibility theory is then applied to generalize a deviation interval and a solution concept to fuzzy ones.     

A minmax regret approach to the critical path method with task interval times

The execution of a given project, with a number of interrelated tasks due to precedence constraints, represents a challenge when one must to control the available resources and the compromised due dates. In this paper, we analyse this problem under uncertain individual task completing times, specifically, we will assume that a given range, for the admissible values of each individual completing time, is available. Taking into account that the precedence relations between tasks must be preserved, each realization of the admissible execution times for the set of tasks will define a new scenario determining the ending time for the project and the subset of critical tasks.     

Complexity of the min-max and min-max regret assignment problems

This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment problem is strongly NP-hard.     

Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion

In this paper, the single machine sequencing problem with maximum lateness criterion is discussed. The parameters of the problem are imprecise and they are specified as intervals. The maximal regret criterion is applied to calculate the optimal sequence. A polynomial algorithm for the studied problem is constructed.     

On the complexity of the continuous unbounded knapsack problem with uncertain coefficients

In this paper, a linear-time algorithm is developed for the minmax-regret version of the continuous unbounded knapsack problem with n items and uncertain objective function coefficients, where the interval estimates for these coefficients are known. This improves the previously known bound of time for this optimization problem.     

A tabu search algorithm for the minmax regret minimum spanning tree problem with interval data

This paper deals with the strongly NP-hard minmax regret version of the minimum spanning tree problem with interval costs. The best known exact algorithms solve the problem in reasonable time for rather small graphs. In this paper an algorithm based on the idea of tabu search is constructed. Some properties of the local minima are shown. Exhaustive computational tests for various classes of graphs are performed. The obtained results suggest that the proposed tabu search algorithm quickly outputs optimal solutions for the smaller instances, previously discussed in the existing literature. Furthermore, some arguments that this algorithm performs well also for larger instances are provided.     

On the complexity of the robust spanning tree problem with interval data

This paper studies the complexity of the robust spanning tree problem with interval data (RSTID). It shows that the problem is NP-complete, settling the conjecture of Kouvelis and Yu, and that it remains so for complete graphs or when the intervals are all [0,1]. These results indicate that the difficulty of RSTID stems from both the graph topology and the structure of the cost intervals, suggesting new directions for search algorithms.     

Complexity of flow time minimization in a crossdock truck scheduling problem with asymmetric handover relations

We address a novel truck scheduling problem arising in crossdocking logistics, in which inbound trucks carry items (pallets) which must be sorted and loaded onto outbound trucks. We minimize the utilisation of the warehouse by focusing on the synchronisation between the different related trucks. The problem is to assign the trucks to the doors of the warehouse and sequence them, in order to minimize the total time spent in the system by the pallets. We discuss the complexity of the problem, showing that even with a single door the problem is NP-hard in general, and discuss some special cases.     

Robust multi-market newsvendor models with interval demand data

We present a robust model for determining the optimal order quantity and market selection for short-life-cycle products in a single period, newsvendor setting. Due to limited information about demand distribution in particular for short-life-cycle products, stochastic modeling approaches may not be suitable. We propose the minimax regret multi-market newsvendor model, where the demands are only known to be bounded within some given interval. In the basic version of the problem, a linear time solution method is developed. For the capacitated case, we establish some structural results to reduce the problem size, and then propose an approximation solution algorithm based on integer programming. Finally, we compare the performance of the proposed minimax regret model against the typical average-case and worst-case models. Our test results demonstrate that the proposed minimax regret model outperformed the average-case and worst-case models in terms of risk-related criteria and mean profit, respectively.     

A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines

The paper proposes a Mixed Integer Programming (MIP) formulation of the scheduling problem with total flow criterion on a set of parallel unrelated machines under an uncertainty context about the processing times. To model the problem we assume that lower and upper bounds are known for each processing time. In this context we consider an optimal minmax regret schedule as a suitable approximation to the optimal schedule under an arbitrary choice of the possible processing times.     

Proportion-based robust optimization and team orienteering problem with interval data

In this paper, a proportion-based robust optimization approach is developed to deal with uncertain combinatorial optimization problems. This approach assumes that a certain proportion of uncertain coefficients in each solution are allowed to change and optimizes a deterministic model so as to achieve a trade-off between optimality and feasibility when the coefficients change. We apply this approach on team orienteering problem with interval data (TOPID), a variant of vehicle routing problem, which has not yet been studied before. A branch and price algorithm is proposed to solve the robust counterpart by using two novel dominance relations. Finally, numerical study is performed. The results show the usefulness of the proposed robust optimization approach and the effectiveness of our algorithm.     

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε$2+\epsilon$.     

Pinpointing the complexity of the interval min–max regret knapsack problem

We show that a natural robust optimization variant of the knapsack problem is complete for the second level of the polynomial hierarchy.