Including an Industrial Optimization Day

HEC Montréal, May 7 - 9, 2012


HEC Montréal, May 7 — 9, 2012

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

MB4 Ordonnancement / Scheduling

May 7, 2012 10:30 AM – 12:10 PM

Location: Quebecor

Chaired by Sheldon Jacobson

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:30 AM - 10:55 AM

    Maintenance Scheduling of Multi-Component Systems with a Set-Up Cost

    • Adam Wojciechowski, presenter, Chalmers University of Technology

    I will present a MIP model for maintenance scheduling of a multi-component system where each component is assigned a maximum maintenance interval. We have shown that the problem is NP-hard and discovered a class of facets of the convex hull of feasible solutions obtained by zero-half CG rounding. We have also extended the model to maintenance scheduling with stochastic component failures.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:55 AM - 11:20 AM

    Batch Scheduling in an Aluminum Company

    • Aïda Reguigui, presenter, GERAD - Polytechnique Montréal
    • François Soumis, Polytechnique Montréal

    The problem is to assign pieces to batches and to determine the heat treatment schedules. We generated patterns and inserted them into an integer linear programming model to respect, among others, due dates of pieces and energy constraints. The model was resolved with CPLEX. Results will be presented.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:20 AM - 11:45 AM

    A Polynomial Algorithm to Solve the Mono-Item Capacitated Lot-Sizing Problem with Minimum Order Quantity

    • Bertrand Hellion, presenter, Laboratoire G-SCOP
    • Bernard Penz, Laboratoire G-SCOP
    • Fabien Mangione, Institut polytechnique de Grenoble

    In the lot-sizing problem, a demand must be satisfied at each period over a planning horizon. This demand can be satisfied from the stock or by a production. Even if the problem has been proven np-complete, special cases are polynomially solved. We consider a special case, in which a minimum order quantity constraints the production. We expose a polynomial algorithm to solve this problem.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:45 AM - 12:10 PM

    A Branch, Bound, and Remember Algorithm for the Simple Assembly Line Balancing Problem

    • Sheldon Jacobson, presenter, University of Illinois
    • Edward Sewell, Southern Illinois University Edwardsville

    A new exact algorithm is presented for the assembly line balancing problem, which finds and verifies the optimal solution for every problem in the benchmarks of Hoffmann, Talbot, and Scholl one-half second per problem, on average, including one problem that has remained open for over ten years. The previous best known algorithm solved 257 of the 269 benchmarks. The new algorithm is based on a branch & bound method using memory to eliminate redundant subproblems.