Skip to Main content Skip to Navigation
Journal articles

Scheduling batches in flowshop with buffers in the shampoo industry

Rabah Belaid 1 Vincent t'Kindt 2 Carl Esswein 2 
2 ROOT - Recherche Opérationnelle, Ordonnancement, Transport ERL 7002
LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours, CNRS - Centre National de la Recherche Scientifique : EMR7002 / ERL7002
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.
Document type :
Journal articles
Complete list of metadata
Contributor : Vincent T'Kindt Connect in order to contact the contributor
Submitted on : Tuesday, June 10, 2014 - 5:07:24 PM
Last modification on : Tuesday, August 30, 2022 - 5:14:20 PM



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⟩



Record views