A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion |
| |
Authors: | Adam Kasperski Pawe? Zieliński |
| |
Institution: | a Institute of Industrial Engineering and Management, Wroc?aw University of Technology, Wybrze?e Wyspiańskiego 27, 50-370 Wroc?aw, Poland b Institute of Mathematics and Computer Science, Wroc?aw University of Technology, Wybrze?e Wyspiańskiego 27, 50-370 Wroc?aw, Poland |
| |
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. |
| |
Keywords: | Scheduling Interval data Minmax regret Approximation algorithm |
本文献已被 ScienceDirect 等数据库收录! |