Scheduling with earliness–tardiness penalties and parallel machines

This is a summary of the author’s PhD thesis supervised by Francis Sourd and Philippe Chrétienne and defended on 30 January 2007 at the Université Pierre et Marie Curie, Paris. The thesis is written in French and is available from the author upon request. This work is about scheduling on parallel machines in order to minimize the total sum of earliness and tardiness costs. To solve some variants of this problem we propose: an exact method based on continuous relaxations of convex reformulations derived from a 0–1 quadratic program; a heuristic algorithm that relies on a new exponential size neighborhood search; finally, a lower bound method based on a polynomial time solution of a preemptive scheduling problem for which the cost functions of the jobs have been changed into so called position costs functions. Partial funding provided by CONACyT (Mexican Council for Science&Technology).     

A method for determining cost-efficient inspection strategies in multistage production systems

This is a summary of the author’s PhD thesis. The thesis, written in English, was defended on 6 March 2006, and was supervised by Rik Van Landeghem and Claude Van Mechelen. A copy is available from the author upon request. This PhD thesis focuses on (cost-)efficient quality control for multistage production processes, a major issue to manufacturers. Subjecting a larger product fraction to inspection, or tightening the acceptance limits, will normally lead to a higher product quality, but will also result in higher costs of inspection, scrap and rework. Quantifying this trade-off and thus establishing ways of finding an economic optimum is at the heart of this research. Thereto, a metaheuristic solution approach, consisting of an evolutionary algorithm combined with simulation, is presented and validated.      

Models and methods for capacitated lot-sizing problems

This is a summary of the author’s PhD thesis supervised by Philippe Chrétienne and Safia Kedad-Sidhoum and defended in December 2005 at the Université Pierre et Marie Curie (Paris VI). The thesis is written in French and is available from . This work mainly deals with multi-item capacitated lot-sizing problems with setup times, shortages on demand and safety stock deficit costs. We propose a new mathematical model that includes these new constraints. Three solution approaches are considered: branch-and-cut, Lagrangean relaxation and MIP-based heuristics approaches. Experimental results showing the effectiveness and the limit of each approach are presented. This work was financed by the ANRT and DynaSys S.A.     

Agent scheduling in a multiskill call center

This is a summary of the author’s PhD thesis, supervised by Pierre L’Ecuyer and Roberto Musmanno and defended on 21 February 2008 at the Università della Calabria. The thesis is written in English and is available from the author upon request. This work deals with the comparison of simulation-based algorithms for solving the agents scheduling problem in a multiskill call center minimizing their costs under service levels constraints. A solution approach, combining simulation, with integer or linear programming, and cut generation, is proposed. Considering realistic problems, it performs better than the two-step approach proposed in the literature. It is also shown that a randomized search, extending the one defined for the single-period staffing problem in Avramidis et al. [IIE Trans (in press), 2008], yields highly suboptimal solutions. Finally, an extension of the cutting plane method to directly control the probability on the customers abandonments is designed.      

Optimal Paths And Costs Of Adjustment In Dynamic DEA Models: With Application To Chilean Department Stores

In this paper we propose a range of dynamic data envelopment analysis (DEA) models which allow information on costs of adjustment to be incorporated into the DEA framework. We first specify a basic dynamic DEA model predicated on a number of simplifying assumptions. We then outline a number of extensions to this model to accommodate asymmetric adjustment costs, non-static output quantities, non-static input prices, and non-static costs of adjustment, technological change, quasi-fixed inputs and investment budget constraints. The new dynamic DEA models provide valuable extra information relative to the standard static DEA models—they identify an optimal path of adjustment for the input quantities, and provide a measure of the potential cost savings that result from recognising the costs of adjusting input quantities towards the optimal point. The new models are illustrated using data relating to a chain of 35 retail department stores in Chile. The empirical results illustrate the wealth of information that can be derived from these models, and clearly show that static models overstate potential cost savings when adjustment costs are non-zero. This paper arises out the senior author's PhD thesis at the University of New England, Australia. The authors gratefully acknowledge Dr. George E. Battese for his comments on earlier drafts of this work.     

Heuristic Algorithms for Solving a Large Scale Multicommodity Flow Problem on a Network with a Step Function Cost

This thesis presents a multicommodity flow problem on a telephone network, consisting in allocating telephone lines from one switching center to another to physical routes represented by edges. The criterion is the minimum of the total investment cost, in which the cost of each edge is a step function. Representing each group of lines between two vertices as a flow gives a very large model; decomposing these flows along paths permits the use of generalized programming; defining the total cost from the lines themselves exhibits a solution method by approximation. Three heuristic methods are presented. Solving by successive approximations to the actual costs of the lines gives a good solution. Rerouting lines from one path to another presents several pathologies which can be corrected, and shows the possibility of improving the solution yielded by the approximation method.     

Approximation and resolution of min–max and min–max regret versions of combinatorial optimization problems

This is a summary of the most important results presented in the author’s PhD thesis. This thesis, written in French, was defended on November 2005 and supervised by Cristina Bazgan and Daniel Vanderpooten. A copy is available from the author upon request. This thesis deals with the complexity, approximation and resolution of the min–max and min–max versions of classical combinatorial optimization problems. In addition to these theoretical aspects, a practical application of robustness approaches to the problem of data association is considered.     

On a new class of nonlinear set covering problems arising in wireless network design

This is a summary of the author’s PhD thesis, supervised by Edoardo Amaldi and defended on 28 April 2006 at Politecnico di Milano, Dipartimento di Matematica. The thesis is written in English and is available from the author upon request. The thesis investigates a class of nonlinear set covering variants arising from the problem of designing single-frequency Wireless Local Area Networks (WLANs) with maximum efficiency. In the first part of the thesis a basic hyperbolic formulation of the problem is considered. After a complexity and approximability study, the problem is tackled by linearization techniques, and by Lagrangean and Dantzig–Wolfe decompositions. The second part of the thesis focuses on variants accounting for various relevant features of the WLAN application. A Branch-and-Price algorithm is presented, and extensions to the multiple-frequency WLAN design problem are considered.      

Nonsmooth optimization: theory and algorithms

This is a summary of the author’s PhD thesis supervised by Manlio Gaudioso and Maria Flavia Monaco and defended on 21 February 2008 at the Università della Calabria. The thesis is a survey on nonsmooth optimization methods for both convex and nonconvex functions. The main contribution of the dissertation is the presentation of a new bundle type method. The thesis is written in English and is available from .     

Algorithms for some graph theoretical optimization problems

This is a summary of the main results presented in the author’s PhD thesis. This thesis, written in English, was supervised by Frits Spieksma and defended on September 23, 2005 at the Katholieke Universiteit Leuven. A copy of the thesis is available from the authors website (http://www.econ. kuleuven.be/linda.moonen/public/). The thesis can be roughly split into two parts. The first part is dedicated to the problem of partitioning partially ordered sets into chains of limited size. The second part deals with the structure and the connectivity of the Internet.     

On the optimal control for variational inequalities

We prove an existence theorem for the optimal control of variational inequalities governed by a pseudomonotone operator: the cost is assumed to be quadratic. Then, we give an extension of the theorem to more general costs (assuming the operator to be monotone); we also give a result on a perturbation problem.This work is an extended part of the author's thesis, written under the direction of Professor T. Zolezzi. This research was partially supported by the Consiglio Nazionale delle Ricerche (CNR), Rome, Italy.     

Multicast problems in telecommunication networks

This is a summary of the author’s PhD thesis supervised by Paolo Nobili and defended on 20 April 2007 at the Università del Salento (Lecce). The thesis is written in English and is available from the author upon request. This work deals with multicast problems in wireless Ad-Hoc networks and some related variants.      

Models and algorithms for the reconfiguration of distributed wireless switching systems

This paper is a summary of the author’s PhD thesis entitled “Models and algorithms for the reconfiguration of wireless switching systems”. The thesis deals with the study of a strongly NP-hard resource-constrained scheduling problem arising from the telecommunication industry. This work was supervised by Jacques Carlier and Dritan Nace, both from Université de Technologie de Compiègne, and carried out while the author was a System Architect within Nortel GSM Access R&D organization. The thesis, which is written in both French and English, has been defended on 29 March 2007 and is available by email request to the author. This research was supported in part by Association Nationale de la Recherche Technique grant CIFRE-121/2004.     

Exact and approximate resolution of integral multiflow and multicut problems: algorithms and complexity

This is a summary of the author’s PhD thesis supervised by Marie- Christine Costa and Frédéric Roupin and defended on 20 November 2006 at the Conservatoire National des Arts et Métiers in Paris (France). The thesis is written in French and is available upon request from the author. This work deals with two well-known optimization problems from graph theory: the maximum integral multiflow and the minimum multicut problems. The main contributions of this thesis concern the polynomial-time solvability and the approximation of these two problems (and of some of their variants) in classical classes of graphs: bounded tree-width graphs, planar graphs and grids, digraphs, etc.      

On the design of networks with unicyclic connected components

This is a summary of my PhD thesis supervised by Walid Ben-Ameur and defended on September 29 2009, at Télécom SudParis. The thesis is written in French language and is available from the author upon request at makhlouf.hadji@it-sudparis.eu.     

Enhanced mixed integer programming techniques and routing problems

This is a summary of the author’s PhD thesis supervised by Andrea Lodi and Paolo Toth and defended on 16 April 2009 at the Università di Bologna. The thesis is written in English and is available from the author upon request. This work is focused on Mixed Integer Programming (MIP). In particular, the first part of the thesis deals with general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. The second part is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications.     

Polynomial approximation: a structural and operational study

This is a summary of the most important results of the author’s PhD thesis. This thesis, supervised by Vangelis Th. Paschos, was defended in October 2005 at the Université Paris Dauphine. It is written in French and is available on-line. The thesis is focused on combinatorial optimization problems, studied from the standpoint of polynomial approximation theory. We were interested both in structural concerns (mainly completeness in approximation classes and logical expressivity) and operational ones (with the study of satisfiability, coloring and covering problems). http://www.lamsade.dauphine.fr/~escoffier/fichiers/TheseEscoffier.pdf     

A new stochastic Petri net model and its applications to logistics systems

This is a summary of the author’s PhD thesis supervised by Lionel Amodeo and Hoaxun Chen and defended on 29 November 2005 at the Université de Technologie de Troyes (France). The thesis is written in French and is available from the author upon request. This work deals with a new stochastic Petri net model and its applications for modeling and studying logistics systems and more generally discrete event dynamic systems.      

Impact of replenishment rules with endogenous lead times on supply chain performance

This text summarizes the PhD thesis of Robert Boute, obtained at the Katholieke Universiteit Leuven (Belgium) under supervision of Marc Lambrecht. This doctoral dissertation in the field of Supply Chain Management demonstrates that significant cost reductions can be obtained for both the retailer and the manufacturer when they align their replenishment policy. Such a collaboration strategy goes far beyond “information sharing”. In this summary, we present the research model, the general outline of the thesis and the methodology used. The PhD thesis, written in English, is available from the author upon request.      

Multiple criteria decision aiding: a dialectical perspective

This is a summary of the Ouerdane’s PhD thesis supervised by Alexis Tsoukiàs and Nicolas Maudet and defended on 01 December 2009 at the Université Paris-Dauphine, Paris. The thesis is written in English and is available from the author upon request. This work has the aim to investigate the different ways to use argumentation theory in a decision context. More precisely within multi-criteria evaluation models. The principal aim is to meet the needs in terms of explanations and revision during a decision process.