Incluant une Journée industrielle de l'optimisation
HEC Montréal, 7  9 mai 2012
JOPT2012
HEC Montréal, 7 — 9 mai 2012
MB4 Ordonnancement / Scheduling
7 mai 2012 10h30 – 12h10
Salle: Quebecor
Présidée par Sheldon Jacobson
4 présentations

10h30  10h55
Maintenance Scheduling of MultiComponent Systems with a SetUp Cost
I will present a MIP model for maintenance scheduling of a multicomponent system where each component is assigned a maximum maintenance interval. We have shown that the problem is NPhard and discovered a class of facets of the convex hull of feasible solutions obtained by zerohalf CG rounding. We have also extended the model to maintenance scheduling with stochastic component failures.

10h55  11h20
Batch Scheduling in an Aluminum Company
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.

11h20  11h45
A Polynomial Algorithm to Solve the MonoItem Capacitated LotSizing Problem with Minimum Order Quantity
In the lotsizing 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 npcomplete, 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.

11h45  12h10
A Branch, Bound, and Remember Algorithm for the Simple Assembly Line Balancing Problem
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 onehalf 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.