10:30 AM - 10:55 AM
Maintenance Scheduling of Multi-Component Systems with a Set-Up Cost
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
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
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
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.