Minimizing total completion time on a bounded batching machine with job compatibilities and one unavailability period

Adrien Bellanger 1 Ammar Oulamara 1
1 ORCHIDS - Operations research for Complex HybrId Decision Sytems
LORIA - NSS - Department of Networks, Systems and Services
Abstract : Originally in production scheduling theory a machine can process only one job at once and is always available, but in some contemporary factories -like semiconductor or tire manufacturing factories- those restrictions are outdated. Machines can process several jobs simultaneously, and maintenance activities could be needed along the schedule. In this abstract, the problem of minimizing the total completion time on an bounded batching machine with job compatibilities and a maintenance task is studied. The machine can process k jobs simultaneously in a batch with respect to the additional constraint that, in the same batch, the job processing times are compatible. Each job has a normal processing time which could be increased of a certain percent to be compatible with longer jobs. Note that this percent is the same for all jobs. Thus, all job has a processing time interval, and two jobs are compatible if their processing time intervals intersect. Since the objective function is regular, the batch processing time is equal to the left endpoint of the intersection of the processing time intervals of the batch's jobs. Then the batch processing time is the smallest processing time shared by all its jobs, and all jobs of the batch start and complete together. This problem has been proven to be NP-Hard even for unit capacity. The pseudo-polynomial dynamic programming algorithm developed in this paper implies that the problem is weakly NP-hard. In addition to this complexity result, a heuristic with performance guarantee is presented.
Type de document :
Communication dans un congrès
The 24th Conference of the European Chapter on Combinatorial Optimization - ECCO 2011, May 2011, Amsterdam, Netherlands. 2011
Liste complète des métadonnées

https://hal.inria.fr/inria-00606093
Contributeur : Ammar Oulamara <>
Soumis le : mardi 5 juillet 2011 - 13:31:17
Dernière modification le : mardi 24 avril 2018 - 13:30:38

Identifiants

  • HAL Id : inria-00606093, version 1

Collections

Citation

Adrien Bellanger, Ammar Oulamara. Minimizing total completion time on a bounded batching machine with job compatibilities and one unavailability period. The 24th Conference of the European Chapter on Combinatorial Optimization - ECCO 2011, May 2011, Amsterdam, Netherlands. 2011. 〈inria-00606093〉

Partager

Métriques

Consultations de la notice

74