Applications : Job-shop scheduling Project scheduling Engineering activity planning in aeronautics Pilot training timetabling Instruction scheduling on parallel architectures

Methods: Temporal reasoning Constraint propagation Tree search Graph algorithms Integer linear programming

A first work deals with the design of new scheduling models and algorithms, either to improve the state-of-the-art results of known NP-hard scheduling problems, or to solve new problems with complex constraints issued from real applications. The problems under study integrate some of the following constraints: cumulative resources, setup times, generalized precedence constraints, resource flexibility, cyclic scheduling. We are more particularly concerned with the proposition of new ILP formulations, discrepancy-based tree search procedures and constraint propagation techniques. We obtained the best existing results for hybrid flow-shops, job-shops with setup times and resource-constrained project scheduling problems (Fig 2). We also proposed complexity results for task insertion problems.

A second part focuses on the determination of robust schedules. The robustness is obtained by computing a set of solutions having a known worst performance and a known cardinality. The main difficulty is to characterize a large set of solutions in such a way that its worst performance and cardinality can be computed in polynomial time, while avoiding the enumeration of the solutions it contains. For this purpose, considering the particular single machine scheduling problem, some dominance conditions have been put in evidence that allow to characterize a set of dominant solutions having the sought properties. We also study cooperative approaches. It is assumed that the global schedule is built up by successive negotiations between resources, each resource managing its own local robust schedule, using the robust scheduling technique. The goal is to make a relevant trade-off between the local resource objectives and a global objective.

Contacts : Christian Artigues, Cyril Briand, Patrick Esquirol, Marie-José Huguet, Pierre Lopez

PhD student : Hassen Gharbi, Maria Ayala, Abir Ben Hmida, Bernat Gacias, Oumar Kone

Selected publications (see complete list on LAAS server) :

• C.ARTIGUES, D.FEILLET, A branch and bound method for the job-shop problem with sequence-dependent setup times, Annals of Operation Research, Vol.159, N°1, pp.135-159, Mars 2008

• C.BRIAND, H.T.LA, J.ERSCHLER, A robust approach for the single machine scheduling problem, Journal of Scheduling, Vol.10, N°3, pp.209-221, Juin 2007

• A.BEN HMIDA, M.J.HUGUET, P.LOPEZ, M.HAOUARI, Climbing depth-bounded discrepancy search for solving hybrid flow shop problems, European Journal of Industrial Engineering, Vol.1, N°2, pp.223-243, Juillet 2007

• I.LIZARRALDE, P.ESQUIROL, A.RIVIERE, Adapting project management to complex systems development reality: a maturity and energy constraints based approach, 16th CIRP International Design Seminar, Alberta (Canada), 16-19 Juillet 2006

• J.F.HERNANDEZ-SILVA, C.MERCE, G.FONTAN, A multilevel approach for scheduling and capacity management, International Conference on Industrial Engineering and Systems Management (IESM'07), Beijing (Chine), 30 mai - 2 Juin 2007