Philippe BAPTISTE home page

Director of the CNRS institute for information science and technology INS2I
Research Interest: Op. Research, 
Scheduling theory, Constraint Prog.,  Air Traffic Management

Ecole Polytechnique, CNRS LIX, F-91128 Palaiseau. +33 1 69 33 40 56 or +33 6 73 71 05 48

Ads - Books

CBS text book

Editorial Duties

Since january 2009, I'm the editor in chief (jointly with S. Martello and F. Plastria) of
4OR: A Quarterly Journal of Operations Research
(thanks a lot to D. Bouyssou who has been in charge for many years)
I'm also an associate editor of the following journals

Journal of Scheduling

Operations Research Letters

Discrete Optimization


Constraint Programming Letters


I'm / I was also a PC member of
several conferences, including


Some papers in international journal 

  1. Ph. Baptiste. A Note on Scheduling Identical Coupled Tasks In constant Time. Accepted Pending Minor Revision, DAM (Discrete Applied Mathematics)
  2. Ph. Baptiste, R. Sadykov. On scheduling a single machine to minimize a piecewise linear objective function : A compact MIP formulation,  to appear in Naval Research Logistics.
  3. Ph. Baptiste, Ph. Chrétienne, J. Meng-Grard and F. Sourd. On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups. Accepted for publication in DAM (Discrete Applied Mathematics), special issue following GO06.
  4. Ph. Baptiste, F. DellaCroce, A.Grosso, V. T'kindt. Sequencing a single machine with due dates and deadlines: an ILP-based approach to solve very large instances. To appear in Journal of Scheduling. 
  5. G. Nannicini, Ph. Baptiste, G. Barbier, D. Krob, and L. Liberti. Fast paths in large-scale dynamics road networks. Computational Optimization and Applications, 2008 (DOI 10.1007/s10589-008-9172-y)
  6. K. Artiouchine, Ph. Baptiste and J. Mattioli. The K King Problem, an Abstract Model for Computing Aircraft Landing Trajectories: On Modeling a Dynamic Hybrid System with Constraints. INFORMS Journal on Computing, Vol. 20, No. 2, Spring 2008, pp. 222-233.
  7. Jouglet, D. Savourey, J. Carlier and Ph. Baptiste. Dominance-Based Heuristics for One-Machine Total Cost Scheduling Problems. European Journal of Operational Research, Volume 184, Issue 3, 1 February 2008, Pages 879-899
  8. Ph. Baptiste, M. Flamini and F. Sourd. Lagrangian Bounds for Just-In-Time Job-Shop Scheduling.  Computers & Operations Research, Vol 35, N¡3, 2008, pp. 906--915.
  9. Ph. Baptiste, Antoine Jouglet and David Savourey. Lower Bounds for Parallel Machine Scheduling Problems. International Journal of Operational Research 2008 - Vol. 3, No.6  pp. 643 - 664
  10. K. Artiouchine, Ph. Baptiste and C. Durr. Runway Sequencing with Holding Patterns. European Journal of Operational Research. Volume 189, Issue 3, 16 September 2008, Pages 1254-1266 
  11. E. Winter, Ph. Baptiste. On Scheduling a Multifunction Radar. Aerospace Science and Technology, 11 (4), p. 289-294, May 2007.
  12. Ph Baptiste, Peter Brucker, Marek Chrobak, Christoph Durr, Svetlana A. Kravchenko and Francis Sourd. The Complexity of Mean Flow Time Scheduling Problems with Release Times. Journal of Scheduling, Volume 10, Number 2, April 2007, pp. 139-146.
  13. K. Artiouchine and Ph. Baptiste. Arc-B-Consistency of the Inter-Distance Constraint.  Constraints, Volume 12, Number 1, March 2007, pp. 3-19.
  14. Ph. Baptiste and C. Le Pape. Scheduling a Single Machine to Minimize a Regular Objective Function under Setup Constraints. Discrete Optimization 2(2005) 83-99.
  15. Huy Trandac, Ph. Baptiste and Vu Duong. Airspace sectorization with constraints.  RAIRO Oper. Res. 39 (2005) 105-122.
  16. Ph. Baptiste and V. Timkovsky. Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time. Mathematical Methods of Operations Research  Volume 60, Number 1, 145–153, 2004.
  17. Ph. Baptiste, Peter Brucker, Sigrid Knust and Vadim G. Timkovsky. Ten notes on equal-processing-time scheduling. 4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies,  Volume 2, 111 - 127, 2004.
  18. Ph. Baptiste, Chrobak, Durr, Jawor, Vakhania. Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput. Operations Research Letters, Volume 32, Issue 3, 258-264, 2004.
  19. Ph. Baptiste and S. Demassey. Tight LP Bounds for Resource Constrained Project Scheduling. OR Spectrum, 26 : 251 – 262, 2004.
  20. Ph. Baptiste, J. Carlier and A. Jouglet. A Branch-and-Bound Procedure to Minimize Total Tardiness on One Machine with Arbitrary Release Dates. European Journal of Operational research, Vol. 158 595-608, 2004.
  21. Ph. Baptiste. On Minimizing the Weighted Number of Late Jobs in Unit Execution Time Open-Shops. European Journal of Operational Research, Volume 149, 344-354, 2003.
  22. Ph. Baptiste, B. Schieber. A Note on Scheduling Tall/Small Multiprocessor Tasks with Unit Processing Time to Minimize Maximum Tardiness. Journal of Scheduling 6(4): 395-404, 2003.
  23. Ph. Baptiste. A Note on Scheduling Multiprocessor Tasks with Identical Processing times. Computers andOperations Research 30, 2003.
  24. Ph. Baptiste, Laurent Peridy and Eric Pinson . A Branch and Bound to Mininimze the Number of Late Jobs on a Single Machine with Release Time Constraints. European Journal of Operational Research, 144 (1) (2003) 1-11.
  25. E. Néron, Ph. Baptiste, J. Gupta. Solving Hybrid Flow Shop Problem Using Energetic Reasoning and Global Operations. Omega, 29 (2001) 501-511
  26. Ph. Baptiste and A. Jouglet. On Minimizing Total Tardiness in a Serial Batching Problem. RAIRO Operations Research, 35 (2001) 107-115.
  27. Ph. Baptiste and V. G. Timkovsky. On Preemption Redundancy In Scheduling Unit Processing Time Jobs On Two Parallel Machines. Operations Research Letters, 28 (2001) 205-212.
  28. Ph. Baptiste. Batching Identical Jobs. Mathematical Methods of Operation Research, 52 (2000) 355-367.
  29. Ph. Baptiste. Scheduling Equal-Length Jobs on Identical Parallel Machines. Discrete Applied Mathematics, 103(2000) 21-32.
  30. Ph. Baptiste and C. Le Pape. Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problem. Constraints, 5 (2000)119-139.
  31. Ph. Baptiste. Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine when Processing Times are Equal, Journal of Scheduling 2(1999)245-252.
  32. Ph. Baptiste. An O(n4) Algorithm for Preemptive Scheduling of a Single Machine to Minimize the Number of Late Jobs. Operations Research Letters, 24 (1999) 175-180.
  33. Ph. Baptiste, C. Le Pape and W. Nuijten. Satisfiability Tests and Time-Bound Adjustments for Cumulative Scheduling Problems. Annals of Operations Research, 92(1999)305-333.
  34. Le Pape and Ph. Baptiste. Heuristic Control of a Constraint-Based Algorithm for the Preemptive Job-Shop Scheduling Problem. Journal of Heuristics 5 (1999) 305-325.
  35. Le Pape and Ph. Baptiste. Resource Constraints for Preemptive Job-Shop Scheduling. Constraints, 3(4):263-287, 1998.
  36. Ph. Baptiste and C. Le Pape. Disjunctive Constraints for Manufacturing Scheduling: Principles and Extensions. International Journal of Computer Integrated Manufacturing 9(4):306-310, 1996.

Habilitation (HDR), PhD & MSc Thesis

Philippe Baptiste. Resultats de complexité et programmation par contraintes pour l'ordonnancement. Habilitation a diriger des recherches presentee le 1er juillet 2002 devant le jury compose de Jacques Carlier, Philippe Chretienne, Bernard Dubuisson, Pascal van Hentenryck, Jan-Karel Lenstra, Claude Le Pape, Eric Pinson and Baruch Schieber.

Philippe Baptiste.A Theoretical and Experimental Study of Resource Constraint Propagation . PhDThesis, University of Compiègne, 1998. ( Compressed Word version , pdf )

Philippe Baptiste. Resource Constraints for Preemptive and Non-Preemptive Scheduling. MSc Thesis, University Paris VI, 1995. (Compressed postscript version)

Philippe Baptiste. Constraint-Based Scheduling: Two extensions. MSc Thesis, University of Strathclyde, 1994. (Compressed postscript version)

Valid HTML 4.01 Transitional