Scheduling batches in flowshop with limited buffers in the shampoo industry
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.
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Kovalyov, Mikhail Y. & Ng, C.T. & Cheng, T.C. Edwin, 2007. "Fixed interval scheduling: Models, applications, computational complexity and algorithms," European Journal of Operational Research, Elsevier, vol. 178(2), pages 331-342, April.
- Mocquillon, Cédric & Lenté, Christophe & T'Kindt, Vincent, 2011. "An efficient heuristic for medium-term planning in shampoo production," International Journal of Production Economics, Elsevier, vol. 129(1), pages 178-185, January.
- Khosla, Inder, 1995. "The scheduling problem where multiple machines compete for a common local buffer," European Journal of Operational Research, Elsevier, vol. 84(2), pages 330-342, July.
- Allahverdi, Ali & Ng, C.T. & Cheng, T.C.E. & Kovalyov, Mikhail Y., 2008. "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 985-1032, June.
- T'kindt, Vincent & Monmarche, Nicolas & Tercinet, Fabrice & Laugt, Daniel, 2002. "An Ant Colony Optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 142(2), pages 250-257, October.
When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:223:y:2012:i:2:p:560-572. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Shamier, Wendy)
If references are entirely missing, you can add them using this form.