In this presentation, a solution approach based on the column generation technique is presented for solving a time-indexed formulation of the single machine total weighted tardiness problem. An accelerating strategy based on a decomposition of the time horizon into subperiods is used to solve the linear relaxation. This strategy, when embedded into a classical implicit enumeration scheme, allows us to solve several open problems of the OR-Library.

We present a new heuristic to solve large-scale generalized job shop scheduling problems with a weighted tardiness minimization objective. The heuristic is based on a combinatorial auction decomposition of the job shop problem where a job agent is associated with each job and solves a single job jobshop problem using a very fast polynomial time dynamic programming method. Each job agent submits a schedule to the auctioneer who then solves a winner determination problem to determine a feasible global schedule. 15 by 15 job shops are solved to optimality in well under 60 seconds. In addition, the auction method consistently solves JS problems quickly where as competing methods require time ranging from a minute to 6 hours for problems that are always solved in less a minute by the auction method for 15 by 15 instances. Results for instances up to 20 by 20 and higher will also be reported.

The Chuquicamata Copper Smelter, CODELCO-NORTE, Chile, should now follow a new environmental standard that limits its environmental sulfur emissions generated in the copper production process. This issue has imposed production constraints to not exceed pollution emissions. Therefore, the company should have an efficient and flexible tool, to maximize the daily production in function to the daily machine scheme, pollution emission limits and metallurgic constraints. This paper proposes a Flexible Job Shop approach that represents the current Cooper Smelting conditions. We present metaheuristics algorithms to find a good solution for this problem; Tabu Search and Simulated Annealing are used. Both performances are comparing. Hierarchical strategies are based on the decomposition in a routing and a job shop scheduling subproblems, both tackled by the metaheuristic algorithms mentioned. A disjunctive graph is used to represent a particular solution for the Flexible Job Shop problem. Preliminary computational results are presented.

Le problème d’ordonnancement des activités sous contraintes de ressources (communément noté RCPSP) consiste à planifier un ensemble d’activités, qui consomment des ressources disponibles en quantités limitées, entre lesquelles il existe des contraintes de précédence qui associent à chaque activité un ensemble d’activités qui doivent la précéder. L’objectif étant de minimiser la durée totale d’exécution de toutes les activités. Le problème est NP-Difficile. Comme c’est le cas de la majorité des problèmes de ce niveau de complexité, les méthodes heuristiques sont les plus efficaces pour le résoudre alors que les méthodes exactes ne sont efficaces que pour des instances de petites tailles. Les heuristiques les plus efficaces pour le problème sont, principalement, basées sur une représentation particulière des solutions (nommée représentation en liste des activités) couplée à une technique (nommée SGS) permettant le passage de la représentation à la planification des activités proprement dite. Nous avons développé une nouvelle représentation (nommée représentation en liste d’ensembles d’activités) qui s’avère très prometteuse par ses nombreuses propriétés et qui peut se révéler supérieure à la représentation en liste des activités. De plus, nous avons établit un certain nombre de résultats importants, notamment, que cette nouvelle représentation n’exclut jamais la solution optimale du problème et qu’elle permet de faire de meilleurs déplacements dans le domaine des solutions réalisables sans trop d’efforts de calcul supplémentaires. La représentation en liste d’ensembles d’activités ouvre la porte vers une multitude de possibilités de construction d’heuristiques susceptibles d’être compétitives avec les meilleures méthodes existantes. Plusieurs de nos tests, sur des instances connues dans la littérature, le démontrent. Mots-clefs : Problème d’ordonnancement sous contraintes de ressources, RCPS, SGS, représentation en liste des activités, représentation en liste d’ensembles d’activités.