An estimation of distribution algorithm for lot-streaming flow shop problems with setup times
AbstractLot-streaming flow shops have important applications in different industries including textile, plastic, chemical, semiconductor and many others. This paper considers an n-job m-machine lot-streaming flow shop scheduling problem with sequence-dependent setup times under both the idling and no-idling production cases. The objective is to minimize the maximum completion time or makespan. To solve this important practical problem, a novel estimation of distribution algorithm (EDA) is proposed with a job permutation based representation. In the proposed EDA, an efficient initialization scheme based on the NEH heuristic is presented to construct an initial population with a certain level of quality and diversity. An estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. A simple but effective local search is added to enhance the intensification capability. A diversity controlling mechanism is applied to maintain the diversity of the population. In addition, a speed-up method is presented to reduce the computational effort needed for the local search technique and the NEH-based heuristics. A comparative evaluation is carried out with the best performing algorithms from the literature. The results show that the proposed EDA is very effective in comparison after comprehensive computational and statistical analyses.
Download InfoIf 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.
Bibliographic InfoArticle provided by Elsevier in its journal Omega.
Volume (Year): 40 (2012)
Issue (Month): 2 (April)
Contact details of provider:
Web page: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description
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.:
- Ruiz, Ruben & Maroto, Concepcion, 2005. "A comprehensive review and evaluation of permutation flowshop heuristics," European Journal of Operational Research, Elsevier, vol. 165(2), pages 479-494, September.
- Allahverdi, Ali & Soroush, H.M., 2008. "The significance of reducing setup times/setup costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 978-984, June.
- Rios-Mercado, Roger Z. & Bard, Jonathan F., 1998. "Heuristics for the flow line problem with setup costs," European Journal of Operational Research, Elsevier, vol. 110(1), pages 76-98, October.
- Quan-Ke Pan & Ling Wang, 2008. "A novel differential evolution algorithm for no-idle permutation flow-shop scheduling problems," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 2(3), pages 279-297.
- Walid Besbes & Jacques Teghem & Taicir Loukil, 2010. "Scheduling hybrid flow shop problem with non-fixed availability constraints," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 4(4), pages 413-433.
- Hamed Samarghandi & Tarek Y. ElMekkawy, 2011. "An efficient hybrid algorithm for the two-machine no-wait flow shop problem with separable setup times and single server," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 5(2), pages 111-131.
- Tseng, Chao-Tang & Liao, Ching-Jong, 2008. "A discrete particle swarm optimization for lot-streaming flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 191(2), pages 360-373, December.
- Kalir, Adar A. & Sarin, Subhash C., 2001. "A near-optimal heuristic for the sequencing problem in multiple-batch flow-shops with small equal sublots," Omega, Elsevier, vol. 29(6), pages 577-584, December.
- 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.
- Allahverdi, Ali & Gupta, Jatinder N. D. & Aldowaisan, Tariq, 1999. "A review of scheduling research involving setup considerations," Omega, Elsevier, vol. 27(2), pages 219-239, April.
- Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
- Martin, Clarence H, 2009. "A hybrid genetic algorithm/mathematical programming approach to the multi-family flowshop scheduling problem with lot streaming," Omega, Elsevier, vol. 37(1), pages 126-137, February.
- Zhang, Wei & Yin, Changyu & Liu, Jiyin & Linn, Richard J., 2005. "Multi-job lot streaming to minimize the mean completion time in m-1 hybrid flowshops," International Journal of Production Economics, Elsevier, vol. 96(2), pages 189-200, May.
- Vickson, R. G., 1995. "Optimal lot streaming for multiple products in a two-machine flow shop," European Journal of Operational Research, Elsevier, vol. 85(3), pages 556-575, September.
- Vallada, Eva & Ruiz, Rubén, 2010. "Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem," Omega, Elsevier, vol. 38(1-2), pages 57-67, February.
- Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
- Rad, Shahriar Farahmand & Ruiz, Rubén & Boroojerdian, Naser, 2009. "New high performing heuristics for minimizing makespan in permutation flowshops," Omega, Elsevier, vol. 37(2), pages 331-345, April.
- Ribas, Imma & Companys, Ramon & Tort-Martorell, Xavier, 2011. "An iterated greedy algorithm for the flowshop scheduling problem with blocking," Omega, Elsevier, vol. 39(3), pages 293-301, June.
- Ruiz, Rubén & Maroto, Concepciøn & Alcaraz, Javier, 2006. "Two new robust genetic algorithms for the flowshop scheduling problem," Omega, Elsevier, vol. 34(5), pages 461-476, October.
- Ruiz-Torres, Alex J. & Ho, Johnny C. & Ablanedo-Rosas, José H., 2011. "Makespan and workstation utilization minimization in a flowshop with operations flexibility," Omega, Elsevier, vol. 39(3), pages 273-282, June.
- Jorge M.S. Valente & Jeffrey E. Schaller, 2010. "Improved heuristics for the single machine scheduling problem with linear early and quadratic tardy penalties," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 4(1), pages 99-129.
- Adel Manaa & Chengbin Chu, 2010. "Scheduling multiprocessor tasks to minimise the makespan on two dedicated processors," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 4(3), pages 265-279.
- Chen, Shih-Hsin & Chen, Min-Chih, 2013. "Addressing the advantages of using ensemble probabilistic models in Estimation of Distribution Algorithms for scheduling problems," International Journal of Production Economics, Elsevier, vol. 141(1), pages 24-33.
- Pan, Quan-Ke & Ruiz, Rubén, 2014. "An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem," Omega, Elsevier, vol. 44(C), pages 41-50.
- Pan, Quan-Ke & Wang, Ling & Li, Jun-Qing & Duan, Jun-Hua, 2014. "A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation," Omega, Elsevier, vol. 45(C), pages 42-56.
- Malaguti, Enrico & Medina Durán, Rosa & Toth, Paolo, 2014. "Approaches to real world two-dimensional cutting problems," Omega, Elsevier, vol. 47(C), pages 99-115.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei).
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.