Scheduling batches in flowshop with buffers in the shampoo industry

Abstract : In this paper we address the problem of planning a temporary storage area in a real production system. This temporary storage area is composed of parallel temporary storage units with distinct capacities. The storage operation of a job, also called a batch, has to answer time restrictions such as release dates, due dates, restricted family dependent setup times and time lags, and also a space constraint which is the capacity of the temporary storage unit. The goal is to schedule the batches on the storage units in order to minimize the total setup times and the maximum lateness. First, we model the problem on a single storage unit as a two-machine flowshop problem with a limited buffer capacity and we show that it is NP-hard. We also show that the particular case in which no lateness is allowed is solvable in polynomial time under special conditions on the buffer capacity, both for single or parallel temporary storage units. Next we provide three heuristics: a greedy algorithm, a hybrid heuristic based on Ant Colony Optimization and Simulated Annealing and finally a dedicated heuristic. The latter strongly exploits the structural properties shown in this paper. We provide experimental results which highlight the efficiency of the dedicated heuristic in comparison with the two other heuristics.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2012, 223 (2), pp.560-572. 〈10.1016/j.ejor.2012.06.035〉
Liste complète des métadonnées

https://hal-univ-tours.archives-ouvertes.fr/hal-01003822
Contributeur : Vincent T'Kindt <>
Soumis le : mardi 10 juin 2014 - 17:07:24
Dernière modification le : mardi 9 octobre 2018 - 11:46:07

Identifiants

Collections

Citation

Rabah Belaid, Vincent T'Kindt, Carl Esswein. Scheduling batches in flowshop with buffers in the shampoo industry. European Journal of Operational Research, Elsevier, 2012, 223 (2), pp.560-572. 〈10.1016/j.ejor.2012.06.035〉. 〈hal-01003822〉

Partager

Métriques

Consultations de la notice

74