Scientific report COST-STSM-ECOST-STSM-IC0602-300111-004832

Beneficiary: ALOULOU Mohamed Ali, LAMSADE - Universite Paris-Dauphine

Period : 13-19 February 2011

Host : Federico Della Croce, Politecnico di Torino, Italy

Subject : Just-in-time scheduling problems in the presence of uncertainty : computational complexity and approximation results.

Amount : 900 euros

During my visit to Torino, we dealt with just-in-time single machine scheduling problems in the presence of uncertainty. In such a context, uncertainty or imprecision is structured by means of scenarios, each of which specifies a potential realization of problem parameters (Roy 1998, Vincke 1999). Two natural ways of describing the set S of all possible scenarios have been investigated in the literature. In the interval data case, each parameter may take any value between given lower and upper bounds, independent of the values of the other problem parameters. In the discrete scenario case, the set S is described explicitly. Both cases have been considered. The min-max and min-max regret criteria, stemming from decision theory, are often used to obtain solutions hedging against parameters variations. The study of these criteria is motivated by practical applications where an anticipation of the worst case is crucial. We considered minmax criterion in our work.

To the best of our knowledge, the problem we dealt with has never been considered in the literature. The related papers can be partitioned into two sets. In the first set, we have several papers about just-in time scheduling problems where all problem parameters (processing times, due dates, penalties ...) are known precisely (see for instance Kanet 1981, Hoogoven 1996). In the second set, we have few papers dealing with single machine scheduling problems in the presence of uncertainty with other criteria (Aissi, Aloulou and Kovalyov 2010, Aloulou and Della Croce 2008, Kouvelis and Yu 1997).

We studied the computational complexity of two special cases. We succeed to prove the NP-hardness of one of them and derived exact and approximation algorithms for the second problem. Unfortunately, several questions are still open and we hope providing convincing answers in the near future. A visit of Federico Della Croce to Paris is planned in the late of May and this would help to complete the obtained results.