Person:
HAOUARI, Mohamed

Profile Picture

Email Address

Birth Date

WoSScopusGoogle ScholarORCID

Name

Job Title

First Name

Mohamed

Last Name

HAOUARI
OrgUnit Logo
Organizational Unit

Filters

2008 - 200942010 - 201424
Reset filters

Settings

Publication Search Results

Now showing 1 - 10 of 28
  • Placeholder
    ArticlePublicationMetadata only
    Exact methods for the robotic cell problem
    (Springer Science+Business Media, 2011-06) Kharbeche, M.; Carlier, J.; Haouari, Mohamed; Moukrim, A.; Industrial Engineering; HAOUARI, Mohamed
    This paper investigates an exact method for the Robotic Cell Problem. We present a branch-and-bound algorithm which is the first exact procedure specifically designed with regard to this complex flow shop scheduling variant. Also, we propose a new mathematical programming model as well as new lower bounds. Furthermore, we describe an effective genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that medium-sized instances, with up to 176 operations, can be optimally solved. Also, we found that the new proposed lower bounds outperform lower bounds from the literature. Finally, we show, that the genetic algorithm delivers good solutions while requiring short CPU times.
  • Placeholder
    ArticlePublicationMetadata only
    Tight compact models and comparative analysis for the prize collecting Steiner tree problem
    (Elsevier, 2013-03) Haouari, Mohamed; Layeb, S. B.; Sherali, H. D.; Industrial Engineering; HAOUARI, Mohamed
    We investigate a generalized version of the prize collecting Steiner tree problem (PCSTP), where each node of a given weighted graph is associated with a prize as well as a penalty cost. The problem is to find a tree spanning a subset of nodes that collects a total prize not less than a given quota Q, such that the sum of the weights of the edges in the tree plus the sum of the penalties of those nodes that are not covered by the tree is minimized. We formulate several compact mixed-integer programming models for the PCSTP and enhance them by appending valid inequalities, lifting constraints, or reformulating the model using the Reformulation–Linearization Technique (RLT). We also conduct a theoretical comparison of the relative strengths of the associated LP relaxations. Extensive results are presented using a large set of benchmark instances to compare the different formulations. In particular, a proposed hybrid compact formulation approach is shown to provide optimal or very near-optimal solutions for instances having up to 2500 nodes and 3125 edges.
  • Placeholder
    ArticlePublicationMetadata only
    Algorithmic expedients for the prize collecting Steiner tree problem
    (Elsevier, 2010) Haouari, Mohamed; Layeb, S. B.; Sherali, H. D.; Industrial Engineering; HAOUARI, Mohamed
    This paper investigates the Prize Collecting Steiner Tree Problem (PCSTP) on a graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, node prizes and penalties, as well as a preset quota, the PCSTP seeks to find a subtree that includes the root node and collects a total prize not smaller than the specified quota, while minimizing the sum of the total edge costs of the tree plus the penalties associated with the nodes that are not included in the subtree. For this challenging network design problem that arises in telecommunication settings, we present two valid 0-1 programming formulations and use them to develop preprocessing procedures for reducing the graph size. Also, we design an optimization-based heuristic that requires solving a PCSTP on a specific tree-subgraph. Although, this latter special case is shown to be NP-hard, it is effectively solvable in pseudo-polynomial time. The worst-case performance of the proposed heuristic is also investigated. In addition, we describe new valid inequalities for the PCSTP and embed all the aforementioned constructs in an exact row-generation approach. Our computational study reveals that the proposed approach can solve relatively large-scale PCSTP instances having up to 1000 nodes to optimality.
  • Placeholder
    ArticlePublicationMetadata only
    Robust scheduling and robustness measures for the discrete time/cost trade-off problem
    (Elsevier, 2010-12-01) Hazır, Ö.; Haouari, Mohamed; Erel, E.; Industrial Engineering; HAOUARI, Mohamed
    Projects are often subject to various sources of uncertainties that have a negative impact on activity durations and costs. Therefore, it is crucial to develop effective approaches to generate robust project schedules that are less vulnerable to disruptions caused by uncontrollable factors. In this paper, we investigate the robust discrete time/cost trade-off problem, which is a multi-mode project scheduling problem with important practical relevance. We introduce surrogate measures that aim at providing an accurate estimate of the schedule robustness. The pertinence of each proposed measure is assessed through computational experiments. Using the insights revealed by the computational study, we propose a two-stage robust scheduling algorithm. Finally, we provide evidence that the proposed approach can be extended to solve a complex robust problem with tardiness penalties and earliness revenues.
  • Placeholder
    ArticlePublicationMetadata only
    A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture
    (Springer Science+Business Media, 2013-11) Sherali, H. D.; Bae, K.-H.; Haouari, Mohamed; Industrial Engineering; HAOUARI, Mohamed
    The airline’s ability to offer flight schedules that provide service to passengers at desired times in competitive markets, while matching demand with an aircraft fleet of suitable size and composition, can significantly impact its profits. In this spirit, optional flight legs can be considered to construct a profitable schedule by optimally selecting among such alternatives in concert with assigning the available aircraft fleet to all the scheduled legs. Examining itinerary-based demands as well as multiple fare-classes can effectively capture network effects and realistic demand patterns. In addition, allowing flexibility on the departure times of scheduled flight legs can increase connection opportunities for passengers, hence yielding robust schedules while saving fleet assignment costs within the framework of an integrated model. Airlines can also capture an adequate market share by balancing flight schedules throughout the day, and recapture considerations can contribute to more realistic accepted demand realizations. We therefore propose in this paper a model that integrates the schedule design and fleet assignment processes while considering flexible flight times, schedule balance, and recapture issues, along with optional legs, path/itinerary-based demands, and multiple fare-classes. A polyhedral analysis is conducted to generate several classes of valid inequalities, which are used along with suitable separation routines to tighten the model representation. Solution approaches are designed by applying Benders decomposition method to the resulting tightened model, and computational results are presented using real data obtained from United Airlines to demonstrate the efficacy of the proposed procedures.
  • Placeholder
    Conference ObjectPublicationMetadata only
    An exact algorithm for the Steiner tree problem with delays
    (Elsevier, 2010-08-01) Leggieri, V.; Haouari, Mohamed; Triki, C.; Industrial Engineering; HAOUARI, Mohamed
    The Steiner Tree Problem with Delays (STPD) is a variant of the well-known Steiner Tree Problem in which the delay on each path between a source node and a terminal node is limited by a given maximum value. We propose a Branch-and-Cut algorithm for solving this problem using a formulation based on lifted Miller-Tucker-Zemlin subtour elimination constraints. The effectiveness of the proposed algorithm is assessed through computational experiments carried out on dense benchmark instances.
  • Placeholder
    Conference ObjectPublicationMetadata only
    Exact method for robotic cell problem
    (Elsevier, 2010-08-01) Kharbeche, M.; Carlier, J.; Haouari, Mohamed; Moukrim, A.; Industrial Engineering; HAOUARI, Mohamed
    This study investigates an exact method for the Robotic Cell Problem. We present an exact branch and bound algorithm which is the first exact procedure specifically designed for this strongly NP-hard problem. In this paper, we propose a new mathematical formulation and we describe a new lower bound for the RCP. In addition, we propose a genetic algorithm. We report that the branch and bound algorithm is more effective than the proposed mathematical formulation which can solve small sized problem. Also, computational study provides evidence that the genetic algorithm delivers reasonably good solutions while requiring significantly shorter CPU times to solve this problem.
  • Placeholder
    ArticlePublicationMetadata only
    Approximation algorithms for single machine scheduling with one unavailability period
    (Springer Nature, 2009-03) Kacem, I.; Haouari, Mohamed; Industrial Engineering; HAOUARI, Mohamed
    In this paper, we investigate the single machine scheduling problem with release dates and tails and a planned unavailability time period. We show that the problem admits a fully polynomial-time approximation scheme when the tails are equal. We derive an approximation algorithm for the general case and we show that the worst-case bound of the sequence yielded by Schrage’s algorithm is equal to 2 and that this bound is tight. Some consequences of this result are also presented.
  • Placeholder
    ArticlePublicationMetadata only
    The Steiner tree problem with delays: a compact formulation and reduction procedures
    (Elsevier, 2014-02-19) Leggieri, V.; Haouari, Mohamed; Triki, C.; Industrial Engineering; HAOUARI, Mohamed
    This paper investigates the Steiner Tree Problem with Delays (STPD), a variation of the classical Steiner Tree problem that arises in multicast routing. We propose an exact solution approach that is based on a polynomial-size formulation for this challenging NP-hard problem. The LP relaxation of this formulation is enhanced through the derivation of new lifted Miller Tucker Zemlin subtour elimination constraints. Furthermore, we present several preprocessing techniques for both reducing the problem size and tightening the LP relaxation. Finally, we report the results of extensive computational experiments on instances with up to 1000 nodes. These results attest to the efficacy of the combination of the enhanced formulation and reduction techniques.
  • Placeholder
    ArticlePublicationMetadata only
    Solving two-stage hybrid flow shop using climbing depth-bounded discrepancy search
    (Elsevier, 2011-03) Hmida, A. B.; Haouari, Mohamed; Huguet, M.-J.; Lopez, P.; Industrial Engineering; HAOUARI, Mohamed
    This paper investigates how to adapt a discrepancy-based search method to solve two-stage hybrid flowshop scheduling problems in which each stage consists of several identical machines operating in parallel. The objective is to determine a schedule that minimizes the makespan. We present an adaptation of the Climbing Depth-bounded Discrepancy Search (CDDS) method based on Johnson’s rule and on dedicated lower bounds for the two-stage hybrid flow shop problem. We report the results of extensive computational experiments, which show that the proposed adaptation of the CDDS method solves instances in restrained CPU time and with high quality of makespan.