On the complexity of constructing a minmax regret solution for the two-machine flow shop problem under the interval unce
- PDF / 281,756 Bytes
- 5 Pages / 595.276 x 790.866 pts Page_size
- 6 Downloads / 200 Views
On the complexity of constructing a minmax regret solution for the two-machine flow shop problem under the interval uncertainty Yakov Shafransky1 · Viktor Shinkarevich2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We prove the NP-hardness of constructing a minmax regret solution for the two-machine flow shop problem under the interval uncertainty of the job processing times. The problem complexity status has been an open question for over the past 20 years. We establish the NP-hardness of this problem using a so-called alternative scheme for proving the NP-hardness of optimization problems. Also, we show that the problem is non-approximable in polynomial time. Keywords Minmax regret · Interval uncertainty · Two-machine flow shop · NP-hardness
1 Introduction The paper is addressed to the classical two-machine flow shop problem F2||Cmax in the situation when the processing times of jobs are uncertain. We have n jobs to be successively processed on two machines. Each job j should be uninterruptedly processed by the first machine during a j time units, then by the second machine during b j time units. Each machine can process at most one job at a time. The objective is to minimize the makespan. A schedule of the job processing may be presented by a permutation π of job numbers (see Johnson 1954). We consider this problem under the interval uncertainty of the processing times of jobs: a j and b j can take any values + − + from the given intervals [a − j , a j ] and [b j , b j ], respectively, j = 1, ..., n. All numbers are supposed to be non-negative rational numbers. Remind that in the deterministic case, the optimal schedule can be constructed in O(n log n) time using Johnson’s algorithm (Johnson 1954). The collection S = ((a1 , b1 ), . . . , (an , bn )), where a j and b j are from the mentioned intervals, is called a scenario. Denote by S the set of all possible scenarios. Let Cmax (π, S)
B
Yakov Shafransky [email protected] Viktor Shinkarevich [email protected]
1
United Institute of Informatics Problems, NAS of Belarus, Minsk, Belarus
2
Belarusian State University, Minsk, Belarus
denote the makespan for permutation π and for the processing times of jobs defined by scenario S. Also, we denote by π ∗ (S) the optimal permutation for scenario S, i.e., the permutation that gives minimum to Cmax (π, S). Introduce function Z (π, S) = max(Cmax (π, S) − Cmax (π ∗ (S), S) S∈S
that is called the maximum regret. Our aim is to find a permutation that gives minimum to the maximum regret. Two most popular ways of defining the uncertainty in the discrete optimization problems are known (see Kasperski 2008, e.g.) The first one is described above, where the scenario set is the Cartesian product of all pairs of intervals + − + ([a − j , a j ], [b j , b j ]), j = 1, ..., n. We call it the interval uncertainty (or the interval scenario representation). Under the interval uncertainty the scenario set is infinite. The second way is to define a scenario set by direct enumeration of all scenarios
Data Loading...
