Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata
Contributor : Ammar Oulamara Connect in order to contact the contributor
Submitted on : Tuesday, July 5, 2011 - 1:31:17 PM
Last modification on : Saturday, October 16, 2021 - 11:26:05 AM


  • HAL Id : inria-00606093, version 1



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, University of Amsterdam and VU University Amsterdam, May 2011, Amsterdam, Netherlands. ⟨inria-00606093⟩



Record views