Industrial Engineering

Permanent URI for this collectionhttps://hdl.handle.net/10679/45

Browse

Now showing 1 - 20 of 27

Unknown
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.
Unknown
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.
Metadata 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.
Metadata only
Bounding strategies for the hybrid flow shop scheduling problem
(Elsevier, 2011-07-01) Hidri, L.; Haouari, Mohamed; Industrial Engineering; HAOUARI, Mohamed
In this paper, we investigate new lower and upper bounds for the multiple-center hybrid flow shop scheduling problem. We propose a family of center-based lower bounds as well as a destructive lower bound that is based on the concept of revised energetic reasoning. Also, we describe an optimization-based heuristic that requires iteratively solving a sequence of parallel machine problems with heads and tails. We present the results of extensive computational experiments that provide evidence that the proposed bounding procedures consistently improve the best existing ones.
Metadata only
A branch-and-cut algorithm for the Steiner tree problem with delays
(Springer Science+Business Media, 2012-12) Leggieri, V.; Haouari, Mohamed; Triki, C.; Industrial Engineering; HAOUARI, Mohamed
In this paper, we investigate the Steiner tree problem with delays, which is a generalized version of the Steiner tree problem applied to multicast routing. For this challenging combinatorial optimization problem, we present an enhanced directed cut-based MIP formulation and an exact solution method based on a branch-and-cut approach. Our computational study reveals that the proposed approach can optimally solve hard dense instances.
Metadata only
A computational study of lower bounds for the two dimensional bin packing problem
(Elsevier, 2010-08-01) Serairi, M.; Haouari, Mohamed; Industrial Engineering; HAOUARI, Mohamed
We survey lower bounds for the variant of the two-dimensional bin packing problem where items cannot be rotated. We prove that the dominance relation claimed by Carlier et al. between their lower bounds and those of Boschetti and Mingozzi is not valid. We analyze the performance of lower bounds from the literature and we provide the results of a computational experiment.
Metadata only
Development of lower bounds for the scheduling of setup tasks in serial production lines
(Inderscience Publishers, 2013) Pessan, C.; Neron, E.; Haouari, Mohamed; Industrial Engineering; HAOUARI, Mohamed
Efficient production resettings are necessary to achieve production flexibility. For this reason, it is of primary importance to reduce the setup time required to switch the production from one product type to another, and more generally to minimise the loss of production during these resetting phases. In this paper, we investigate the problem of scheduling operations within a production resetting that arises at the ball bearing factories of the SKF group. In the case of full serial production lines, improving the setup times amount to minimising the time spent prior to restarting production. We show that the problem of scheduling operations within a production resetting can be modelled as an unrelated parallel machine scheduling problem, and we propose several lower bounds. The first one is an extension of the improved energetic reasoning to the unrelated parallel machine problem. The second one is based on a preemptive relaxation that includes valid inequalities. We report the results of computational experiments that were carried out on both industrial and generated instances and that provide evidence of the efficacy of the proposed lower bounds.
Metadata only
Discrepancy search for the flexible job shop scheduling problem
(Elsevier, 2010-12) Hmida, A. B.; Haouari, Mohamed; Huguet, M.-J.; Lopez, P.; Industrial Engineering; HAOUARI, Mohamed
The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop problem in which each operation must be processed on a given machine chosen among a finite subset of candidate machines. The aim is to find an allocation for each operation and to define the sequence of operations on each machine, so that the resulting schedule has a minimal completion time. We propose a variant of the climbing discrepancy search approach for solving this problem. We also present various neighborhood structures related to assignment and sequencing problems. We report the results of extensive computational experiments carried out on well-known benchmarks for flexible job shop scheduling. The results demonstrate that the proposed approach outperforms the best-known algorithms for the FJSP on some types of benchmarks and remains comparable with them on other ones.
Metadata only
Discrete time/cost trade-off problem: a decomposition-based solutionalgorithm for the budget version
(Elsevier, 2010-04) Hazır, Ö.; Haouari, Mohamed; Erel, E.; Industrial Engineering; HAOUARI, Mohamed
This paper investigates the budget variant of the discrete time/cost trade-off problem (DTCTP). This multi-mode project scheduling problem requires assigning modes to the activities of a project so that the total completion time is minimized and the budget and the precedence constraints are satisfied. This problem is often encountered in practice as timely completion of the projects without exceeding the budget is crucial. The contribution of this paper to the literatures is to describe an effective Benders Decomposition-based exact algorithm to solve the DTCTP instances of realistic sizes. Although Benders Decomposition often exhibits a very slow convergence, we have included several algorithmic features to enhance the performance of the proposed tailored approach. Computational results attest to the efficacy of the proposed algorithm, which can solve large-scale instances to optimality.
Metadata only
Energetic reasoning revisited: application to parallel machine scheduling
(Springer Science+Business Media, 2008-08) Hidri, L.; Gharbi, A.; Haouari, Mohamed; Industrial Engineering; HAOUARI, Mohamed
We consider the problem of minimizing makespan on identical parallel machines subject to release dates and delivery times. We present several new feasibility tests and adjustment techniques that consistently improve theclassical energetic reasoning approach. Computational results carried out on a set of hard instances provide strong evidence that the performance of a state-of-the-art exact branch-and-bound algorithm is substantially improved through embedding the proposed enhanced energetic reasoning.
Metadata only
Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem
(Elsevier, 2012-05) Haouari, Mohamed; Kooli, A.; Neron, E.; Industrial Engineering; HAOUARI, Mohamed
We present new and effective lower bounds for the resource constrained project scheduling problem. This problem is widely known to be notoriously difficult to solve due to the lack of lower bounds that are both tight and fast. In this paper, we propose several new lower bounds that are based on the concept of energetic reasoning. A major contribution of this work is to investigate several enhanced new feasibility tests that prove useful for deriving new lower bounds that consistently outperform the classical energetic reasoning-based lower bound. In particular, we present the results of a comprehensive computational study, carried out on 1560 benchmark instances, that provides strong evidence that a deceptively simple dual feasible function-based lower bound is highly competitive with a state-of-the-art lower bound while being extremely fast. Furthermore, we found that an effective shaving procedure enables to derive an excellent lower bound that often outperforms the best bound from the literature while being significantly simpler.
Metadata 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.
Metadata only
Exact approaches for integrated aircraft fleeting and routing at TunisAir
(Science+Business Media, 2011-06) Haouari, Mohamed; Sherali, H. D.; Mansour, F. Z.; Aissaoui, N.; Industrial Engineering; HAOUARI, Mohamed
We describe models and exact solutions approaches for an integrated aircraft fleeting and routing problem arising at TunisAir. Given a schedule of flights to be flown, the problem consists of determining a minimum cost route assignment for each aircraft so as to cover each flight by exactly one aircraft while satisfying maintenanceactivity constraints. We investigate two tailored approaches for this problem: Benders decomposition and branch-and-price. Computational experiments conducted on real-data provide evidence that the branch-and-price approach outperforms the Benders decomposition approach and delivers optimal solutions within moderate CPUtimes. On the other hand, the Benders algorithm yields very quickly high quality near-optimal solutions.
Metadata 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.
Metadata 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.
Metadata only
Flexible aircraft fleeting and routing at TunisAir
(Palgrave Macmillan, 2011-02) Zeghal, F. M.; Haouari, Mohamed; Sherali, H. D.; Aissaoui, N.; Industrial Engineering; HAOUARI, Mohamed
This paper addresses a Flexible Aircraft Fleeting and Routing Problem, which is motivated by the Tunisian national carrier TunisAir. A solution to this problem specifies the departure time of each flight, the subset of aircraft to be chartered or rented out, the individual aircraft assigned to each flight, as well as the sequence of flights to be flown by each aircraft. The objective is to maximize the expected total net profit, while satisfying activity constraints and long-term maintenance requirements. Tailored optimization-based heuristics are developed for solving this complex integrated problem. Computational experiments conducted on real data demonstrate that the proposed procedures are effective and robust, and significantly improve upon TunisAir's solutions.
Metadata only
Heuristics for the variable sized bin-packing problem
(Elsevier, 2009-10) Haouari, Mohamed; Serairi, M.; Industrial Engineering; HAOUARI, Mohamed
We investigate the one-dimensional variable-sized bin-packing problem. This problem requires packing a set of items into a minimum-cost set of bins of unequal sizes and costs. Six optimization-based heuristics for this problem are presented and compared. We analyze their empirical performance on a large set of randomly generated test instances with up to 2000 items and seven bin types. The first contribution of this paper is to provide evidence that a set covering heuristic proves to be highly effective and capable of delivering very-high quality solutions within short CPU times. In addition, we found that a simple subset-sum problem-based heuristic consistently outperforms heuristics from the literature while requir- ing extremely short CPU times.
Metadata only
Integrated airline schedule design and fleet assignment: polyhedral analysis and benders’ decomposition approach
(Informs, 2010-01) Sherali, H. D.; Bae, K.-H.; Haouari, Mohamed; Industrial Engineering; HAOUARI, Mohamed
The main airline operations consist of schedule planning, fleet assignment, aircraft routing, and crew scheduling. To improve profitability, we present in this paper an integrated fleet assignment model with schedule planning by simultaneously considering optional flight legs to select along with the assignment of aircraft types to all scheduled legs. In addition, we consider itinerary-based demands for multiple fare classes. A polyhedral analysis is conducted of the proposed mixed-integer programming model to tighten its representation via several classes of valid inequalities. Solution approaches are developed by applying Benders' decomposition method to the resulting lifted model, and computational results are presented using real data obtained from a major U.S. airline to demonstrate the efficacy of the proposed procedures.
Metadata only
IP-based energetic reasoning for the resource constrained project scheduling problem
(Elsevier, 2010-08-01) Kooli, A.; Haouari, Mohamed; Hidri, L.; Neron, E.; Industrial Engineering; HAOUARI, Mohamed
In this paper, we consider the Resource Constrained Project Scheduling Problem (RCPSP). New feasibility tests for the energetic reasoning are introduced based on new integer programming (IP) formulations. Experimental results are presented based on PSPLIB instances.
Metadata only
Relaxations and exact solution of the variable sized bin packing problem
(Springer Science+Business Media, 2011-03) Haouari, Mohamed; Serairi, M.; Industrial Engineering; HAOUARI, Mohamed
We address a generalization of the classical one-dimensional bin packing problem with unequal bin sizes and costs. We investigate lower bounds for this problem as well as exact algorithms. The main contribution of this paper is to show that embedding a tight network flow-based lower bound, dominance rules, as well as an effective knapsack-based heuristic in a branch-and-bound algorithm yields very good performance. In addition, we show that the particular case with all weight items larger than a third the largest bin capacity can be restated and solved in polynomial-time as a maximum-weight matching problem in a nonbipartite graph. We report the results of extensive computational experiments that provide evidence that large randomly generated instances are optimally solved within moderate CPU times.

Browse

Browsing by Institution Author "HAOUARI, Mohamed"