
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, F91128 Palaiseau. +33 1 69 33 40 56 or +33 6 73 71 05 48 Philippe.Baptiste@polytechnique.fr
Ads  Books
Editorial Duties
Some papers in international journal
 Ph. Baptiste.
A Note on Scheduling Identical Coupled Tasks In constant Time. Accepted Pending
Minor Revision, DAM (Discrete Applied
Mathematics)
 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.
 Ph. Baptiste, Ph. ChrÃ©tienne, J.
MengGrard 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.
 Ph. Baptiste,
F. DellaCroce, A.Grosso, V. T'kindt. Sequencing a single machine
with due dates and deadlines: an ILPbased approach to solve very large
instances. To appear in Journal of
Scheduling.
 G. Nannicini, Ph. Baptiste, G. Barbier, D.
Krob, and L. Liberti. Fast paths in largescale dynamics road networks. Computational Optimization and Applications,
2008 (DOI 10.1007/s105890089172y)
 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.
222233.
 Jouglet, D. Savourey, J. Carlier and Ph. Baptiste. DominanceBased
Heuristics for OneMachine Total Cost Scheduling Problems. European Journal
of Operational Research, Volume 184, Issue 3, 1 February 2008, Pages
879899
 Ph. Baptiste, M. Flamini and F. Sourd. Lagrangian
Bounds for JustInTime JobShop Scheduling. Computers &
Operations Research, Vol 35, NÂ¡3, 2008, pp. 906915.
 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
 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 12541266
 E. Winter, Ph. Baptiste. On Scheduling a Multifunction
Radar. Aerospace Science and Technology, 11 (4), p. 289294, May 2007.
 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. 139146.
 K. Artiouchine and Ph. Baptiste. ArcBConsistency of the InterDistance
Constraint. Constraints, Volume
12, Number 1, March 2007, pp. 319.
 Ph. Baptiste and C. Le Pape. Scheduling a Single
Machine to Minimize a Regular Objective Function under Setup Constraints. Discrete
Optimization 2(2005) 8399.
 Huy Trandac, Ph. Baptiste and Vu Duong. Airspace sectorization with
constraints. RAIRO Oper. Res. 39 (2005)
105122.
 Ph. Baptiste and V. Timkovsky. Shortest path to
nonpreemptive schedules of unittime jobs on two identical parallel machines
with minimum total completion time. Mathematical Methods of Operations Research Volume
60, Number 1, 145â153, 2004.
 Ph. Baptiste, Peter Brucker, Sigrid Knust and
Vadim G. Timkovsky. Ten notes on equalprocessingtime scheduling. 4OR:
Quarterly Journal of the Belgian, French and Italian Operations Research
Societies,
Volume 2, 111  127, 2004.
 Ph. Baptiste, Chrobak, Durr, Jawor, Vakhania.
Preemptive Scheduling of EqualLength Jobs to Maximize Weighted Throughput. Operations
Research Letters, Volume 32, Issue 3, 258264,
2004.
 Ph. Baptiste and S. Demassey. Tight LP Bounds for
Resource Constrained Project Scheduling. OR Spectrum, 26
: 251 â 262, 2004.
 Ph. Baptiste, J. Carlier and A. Jouglet. A BranchandBound Procedure to Minimize
Total Tardiness on One Machine with Arbitrary Release Dates. European Journal of Operational research,
Vol. 158 595608, 2004.
 Ph.
Baptiste. On Minimizing
the Weighted Number of Late Jobs in Unit Execution Time OpenShops.
European Journal of Operational Research, Volume 149, 344354,
2003.
 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): 395404, 2003.
 Ph.
Baptiste. A Note on
Scheduling Multiprocessor Tasks with Identical Processing times. Computers
andOperations Research 30, 2003.
 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)
111.
 E.
NÃ©ron, Ph. Baptiste, J. Gupta. Solving
Hybrid Flow Shop Problem Using Energetic Reasoning and Global Operations. Omega, 29 (2001) 501511
 Ph. Baptiste and A. Jouglet. On
Minimizing Total Tardiness in a Serial Batching Problem. RAIRO Operations
Research, 35 (2001) 107115.
 Ph. Baptiste and V. G. Timkovsky. On Preemption
Redundancy In Scheduling Unit Processing Time Jobs On Two Parallel Machines. Operations
Research Letters, 28 (2001) 205212.
 Ph. Baptiste. Batching Identical Jobs. Mathematical Methods of Operation Research, 52 (2000) 355367.
 Ph. Baptiste. Scheduling EqualLength Jobs on
Identical Parallel Machines. Discrete
Applied Mathematics, 103(2000) 2132.
 Ph. Baptiste and C. Le Pape. Constraint Propagation and Decomposition Techniques for
Highly Disjunctive and Highly Cumulative Project Scheduling Problem. Constraints, 5 (2000)119139.
 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)245252.
 Ph. Baptiste. An O(n^{4})
Algorithm for Preemptive Scheduling of a Single Machine to Minimize the Number
of Late Jobs. Operations Research
Letters, 24 (1999) 175180.
 Ph. Baptiste, C. Le Pape and W.
Nuijten. Satisfiability Tests
and TimeBound Adjustments for Cumulative Scheduling Problems. Annals of Operations Research,
92(1999)305333.
 Le Pape and Ph. Baptiste. Heuristic Control of
a ConstraintBased Algorithm for the Preemptive JobShop Scheduling Problem. Journal of Heuristics 5 (1999) 305325.
 Le Pape and Ph. Baptiste. Resource Constraints
for Preemptive JobShop Scheduling. Constraints,
3(4):263287, 1998.
 Ph. Baptiste and C. Le Pape. Disjunctive
Constraints for Manufacturing Scheduling: Principles and Extensions. International Journal of Computer Integrated
Manufacturing 9(4):306310, 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, JanKarel 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 NonPreemptive Scheduling. MSc Thesis, University Paris VI, 1995. (Compressed postscript version)
Philippe Baptiste. ConstraintBased Scheduling: Two extensions. MSc Thesis, University of Strathclyde, 1994. (Compressed postscript version)