Machine scheduling by column-and-row generation on the time-indexed formulation

Ruslan Sadykov 1, 2 François Vanderbeck 1, 2
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : We consider the general machine scheduling problem to minimize the scheduling cost. One of the most efficient approaches to solve this problem is to use time-indexed Integer Programming formulation. However, the size of this formulation is very big, and even solving its Linear Programming (LP) relaxation is very time consuming. In this work, we apply the column-and-row generation approach to solve the LP relaxation of the time-indexed formulation in significantly less amount of time.
Type de document :
Communication dans un congrès
10th International Workshop on Models and Algorithms for Planning and Scheduling Problems, Jun 2011, Nymburk, Czech Republic. pp.55-57, 2011
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00649184
Contributeur : Ruslan Sadykov <>
Soumis le : mercredi 7 décembre 2011 - 11:51:03
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 14:40:24

Fichier

colRowGen4TimeIndexForm_MAPSP3...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00649184, version 1

Collections

Citation

Ruslan Sadykov, François Vanderbeck. Machine scheduling by column-and-row generation on the time-indexed formulation. 10th International Workshop on Models and Algorithms for Planning and Scheduling Problems, Jun 2011, Nymburk, Czech Republic. pp.55-57, 2011. 〈hal-00649184〉

Partager

Métriques

Consultations de la notice

341

Téléchargements de fichiers

227