Philippe Baptiste

Last updated
DR
Philippe Baptiste
Space Symposium - CNES Bilateral Meeting (NHQ202108250016) (cropped).jpg
Born (1972-03-28) March 28, 1972 (age 52)
NationalityFrench
Alma mater University of Technology of Compiègne, University of Strathclyde, Sorbonne University
Occupation(s)Academician, Civil Engineer, Scientist
TitleCEO of CNES

Philippe Baptiste (born March 28, 1972) is a French engineer, academic and researcher. Baptiste is most well known as the president of the National Centre for Space Studies CNES in addition to his several books and scientific publications and communications in the field of algorithms, combinatorial optimization, operational research and artificial intelligence. [1]

Contents

Early life and education

Baptiste was born on March 28, 1972, in France. Baptise holds a PHD in computer science from the University of Technology of Compiègne additionally he is a civil engineering graduate from the Ecole des Mines engineering school in Nancy. Baptise also holds a Msc from the University of Strathclyde, Glasgow and holds a DEA postgraduate diploma from Sorbonne University and is a research director. [1] [2] Baptiste specialises in operational research and artificial intelligence(AI), combinatorial optimisation, and algorithms.

Career

In 1999 during his academic career, Baptiste was a researcher at the French National scientific research centre (CNRS), in addition to IBM's Watson Research Center during 2000 to 2001. [1]

Furthermore, for more than ten years during 2001 to 2012 Baptiste was a lecturer at France's Ecole Polytechnique engineering school. During this time he published several books and around 150 scientific papers, and became the head of Ecole Polytechnique engineering school's information technology laboratory and is credited with creating the Institute of Information Sciences and Interactions prior to being appointed Associate Director General in 2014 of CNRS. [1]

In 2016, Baptiste was appointed as Chief Scientific Officer and later in 2017 named Chief Technology Officer of oil, natural gas, and speciality chemicals company Total. Furthermore, Baptiste has aided in founding and developing a number of start-ups and followed several collaborations with digital, defence and aviation manufactures. [1]

During May 2017 to 2019, Batiste was named chief of staff to French-based biochemist, academic administrator, and politician who served as Minister of Higher Education Frédérique Vidal. After which in 2019 Batiste was an advisor to the French prime Minister Édouard Philippe, During this time Batiste was in close connection with the space policy. [1]

During 2020, Baptiste was appointed Partner and Director of American global management consulting firm Boston Consulting Group. [1]

Recognition

During 1999, Batisete was awarded the Prix Robert Faure award by the French Operations Research & Decision Support Society(ROADEF), a non-profit society that aims to promote scientific fields of operations Research and Decision in France. The award is in tribute to Professor Robert Faure and available to younger researchers (under 36) who are members of ROADEF, and is awarded every 3 years. [3]

In November 2000, Batiste was awarded the Cor Baayen Award for his PHD thesis in an ERCIM country which include: Cyprus, Poland, France, Germany, Austria, Greece, Italy, Norway, Portugal, The Netherlands, Finland and Sweden. Baptiste won this award fue to the quality of his PHD thesis and his previous publications and achievements up to the year 2000. [4]

Publications

2010–2019

2018

  • Philippe Baptiste, Nicolas Bonifas: Redundant cumulative constraints to compute preemptive bounds. Discret. Appl. Math. 234: 168-177 (2018) [5]

2017

  • Philippe Baptiste, Mikhail Y. Kovalyov, Yury L. Orlovich, Frank Werner, Igor E. Zverovich: Graphs with maximal induced matchings of the same size. Discret. Appl. Math. 216: 15-28 (2017) [6]

2012

  • Philippe Baptiste, Jacques Carlier, Alexander V. Kononov, Maurice Queyranne, Sergey Sevastyanov, Maxim Sviridenko: Integer preemptive scheduling on parallel machines. Oper. Res. Lett. 40(6): 440-444 (2012) [7]
  • Philippe Baptiste, Marek Chrobak, Christoph Dürr: Polynomial-time algorithms for minimum energy scheduling. ACM Trans. Algorithms 8(3): 26:1-26:29 (2012) [8]

2011

  • Philippe Baptiste, Jacques Carlier, Alexander V. Kononov, Maurice Queyranne, Sergey Sevastyanov, Maxim Sviridenko: Properties of optimal schedules in preemptive shop scheduling. Discret. Appl. Math. 159(5): 272-280 (2011) [9]

2010

  • Giacomo Nannicini, Philippe Baptiste, Gilles Barbier, Daniel Krob, Leo Liberti: Fast paths in large-scale dynamic road networks. Comput. Optim. Appl. 45(1): 143-158 (2010) [10]
  • Philippe Baptiste:A note on scheduling identical coupled tasks in logarithmic time. Discret. Appl. Math. 158(5): 583-587 (2010) [11]
  • Philippe Baptiste, Ruslan Sadykov: Time-indexed formulations for scheduling chains on a single machine: An application to airborne radars. Eur. J. Oper. Res. 203(2): 476-483 (2010) [12]
  • Philippe Baptiste, Federico Della Croce, Andrea Grosso, Vincent T'kindt: Sequencing a single machine with due dates and deadlines: an ILP-based approach to solve very large instances. J. Sched. 13(1): 39-47 (2010) [13]
  • Marek Chrobak, Philippe Baptiste, Christoph Dürr:Polynomial Time Algorithms for Minimum Energy Scheduling. Scheduling 2010 [14]

1999–2009

2009

  • J. Meng-Gérard, Philippe Chrétienne, Philippe Baptiste, Francis Sourd: On maximizing the profit of a satellite launcher: Selecting and scheduling tasks with time windows and setups. Discret. Appl. Math. 157(17): 3656-3664 (2009) [15]
  • Philippe Baptiste, Graham Kendall, Alix Munier, Francis Sourd: Preface. J. Sched. 12(6): 563-564 (2009) [16]
  • Philippe Baptiste: Constraint-Based Schedulers, Do They Really Work? CP 2009: 1 [17]
  • Philippe Baptiste, Jacques Carlier, Alexander V. Kononov, Maurice Queyranne, Sergey Sevastyanov, Maxim Sviridenko: Integrality Property in Preemptive Parallel Machine Scheduling. CSR 2009: 38-46 [18]
  • Philippe Baptiste, Marek Chrobak, Christoph Dürr: Polynomial Time Algorithms for Minimum Energy Scheduling. CoRR abs/0908.3505 (2009) [19]

2008

  • Philippe Baptiste, Marta Flamini, Francis Sourd: Lagrangian bounds for just-in-time job-shop scheduling. Comput. Oper. Res. 35(3): 906-915 (2008) [20]
  • Antoine Jouglet, David Savourey, Jacques Carlier, Philippe Baptiste: Dominance-based heuristics for one-machine total cost scheduling problems. Eur. J. Oper. Res. 184(3): 879-899 (2008) [21]
  • Konstantin Artiouchine, Philippe Baptiste, Christoph Dürr: Runway sequencing with holding patterns. Eur. J. Oper. Res. 189(3): 1254-1266 (2008) [22]
  • Konstantin Artiouchine, Philippe Baptiste, Juliette Mattioli: The K King Problem, an Abstract Model for Computing Aircraft Landing Trajectories: On Modeling a Dynamic Hybrid System with Constraints. INFORMS J. Comput. 20(2): 222-233 (2008) [23]
  • Giacomo Nannicini, Philippe Baptiste, Daniel Krob, Leo Liberti: Fast Computation of Point-to-Point Paths on Time-Dependent Road Networks. COCOA 2008: 225-234 [24]

2007

  • Konstantin Artiouchine, Philippe Baptiste: Arc-B-consistency of the Inter-distance Constraint. Constraints An Int. J. 12(1): 3-19 (2007) [25]
  • Philippe Baptiste: Book review. Oper. Res. Lett. 35(1): 139-140 (2007) [26]
  • Philippe Baptiste, Peter Brucker, Marek Chrobak, Christoph Dürr, Svetlana A. Kravchenko, Francis Sourd: The complexity of mean flow time scheduling problems with release times. J. Sched. 10(2): 139-146 (2007) [27]
  • Giacomo Nannicini, Philippe Baptiste, Daniel Krob, Leo Liberti: Fast point-to-point shortest path queries on dynamic road networks with internal data. CTW 2007: 115-118 [28]
  • Philippe Baptiste, Marek Chrobak, Christoph Dürr: Polynomial Time Algorithms for Minimum Energy Scheduling. ESA 2007: 136-150 [29]
  • Giacomo Nannicini, Philippe Baptiste, Gilles Barbier, Daniel Krob, Leo Liberti: Fast paths in large-scale dynamic road networks. CoRR abs/0704.1068 (2007) [28]

2006

  • David Savourey, Philippe Baptiste, Antoine Jouglet: Lower bounds for parallel machines scheduling. RIVF 2006: 195-198 [30]
  • Philippe Baptiste: Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. SODA 2006: 364-367 [31]
  • Philippe Baptiste, Philippe Laborie, Claude Le Pape, Wim Nuijten: Constraint-Based Scheduling and Planning. Handbook of Constraint Programming 2006: 761-799 [32]
  • Philippe Baptiste, Peter Brucker, Marek Chrobak, Christoph Dürr, Svetlana A. Kravchenko, Francis Sourd: The Complexity of Mean Flow Time Scheduling Problems with Release Times. CoRR abs/cs/0605078 (2006) [33]

2005

  • Philippe Baptiste, Claude Le Pape: Scheduling a single machine to minimize a regular objective function under setup constraints. Discret. Optim. 2(1): 83-99 (2005) [34]
  • Huy Trandac, Philippe Baptiste, Vu Duong: Airspace sectorization with constraints. RAIRO Oper. Res. 39(2): 105-122 (2005) [35]
  • Konstantin Artiouchine, Philippe Baptiste:Inter-distance Constraint: An Extension of the All-Different Constraint for Scheduling Equal Length Jobs. CP 2005: 62-76 [36]

2004

  • Philippe Baptiste, Peter Brucker, Sigrid Knust, Vadim G. Timkovsky: Ten notes on equal-processing-time scheduling. 4OR 2(2): 111-127 (2004) [37]
  • Philippe Baptiste, Jacques Carlier, Alix Munier, Andreas S. Schulz: Introduction. Ann. Oper. Res. 129(1-4): 17-19 (2004) [38]
  • Philippe Baptiste, Jacques Carlier, Antoine Jouglet: A Branch-and-Bound procedure to minimize total tardiness on one machine with arbitrary release dates. Eur. J. Oper. Res. 158(3): 595-608(2004) [39]
  • Philippe Baptiste, Vadim G. Timkovsky: Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time. Math. Methods Oper. Res. 60(1): 145-153 (2004) [40]
  • Philippe Baptiste, Marek Chrobak, Christoph Dürr, Wojciech Jawor, Nodari Vakhania: Preemptive scheduling of equal-length jobs to maximize weighted throughput. Oper. Res. Lett. 32(3): 258-264 (2004) [41]
  • Philippe Baptiste, Sophie Demassey: Tight LP bounds for resource constrained project scheduling. OR Spectr. 26(2): 251-262 (2004) [42]
  • Dac-Huy Tran, Philippe Baptiste, Vu Duong: From Sets to Geometrical Sectors in the Airspace Sectorization Problem. RIVF 2004: 7-10 [43]
  • Philippe Baptiste, Peter Brucker: Scheduling Equal Processing Time Jobs. Handbook of Scheduling 2004 [5]
  • Antoine Jouglet, Philippe Baptiste, Jacques Carlier: Branch-and-Bound Algorithms for TotalWeighted Tardiness. Handbook of Scheduling 2004 [5]
  • Philippe Baptiste, Marek Chrobak, Christoph Dürr, Francis Sourd: Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time. CoRR abs/cs/0412094 (2004) [44]

2003

  • Philippe Baptiste: A note on scheduling multiprocessor tasks with identical processing times. Comput. Oper. Res. 30(13): 2071-2078 (2003) [45]
  • Philippe Baptiste, Laurent Péridy, Eric Pinson: A branch and bound to minimize the number of late jobs on a single machine with release time constraints. Eur. J. Oper. Res. 144(1): 1-11(2003) [46]
  • Philippe Baptiste: On minimizing the weighted number of late jobs in unit execution time open-shops. Eur. J. Oper. Res. 149(2): 344-354 (2003) [47]
  • Philippe Baptiste, Baruch Schieber: A Note on Scheduling Tall/Small Multiprocessor Tasks with Unit Processing Time to Minimize Maximum Tardiness. J. Sched. 6(4): 395-404 (2003) [48]
  • Huy Trandac, Philippe Baptiste, Vu Duong: Airspace Sectorization By Constraint Programming. RIVF 2003: 49-58 [49]

2002

  • Philippe Baptiste: Résultats de complexité et programmation par contraintes pour l'ordonnancement. University of Technology of Compiègne, France, 2002 [50]
  • Antoine Jouglet, Philippe Baptiste, Jacques Carlier: Exact procedures for single machine total cost scheduling. SMC 2002: 4 [51]
  • Philippe Baptiste, Marek Chrobak, Christoph Dürr, Wojciech Jawor, Nodari Vakhania:Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput. CoRR cs.DS/0209033 (2002) [52]

2001

  • Philippe Baptiste, Vadim G. Timkovsky: On preemption redundancy in scheduling unit processing time jobs on two parallel machines. Oper. Res. Lett. 28(5): 205-212 (2001) [53]
  • Philippe Baptiste, Antoine Jouglet: On Minimizing Total Tardiness in a Serial Batching Problem. RAIRO Oper. Res. 35(1): 107-115 (2001) [54]
  • Philippe Baptiste, Vadim G. Timkovsky: On preemption redundancy in scheduling unit processing time jobs on two parallel machines. IPDPS 2001: 200 [55]

2000

  • Philippe Baptiste, Claude Le Pape: Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems. Constraints An Int. J. 5(1/2): 119-139 (2000) [56]
  • Philippe Baptiste: Scheduling equal-length jobs on identical parallel machines. Discret. Appl. Math. 103(1-3): 21-32 (2000) [57]
  • Philippe Baptiste: Batching identical jobs. Math. Methods Oper. Res. 52(3): 355-367 (2000) [58]

1990–1999

1999

  • Philippe Baptiste, Claude Le Pape, Wim Nuijten: Satisfiability tests and time‐bound adjustmentsfor cumulative scheduling problems. Ann. Oper. Res. 92: 305-333 (1999) [59]
  • Claude Le Pape, Philippe Baptiste: Heuristic Control of a Constraint-Based Algorithm for the Preemptive Job-Shop Scheduling Problem. J. Heuristics 5(3): 305-325 (1999) [60]
  • Philippe Baptiste: An O(n4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Oper. Res. Lett. 24(4): 175-180 (1999) [61]

1998

  • Claude Le Pape, Philippe Baptiste: Resource Constraints for Preemptive Job-shop Scheduling. Constraints An Int. J. 3(4): 263-287 (1998) [62]
  • Philippe Baptiste, Claude Le Pape, Laurent Péridy: Global Constraints for Partial CSPs: A Case-Study of Resource and Due Date Constraints. CP 1998: 87-101 [63]

1997

  • Philippe Baptiste, Claude Le Pape: Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems. CP 1997: 375-389 [64]

1996

  • Claude Le Pape, Philippe Baptiste:Constraint Propagation Techniques for Disjunctive Scheduling: The Preemptive Case. ECAI 1996: 619-623

1995

  • Philippe Baptiste, Claude Le Pape: A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive Scheduling. IJCAI (1) 1995: 600-606 [5]

Related Research Articles

Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.

<span class="mw-page-title-main">Shortest path problem</span> Computational problem of graph theory

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, splitting a network prefix into multiple subnets, and technology mapping in FPGA semiconductor chip design.

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value which is at least times the correct value, and at most times the correct value.

<span class="mw-page-title-main">Guillotine cutting</span> Process of producing small rectangular items of fixed dimensions

Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine-cuts. A guillotine-cut is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine.

Uniform machine scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m different machines. The goal is to minimize the makespan - the total time required to execute the schedule. The time that machine i needs in order to process job j is denoted by pi,j. In the general case, the times pi,j are unrelated, and any matrix of positive processing times is possible. In the specific variant called uniform machine scheduling, some machines are uniformly faster than others. This means that, for each machine i, there is a speed factor si, and the run-time of job j on machine i is pi,j = pj / si.

Single-machine scheduling or single-resource scheduling is an optimization problem in computer science and operations research. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on a single machine, in a way that optimizes a certain objective, such as the throughput.

Optimal job scheduling is a class of optimization problems related to scheduling. The inputs to such problems are a list of jobs and a list of machines. The required output is a schedule – an assignment of jobs to machines. The schedule should optimize a certain objective function. In the literature, problems of optimal job scheduling are often called machine scheduling, processor scheduling, multiprocessor scheduling, or just scheduling.

Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J1J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan – the total length of the schedule. In the specific variant known as job-shop scheduling, each job consists of a set of operationsO1O2, ..., On which need to be processed in a specific order. Each operation has a specific machine that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the flexible job shop, where each operation can be processed on any machine of a given set.

The Coffman–Graham algorithm is an algorithm for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W. When W = 2, it uses the minimum possible number of distinct levels, and in general it uses at most 2 − 2/W times as many levels as necessary.

Parallel task scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J1J2, ..., Jn of varying processing times, which need to be scheduled on m machines while trying to minimize the makespan - the total length of the schedule. In the specific variant known as parallel-task scheduling, all machines are identical. Each job j has a length parameter pj and a size parameter qj, and it must run for exactly pj time-steps on exactly qj machines in parallel.

Identical-machines scheduling is an optimization problem in computer science and operations research. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m identical machines, such that a certain objective function is optimized, for example, the makespan is minimized.

Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized. The time that machine i needs in order to process job j is denoted by pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj, and identical-machines scheduling - in which pi,j = pi.

Longest-processing-time-first (LPT) is a greedy algorithm for job scheduling. The input to the algorithm is a set of jobs, each of which has a specific processing-time. There is also a number m specifying the number of machines that can process the jobs. The LPT algorithm works as follows:

  1. Order the jobs by descending order of their processing-time, such that the job with the longest processing time is first.
  2. Schedule each job in this sequence into a machine in which the current load is smallest.

Balanced number partitioning is a variant of multiway number partitioning in which there are constraints on the number of items allocated to each set. The input to the problem is a set of n items of different sizes, and two integers mk. The output is a partition of the items into m subsets, such that the number of items in each subset is at most k. Subject to this, it is required that the sums of sizes in the m subsets are as similar as possible.

Matroid-constrained number partitioning is a variant of the multiway number partitioning problem, in which the subsets in the partition should be independent sets of a matroid. The input to this problem is a set S of items, a positive integer m, and some m matroids over the same set S. The goal is to partition S into m subsets, such that each subset i is an independent set in matroid i. Subject to this constraint, some objective function should be minimized, for example, minimizing the largest sum item sizes in a subset. In a more general variant, each of the m matroids has a weight function, which assigns a weight to each element of the ground-set. Various objective functions have been considered. For each of the three operators max,min,sum, one can use this operator on the weights of items in each subset, and on the subsets themselves. All in all, there are 9 possible objective functions, each of which can be maximized or minimized.

The configuration linear program (configuration-LP) is a linear programming technique used for solving combinatorial optimization problems. It was introduced in the context of the cutting stock problem. Later, it has been applied to the bin packing and job scheduling problems. In the configuration-LP, there is a variable for each possible configuration - each possible multiset of items that can fit in a single bin. Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations.

Fractional job scheduling is a variant of optimal job scheduling in which it is allowed to break jobs into parts and process each part separately on the same or a different machine. Breaking jobs into parts may allow for improving the overall performance, for example, decreasing the makespan. Moreover, the computational problem of finding an optimal schedule may become easier, as some of the optimization variables become continuous. On the other hand, breaking jobs apart might be costly.

References

  1. 1 2 3 4 5 6 7 "CNES - Philippe Baptiste". CNES. 21 April 2021. Retrieved 14 January 2022.
  2. "Philippe Baptiste Appointed Senior Vice President, Scientific Development at Total". 2 August 2022. Retrieved 10 August 2022.
  3. "LE PRIX ROBERT FAURE". www.roadef.org. Retrieved 10 August 2022.
  4. "Philippe Baptiste Winner of the 2000 Cor Baayen Award". January 2001. Retrieved 10 August 2022.
  5. 1 2 3 4 "Philippe Baptiste". dblp.org. Retrieved 10 August 2022.
  6. Baptiste, Philippe; Kovalyov, Mikhail Y.; Orlovich, Yury L.; Werner, Frank; Zverovich, Igor E. (2017-01-10). "Graphs with maximal induced matchings of the same size". Discrete Applied Mathematics. Special Graph Classes and Algorithms — in Honor of Professor Andreas Brandstädt on the Occasion of His 65th Birthday. 216: 15–28. doi:10.1016/j.dam.2016.08.015. ISSN   0166-218X.
  7. Baptiste, Ph.; Carlier, J.; Kononov, A.; Queyranne, M.; Sevastyanov, S.; Sviridenko, M. (2012-11-01). "Integer preemptive scheduling on parallel machines". Operations Research Letters. 40 (6): 440–444. doi:10.1016/j.orl.2012.06.011. ISSN   0167-6377.
  8. Baptiste, Philippe; Chrobak, Marek; Dürr, Christoph (July 2012). "Polynomial-time algorithms for minimum energy scheduling". ACM Transactions on Algorithms. 8 (3): 1–29. arXiv: 0908.3505 . doi:10.1145/2229163.2229170. ISSN   1549-6325. S2CID   3092807.
  9. Baptiste, Ph.; Carlier, J.; Kononov, A.; Queyranne, M.; Sevastyanov, S.; Sviridenko, M. (2011-03-06). "Properties of optimal schedules in preemptive shop scheduling". Discrete Applied Mathematics. 159 (5): 272–280. doi: 10.1016/j.dam.2010.11.015 . ISSN   0166-218X.
  10. Nannicini, Giacomo; Baptiste, Philippe; Barbier, Gilles; Krob, Daniel; Liberti, Leo (2010-01-01). "Fast paths in large-scale dynamic road networks". Computational Optimization and Applications. 45 (1): 143–158. arXiv: 0704.1068 . doi:10.1007/s10589-008-9172-y. ISSN   1573-2894. S2CID   458311.
  11. Baptiste, Philippe (2010-03-06). "A note on scheduling identical coupled tasks in logarithmic time". Discrete Applied Mathematics. 158 (5): 583–587. doi:10.1016/j.dam.2009.10.012. ISSN   0166-218X.
  12. Baptiste, Philippe; Sadykov, Ruslan (2010-06-01). "Time-indexed formulations for scheduling chains on a single machine: An application to airborne radars". European Journal of Operational Research. 203 (2): 476–483. doi:10.1016/j.ejor.2009.07.037. ISSN   0377-2217. S2CID   6151721.
  13. Baptiste, P.; Della Croce, F.; Grosso, A.; T’kindt, V. (2010-02-01). "Sequencing a single machine with due dates and deadlines: an ILP-based approach to solve very large instances". Journal of Scheduling. 13 (1): 39–47. doi:10.1007/s10951-008-0092-6. ISSN   1099-1425. S2CID   8279878.
  14. Chrobak, Marek; Baptiste, Philippe; Dürr, Christoph (2010). Albers, Susanne; Baruah, Sanjoy K.; Möhring, Rolf H.; Pruhs, Kirk (eds.). "Polynomial Time Algorithms for Minimum Energy Scheduling". Scheduling. Dagstuhl Seminar Proceedings (DagSemProc). 10071. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 1–12. doi: 10.4230/DagSemProc.10071.8 .
  15. Meng-Gérard, J.; Chrétienne, P.; Baptiste, P.; Sourd, F. (2009-10-28). "On maximizing the profit of a satellite launcher: Selecting and scheduling tasks with time windows and setups". Discrete Applied Mathematics. Sixth International Conference on Graphs and Optimization 2007. 157 (17): 3656–3664. doi: 10.1016/j.dam.2009.02.018 . ISSN   0166-218X.
  16. Baptiste, Philippe; Kendall, Graham; Munier, Alix; Sourd, Francis (2009-10-16). "Preface". Journal of Scheduling. 12 (6): 563. doi:10.1007/s10951-009-0136-6. ISSN   1099-1425. S2CID   214746603.
  17. Baptiste, Philippe (2009), Gent, Ian P. (ed.), "Constraint-Based Schedulers, do They Really Work?", Principles and Practice of Constraint Programming – CP 2009, Lecture Notes in Computer Science, vol. 5732, Berlin, Heidelberg: Springer Berlin Heidelberg, p. 1, doi: 10.1007/978-3-642-04244-7_1 , ISBN   978-3-642-04243-0, S2CID   34432804
  18. Baptiste, Philippe; Carlier, Jacques; Kononov, Alexander; Queyranne, Maurice; Sevastyanov, Sergey; Sviridenko, Maxim (2009). "Integrality Property in Preemptive Parallel Machine Scheduling". In Frid, Anna; Morozov, Andrey; Rybalchenko, Andrey; Wagner, Klaus W. (eds.). Computer Science - Theory and Applications. Lecture Notes in Computer Science. Vol. 5675. Berlin, Heidelberg: Springer. pp. 38–46. doi:10.1007/978-3-642-03351-3_6. ISBN   978-3-642-03351-3.
  19. Baptiste, Philippe; Chrobak, Marek; Durr, Christoph (2010-09-03). "Polynomial Time Algorithms for Minimum Energy Scheduling". arXiv: 0908.3505 [cs.DS].
  20. Baptiste, Philippe; Flamini, Marta; Sourd, Francis (2008-03-01). "Lagrangian bounds for just-in-time job-shop scheduling". Computers & Operations Research. Part Special Issue: New Trends in Locational Analysis. 35 (3): 906–915. doi:10.1016/j.cor.2006.05.009. ISSN   0305-0548.
  21. Jouglet, Antoine; Savourey, David; Carlier, Jacques; Baptiste, Philippe (2008-02-01). "Dominance-based heuristics for one-machine total cost scheduling problems". European Journal of Operational Research. 184 (3): 879–899. doi:10.1016/j.ejor.2006.11.036. ISSN   0377-2217. S2CID   33657053.
  22. Artiouchine, Konstantin; Baptiste, Philippe; Dürr, Christoph (2008-09-16). "Runway sequencing with holding patterns". European Journal of Operational Research. 189 (3): 1254–1266. doi:10.1016/j.ejor.2006.06.076. ISSN   0377-2217.
  23. Artiouchine, Konstantin; Baptiste, Philippe; Mattioli, Juliette (2008-05-01). "The K King Problem, an Abstract Model for Computing Aircraft Landing Trajectories: On Modeling a Dynamic Hybrid System with Constraints". INFORMS Journal on Computing. 20 (2): 222–233. doi:10.1287/ijoc.1070.0234. ISSN   1091-9856.
  24. Nannicini, Giacomo; Baptiste, Philippe; Krob, Daniel; Liberti, Leo (2008). "Fast Computation of Point-to-Point Paths on Time-Dependent Road Networks". In Yang, Boting; Du, Ding-Zhu; Wang, Cao An (eds.). Combinatorial Optimization and Applications. Lecture Notes in Computer Science. Vol. 5165. Berlin, Heidelberg: Springer. pp. 225–234. doi:10.1007/978-3-540-85097-7_21. ISBN   978-3-540-85097-7.
  25. Artiouchine, Konstantin; Baptiste, Philippe (2007-03-01). "Arc-B-consistency of the Inter-distance Constraint". Constraints. 12 (1): 3–19. doi:10.1007/s10601-006-9009-1. ISSN   1572-9354. S2CID   2764020.
  26. Baptiste, Philippe (2007-01-01). "Book review". Operations Research Letters. 35 (1): 139–140. doi:10.1016/j.orl.2006.01.001. ISSN   0167-6377.
  27. Baptiste, Philippe; Brucker, Peter; Chrobak, Marek; Dürr, Christoph; Kravchenko, Svetlana A.; Sourd, Francis (2007-04-01). "The complexity of mean flow time scheduling problems with release times". Journal of Scheduling. 10 (2): 139–146. doi:10.1007/s10951-006-0006-4. ISSN   1099-1425. S2CID   15059745.
  28. 1 2 Nannicini, Giacomo; Baptiste, Philippe; Barbier, Gilles; Krob, Daniel; Liberti, Leo (2007-06-27). "Fast paths in large-scale dynamic road networks". arXiv: 0704.1068 [cs.NI].
  29. Baptiste, Philippe; Chrobak, Marek; Dürr, Christoph (2007). "Polynomial Time Algorithms for Minimum Energy Scheduling". In Arge, Lars; Hoffmann, Michael; Welzl, Emo (eds.). Algorithms – ESA 2007. Lecture Notes in Computer Science. Vol. 4698. Berlin, Heidelberg: Springer. pp. 136–150. doi:10.1007/978-3-540-75520-3_14. ISBN   978-3-540-75520-3.
  30. Savourey, D.; Baptiste, P.; Jouglet, A. (February 2006). "Lower bounds for parallel machines scheduling". 2006 International Conference onResearch, Innovation and Vision for the Future. pp. 195–198. doi:10.1109/RIVF.2006.1696437. ISBN   1-4244-0316-2. S2CID   37865848.
  31. Baptiste, Philippe (2006-01-22). "Scheduling unit tasks to minimize the number of idle periods". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. USA: Society for Industrial and Applied Mathematics. pp. 364–367. doi:10.1145/1109557.1109598. ISBN   978-0-89871-605-4.
  32. Baptiste, Philippe; Laborie, Philippe; Pape, Claude Le; Nuijten, Wim (2006-01-01), Rossi, Francesca; van Beek, Peter; Walsh, Toby (eds.), "Chapter 22 - Constraint-Based Scheduling and Planning", Foundations of Artificial Intelligence, Handbook of Constraint Programming, vol. 2, Elsevier, pp. 761–799, doi:10.1016/S1574-6526(06)80026-X, ISBN   9780444527264 , retrieved 2022-08-10
  33. Baptiste, Philippe; Brucker, Peter; Chrobak, Marek; Durr, Christoph; Kravchenko, Svetlana A.; Sourd, Francis (2006-05-17). "The Complexity of Mean Flow Time Scheduling Problems with Release Times". arXiv: cs/0605078 .
  34. Baptiste, Philippe; Le Pape, Claude (2005-03-30). "Scheduling a single machine to minimize a regular objective function under setup constraints". Discrete Optimization. 2 (1): 83–99. doi:10.1016/j.disopt.2004.12.003. ISSN   1572-5286.
  35. Trandac, Huy; Baptiste, Philippe; Duong, Vu (2005-04-01). "Airspace sectorization with constraints". RAIRO - Operations Research. 39 (2): 105–122. doi:10.1051/ro:2005005. ISSN   0399-0559.
  36. Artiouchine, Konstantin; Baptiste, Philippe (2005). "Inter-distance Constraint: An Extension of the All-Different Constraint for Scheduling Equal Length Jobs". In van Beek, Peter (ed.). Principles and Practice of Constraint Programming - CP 2005. Lecture Notes in Computer Science. Vol. 3709. Berlin, Heidelberg: Springer. pp. 62–76. doi:10.1007/11564751_8. ISBN   978-3-540-32050-0.
  37. Baptiste, Philippe; Brucker, Peter; Knust, Sigrid; Timkovsky, Vadim G. (2004-07-01). "Ten notes on equal-processing-time scheduling". Quarterly Journal of the Belgian, French and Italian Operations Research Societies. 2 (2): 111–127. doi:10.1007/s10288-003-0024-4. ISSN   1619-4500. S2CID   45995160.
  38. Baptiste, Philippe; Carlier, Jacques; Munier, Alix; Schulz, Andreas (July 2004). "Introduction". Annals of Operations Research. 129 (1–4): 17–19. doi:10.1023/B:ANOR.0000030779.01529.d2. ISSN   0254-5330. S2CID   221114747.
  39. Baptiste, Philippe; Carlier, Jacques; Jouglet, Antoine (2004-11-01). "A Branch-and-Bound procedure to minimize total tardiness on one machine with arbitrary release dates". European Journal of Operational Research. 158 (3): 595–608. doi:10.1016/S0377-2217(03)00378-3. ISSN   0377-2217. S2CID   7474157.
  40. Baptiste, Philippe; Timkovsky, Vadim G. (2004-09-01). "Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time". Mathematical Methods of Operations Research. 60 (1): 145–153. doi:10.1007/s001860300336. ISSN   1432-5217. S2CID   21247299.
  41. Baptiste, Philippe; Chrobak, Marek; Dürr, Christoph; Jawor, Wojciech; Vakhania, Nodari (2004-05-01). "Preemptive scheduling of equal-length jobs to maximize weighted throughput". Operations Research Letters. 32 (3): 258–264. arXiv: cs/0209033 . doi:10.1016/j.orl.2003.09.004. ISSN   0167-6377. S2CID   8877838.
  42. Baptiste, Philippe; Demassey, Sophie (2004-03-01). "Tight LP bounds for resource constrained project scheduling". OR Spectrum. 26 (2): 251–262. doi:10.1007/s00291-003-0155-1. ISSN   1436-6304. S2CID   14139174.
  43. "From Sets to Geometrical Sectors in the Airspace Sectorization Problem" (PDF). Archived from the original (PDF) on 2004-07-10. Retrieved 2022-08-10.
  44. Baptiste, Philippe; Chrobak, Marek; Durr, Christoph; Sourd, Francis (2004-12-20). "Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time". arXiv: cs/0412094 .
  45. Baptiste, Philippe (2003-11-01). "A note on scheduling multiprocessor tasks with identical processing times". Computers & Operations Research. 30 (13): 2071–2078. doi:10.1016/S0305-0548(02)00116-8. ISSN   0305-0548.
  46. Baptiste, Philippe; Peridy, Laurent; Pinson, Eric (2003-01-01). "A branch and bound to minimize the number of late jobs on a single machine with release time constraints". European Journal of Operational Research. 144 (1): 1–11. doi:10.1016/S0377-2217(01)00353-8. ISSN   0377-2217.
  47. Baptiste, Philippe (2003-09-01). "On minimizing the weighted number of late jobs in unit execution time open-shops". European Journal of Operational Research. Sequencing and Scheduling. 149 (2): 344–354. doi:10.1016/S0377-2217(02)00759-2. ISSN   0377-2217.
  48. Baptiste, Philippe; Schieber, Baruch (2003-07-01). "A Note on Scheduling Tall/Small Multiprocessor Tasks with Unit Processing Time to Minimize Maximum Tardiness". Journal of Scheduling. 6 (4): 395–404. doi:10.1023/A:1024012811536. ISSN   1099-1425. S2CID   3152736.
  49. "e-ifi" (PDF). Retrieved 2022-08-10.[ permanent dead link ]
  50. Baptiste, Philippe (2002-07-01). Résultats de complexité et programmation par contraintes pour l'ordonnancement (thesis thesis). Université de Technologie de Compiègne.
  51. Jouglet, A.; Baptiste, P.; Carlier, J. (October 2002). "Exact procedures for single machine total cost scheduling". IEEE International Conference on Systems, Man and Cybernetics. Vol. 6. pp. 4 pp. vol.6–. doi:10.1109/ICSMC.2002.1175623. ISBN   0-7803-7437-1. S2CID   60540115.
  52. Baptiste, Philippe; Chrobak, Marek; Durr, Christoph; Jawor, Wojciech; Vakhania, Nodari (2003-03-11). "Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput". arXiv: cs/0209033 .
  53. Baptiste, Philippe; Timkovsky, Vadim G. (2001-06-01). "On preemption redundancy in scheduling unit processing time jobs on two parallel machines". Operations Research Letters. 28 (5): 205–212. doi:10.1016/S0167-6377(01)00068-2. ISSN   0167-6377. S2CID   15124866.
  54. Baptiste, Philippe; Jouglet, Antoine (2001-01-01). "On Minimizing Total Tardiness in a Serial Batching Problem". RAIRO - Operations Research. 35 (1): 107–115. doi:10.1051/ro:2001105. ISSN   0399-0559.
  55. Baptiste, P.; Timkovsky, V.G. (April 2001). "On preemption redundancy in scheduling unit processing time jobs on two parallel machines". Proceedings 15th International Parallel and Distributed Processing Symposium. IPDPS 2001. pp. 2152–2156. doi:10.1109/IPDPS.2001.925215. ISBN   0-7695-0990-8.
  56. Baptiste, Philippe; Pape, Claude Le (2000-01-01). "Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems". Constraints. 5 (1): 119–139. doi:10.1023/A:1009822502231. ISSN   1572-9354. S2CID   18722332.
  57. Baptiste, Philippe (2000-07-15). "Scheduling equal-length jobs on identical parallel machines". Discrete Applied Mathematics. 103 (1): 21–32. doi: 10.1016/S0166-218X(99)00238-3 . ISSN   0166-218X.
  58. Baptiste, Philippe (2000-12-01). "Batching identical jobs". Mathematical Methods of Operations Research. 52 (3): 355–367. doi:10.1007/s001860000088. ISSN   1432-5217. S2CID   11153349.
  59. Baptiste, Ph.; Le Pape, C.; Nuijten, W. (1999-01-01). "Satisfiability tests and time-bound adjustmentsfor cumulative scheduling problems". Annals of Operations Research. 92: 305–333. doi:10.1023/A:1018995000688. ISSN   1572-9338. S2CID   6375958.
  60. Pape, Claude Le; Baptiste, Philippe (1999-10-01). "Heuristic Control of a Constraint-Based Algorithm for the Preemptive Job-Shop Scheduling Problem". Journal of Heuristics. 5 (3): 305–325. doi:10.1023/A:1009613717770. ISSN   1572-9397. S2CID   11933524.
  61. Baptiste, Philippe (1999-05-01). "An O(n4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs". Operations Research Letters. 24 (4): 175–180. doi:10.1016/S0167-6377(98)00045-5. ISSN   0167-6377.
  62. Pape, Claude Le; Baptiste, Philippe (1998-10-01). "Resource Constraints for Preemptive Job-shop Scheduling". Constraints. 3 (4): 263–287. doi:10.1023/A:1009723704757. ISSN   1572-9354. S2CID   12808854.
  63. Baptiste, Philippe; Le Pape, Claude; Peridy, Laurent (1998). "Global Constraints for Partial CSPS: A Case-Study of Resource and Due Date Constraints". In Maher, Michael; Puget, Jean-Francois (eds.). Principles and Practice of Constraint Programming — CP98. Lecture Notes in Computer Science. Vol. 1520. Berlin, Heidelberg: Springer. pp. 87–101. doi:10.1007/3-540-49481-2_8. ISBN   978-3-540-49481-2.
  64. Baptiste, Philippe; Le Pape, Claude (1997). "Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems". In Smolka, Gert (ed.). Principles and Practice of Constraint Programming-CP97. Lecture Notes in Computer Science. Vol. 1330. Berlin, Heidelberg: Springer. pp. 375–389. doi:10.1007/BFb0017454. ISBN   978-3-540-69642-1.

See also