4 Presentations

• 
  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.

• 
  10:55 AM - 11:20 AM

  Batch Scheduling in an Aluminum Company

  • Aïda Reguigui, presenter, GERAD - Polytechnique Montréal
  • Francois Soumis, GERAD et Polytechnique

  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.

• 
  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.

• 
  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.