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.
Document type :
Journal articles
Complete list of metadatas

https://hal-univ-tours.archives-ouvertes.fr/hal-01003822
Contributor : Vincent t'Kindt <>
Submitted on : Tuesday, June 10, 2014 - 5:07:24 PM
Last modification on : Friday, July 26, 2019 - 11:58:03 AM

Identifiers

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⟩

Share

Metrics

Record views

92