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

doi:10.1016/j.orl.2007.11.004

Operations Research Letters

Volume 36, Issue 3, May 2008, Pages 343-344

https://doi.org/10.1016/j.orl.2007.11.004 Get rights and content

Abstract

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.

Section snippets

Preliminaries

We are given a set of jobs $J = {J_{1}, \dots, J_{n}}$ to be processed on a single machine. For the sake of simplicity, we will identify every job $J_{i}$ with its index $i$ . A schedule is a permutation $π = (π (1), \dots, π (n))$ of jobs. The set of jobs may be partially ordered by some precedence constraints, namely if $i \to j$ , then job $j$ must be processed after job $i$ . A schedule $π$ is feasible if it satisfies all the precedence constraints. We denote by $Π$ the set of all feasible schedules. Consider the case in which the processing

The main result

Let us denote by $i_{π}$ the position occupying by job $i$ in schedule $π$ . For any two schedules $π$ , $σ$ and scenario $S \in Γ$ the following equality is true: $F (π, S) - F (σ, S) = \sum_{i \in J} (i_{σ} - i_{π}) p_{i}^{S} .$ Using (2) and the definition of the maximal regret (1) one can easily prove that for any two feasible schedules $π$ and $σ$ the following inequality holds: $Z (π) \geq \sum_{{i : i_{σ} > i_{π}}} (i_{σ} - i_{π}) {\bar{p}}_{i} + \sum_{{i : i_{σ} < i_{π}}} (i_{σ} - i_{π}) {\underline{p}}_{i} .$ We now show that any feasible schedules $π$ and $σ$ satisfy the inequality: $Z (σ) \leq Z (π) + \sum_{{i : i_{π} > i_{σ}}} (i_{π} - i_{σ}) {\bar{p}}_{i} + \sum_{{i : i_{π} < i_{σ}}} (i_{π} - i_{σ}) {\underline{p}}_{i} .$

References (9)

A. Kasperski et al.
An approximation algorithm for interval data minmax regret combinatorial optimization problems
Inform. Process. Lett.
(2006)
E.L. Lawler
Sequencing jobs to minimize total weighted completion time subject to precedence constraints
Ann. Discrete Math.
(1978)
V. Lebedev et al.
Complexity of minimizing the total flow time with interval data and minmax regret criterion
Discrete. Appl. Math.
(2006)
P. Brucker
Scheduling Algorithms
(1998)

There are more references available in the full text version of this article.

Cited by (50)

Robust permutation flow shop total weighted completion time problem: Solution and application to the oil and gas industry
2023, Computers and Operations Research
This work proposes exact solution approaches for the $m$ -machine robust permutation flow shop problem, where operation processing times are uncertain and vary in a given interval. Following the concept of budgeted uncertainty, the objective is to obtain a robust scheduling that minimizes the total weighted completion time of the restricted worst-case scenario, in which only a subset of operation processing times will deviate to worst-case values. We develop several robust counterpart formulations, which can be used to derive optimal solutions for medium-sized problem instances by using a Column-and-Constraint Generation algorithm. The efficacy of the solution methods is validated through experiments on three sets of randomly-generated instances. Finally, a case study for the maintenance schedule of Brazilian oil platforms is presented.
Investigating the recoverable robust single machine scheduling problem under interval uncertainty
2022, Discrete Applied Mathematics
We investigate the recoverable robust single machine scheduling problem under interval uncertainty. In this setting, jobs have first-stage processing times $p$ and second-stage processing times $q$ and we aim to find a first-stage and second-stage schedule with a minimum combined sum of completion times, such that at least $Δ$ jobs share the same position in both schedules.
We provide positive complexity results for some important special cases of this problem, as well as derive a 2-approximation algorithm to the full problem. Computational experiments examine the performance of an exact mixed-integer programming formulation and the approximation algorithm, and demonstrate the strength of a proposed polynomial time greedy heuristic.
Robust (min–max regret) single machine scheduling with interval processing times and total tardiness criterion
2020, Computers and Industrial Engineering
Citation Excerpt :
The interval data min–max regret (IDMR) versions of the classical combinatorial optimization and machine scheduling problems have been studied widely in the literature. In general, the min–max regret versions of classical combinatorial optimization problems are harder than their classical counterparts, since uncertainty increases the search space to find an optimal solution (c.f. Aissi et al., 2005; Averbakh, 2001; Feizollahi & Averbakh, 2014; Kasperski & ZielińSki, 2008; Montemanni et al., 2007). It is relatively easy to determine the worst-case scenario for a feasible solution for many combinatorial optimization problems with interval data such as the 0-1 knapsack problem (Aissi et al., 2009; Furini et al., 2015) whose worst-case scenario of a solution has the lower bound profits for the selected items, and the upper bound profits for the non-selected items, and the traveling salesman problem (Montemanni et al., 2007) whose worst-case scenario of a solution has the upper bound costs for the selected arcs, and the lower bound costs for the non-selected arcs.
This paper studies a robust (min–max regret) single machine scheduling problem with uncertain processing times represented by interval data. The objective is to obtain robust sequences of jobs that minimize the absolute deviation of total tardiness from the optimal solution under the worst-case scenario. The problem is first formulated as a mixed-integer linear programming (MILP) model and assuming that the corresponding deterministic NP-hard problem for the mid-point scenario can be solved optimally, an optimal schedule under the mid-point scenario is then proved to be a 2-approximation solution to the problem. Next, the worst-case scenarios are proved to be not necessarily at the upper or lower limits of the interval processing times. Utilizing these results, a 2-approximation algorithm (2AA), a worst-case scenario-based heuristic (WSH), and an approximate worst-case-based heuristic (AWH) are proposed and empirically evaluated, in which an iterative procedure for evaluating the maximum regret of a solution is integrated. Finally, the paper is concluded by suggesting some fruitful directions for future research in this area.
Robust minmax regret combinatorial optimization problems with a resource–dependent uncertainty polyhedron of scenarios
2019, Computers and Operations Research
A new minmax regret optimization model with a partially controllable set of uncertain parameters is studied in this paper. It is considered a combinatorial optimization problem with a vector of uncertain costs belonging to a given polyhedron. This uncertainty polyhedron allows us to model dependency relations among the unknown parameters of any possible scenario. Moreover, we will assume that we can modify the uncertainty polyhedron by investing a set of available resources in the system. Some properties of the resulting Mathematical Programming formulation are stated and a Benders decomposition algorithmic approach is experimentally analyzed through its application to a Scheduling problem with uncertain processing times.
Scheduling under linear constraints
2016, European Journal of Operational Research
We introduce a parallel machine scheduling problem in which the processing times of jobs are not given in advance but are determined by a system of linear constraints. The objective is to minimize the makespan, i.e., the maximum job completion time among all feasible choices. This novel problem is motivated by various real-world application scenarios. We discuss the computational complexity and algorithms for various settings of this problem. In particular, we show that if there is only one machine with an arbitrary number of linear constraints, or there is an arbitrary number of machines with no more than two linear constraints, or both the number of machines and the number of linear constraints are fixed constants, then the problem is polynomial-time solvable via solving a series of linear programming problems. If both the number of machines and the number of constraints are inputs of the problem instance, then the problem is NP-Hard. We further propose several approximation algorithms for the latter case.
Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty
2016, European Journal of Operational Research
Citation Excerpt :
Combinatorial optimization problems under scenario-based uncertainty have been extensively studied in Aissi, Bazgan, and Vanderpooten (2007); 2009); Kasperski and Zielinski (2006); Kouvelis and Yu (1997). In Daniels and Kouvelis (1995); Kasperski and Zielinski (2008); Kouvelis, Daniels, and Vairaktarakis (2000); Lebedev and Averbakh (2006), the approaches developed above have been applied to machine scheduling problems. Daniels and Kouvelis (1995), Lebedev and Averbakh (2006), and Kasperski and Zielinski (2008) considered the min-max regret version of a single-machine scheduling problem to minimize the total completion time with uncertain processing times.
We consider the min-max regret version of a single-machine scheduling problem to determine which jobs are processed by outsourcing under processing time uncertainty. The performance measure is expressed as the total cost for processing some jobs in-house and outsourcing the rest. Processing time uncertainty is described through two types of scenarios: either an interval scenario or a discrete scenario. The objective is to minimize the maximum deviation from optimality over all scenarios. We show that when the cost for in-house jobs is expressed as the makespan, the problem with an interval scenario is polynomially solvable, while the one with a discrete scenario is NP-hard. Thus, for the discrete scenario case, we develop a 2-approximation algorithm and investigate when the problem is polynomially solvable. Since the problem minimizing the total completion time as a performance measure for in-house jobs is known to be NP-hard for both scenarios, we consider the problem with a special structure for the processing time uncertainty and develop a polynomial-time algorithm for both scenarios.

View all citing articles on Scopus

View full text

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

Abstract

Section snippets

Preliminaries

The main result

Inform. Process. Lett.

Ann. Discrete Math.

Discrete. Appl. Math.

Scheduling Algorithms