Min-Max Regret Version of an m-Machine Ordered Flow Shop with Uncertain Processing Times

We consider an m-machine flow shop scheduling problem to minimize the latest completion time, where processing times are uncertain. Processing time uncertainty is described through a finite set of processing time vectors. The objec-tive is to minimize maximum deviation from optimality for all scenarios. Since this problem is known to be NP-hard, we consider it with an ordered property. We discuss optimality properties and develop a pseudo-polynomial time ap-proach for the problem with a fixed number of machines and scenarios. Furthermore, we find two special structures for processing time uncertainty that keep the problem NP-hard, even for two machines and two scenarios. Finally, we investigate a special structure for uncertain processing times that makes the problem polynomially solvable.