nach oben

Journal of Intelligent Manufacturing

Erschienen in:

24.08.2017

An evolutionary clustering search for the total tardiness blocking flow shop problem

verfasst von: Marcelo Seido Nagano, Adriano Seiko Komesu, Hugo Hissashi Miyata

Erschienen in: Journal of Intelligent Manufacturing | Ausgabe 4/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we propose the evolutionary clustering search (ECS) algorithm combined with a variable neighbourhood search (VNS) for the m-machine blocking flow shop scheduling problem with total tardiness minimization. The proposed ECS uses NEH-based procedure to generate an initial solution, the genetic algorithm to generate solutions and VNS to improve the solutions. A set of experiments were carried out to adjust the parameter of the metaheuristic. ECS is compared with ILS by Ribas et al. (J Prod Res 51(17):5238–5252, 2013), known as the best metaheuristic for the problem. Computational tests show superiority of the new method for the set of problems evaluated. Finally, we update 67 new best values of best-know found by ECS.

Vorheriger Artikel An equivalent generating algorithm to model fuzzy Petri net for knowledge-based system

Nächster Artikel Scalability in manufacturing systems: a hybridized GA approach

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abadi, I. K., Hall, G., & Sriskandarajah, C. (2007). Minimizing cycle time in a blocking flowshop. Operations Research, 19(7), 1553–1570.

Armentano, V. A., & Ronconi, D. (1999). Tabu search for total tardiness minimization in flowshop scheduling problems. Computers and Operations Research, 26, 219–235.CrossRef

Armentano, V. A., & Ronconi, D. (2000). Minimização do Tempo Total de Atraso no Problema FlowShop com Buffer Zero Através de Busca Tabu. Gestão & Produção, 7, 353–63.CrossRef

Caraffa, V., Ianes, S., Bagchi, T., & Sriskandarajah, C. (2001). Minimizing makespan in a blocking flowshop using genetic algorithms. International Journal of Production Economics, 70, 101–115.CrossRef

Companys, R., & Mateo, M. (2007). Different behaviour of a double branch-and-bound algorithm on Fm|prmu|Cmax and Fm|block|Cmax problems. Computers and Operations Research, 34(4), 938–953.CrossRef

Companys, R., Ribas, I., & Mateo, M. (2010). Improvement Tools for NEH based heuristics on permutation and blocking flow shop scheduling problems. In B. Vallespir & T. Alix (Eds.), Advances in production management systems: New challenges, new approaches (Vol. 338, pp. 33–40). Berlin: Springer.

Davendra, D., & Bialic Davendra, M. (2013). Scheduling flow shops with blocking using a discrete self-organising migrating algorithm. International Journal of Production Research, 51, 2200–2218.CrossRef

Davendra, D., Zelinka, I., Bialic-Davendra, M., Senkerik, R., & Jasek, R. (2012). Clustered enhanced differential evolution for the blocking flow shop scheduling problem. Central European Journal of Operations Research, 20(4), 679–717.CrossRef

Deng, G., Xu, Z., & Gu, X. (2012). A discrete artificial bee colony algorithm for minimizing the total flow time in the blocking flow shop scheduling. Chinese Journal of Chemical Engineering, 20(6), 1067–1073.CrossRef

Ding, J.-Y., Song, S., Gupta, J. D., Wang, C., Zhang, R., & Wu, C. (2015). New block properties for flowshop scheduling with blocking and their application in an iterated greedy algorithm. International Journal of Production Research, 7543, 1–14.

Eddaly, M., Jarboui, B., & Siarry, P. (2016). Combinatorial particle swarm optimization for solving blocking flowshop scheduling problem. Journal of Computational Design and Engineering, 3, 295–311.CrossRef

Fernandez-Viagas, V., Leisten, R., & Framinan, J. M. (2016). A computational evaluation of constructive and improvement heuristics for the blocking flow shop to minimise total flowtime. Expert Systems With Applications, 61, 290–301.CrossRef

Glover, F. (1996). Tabu search and adaptive memory programing: Advances, applications and challenges. Interfaces in Computer Science and Operations Research, 7, 1–75.

Gong, H., Tong, L., & Duin, C. W. (2010). A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times. Computers & Operations Research, 37, 960–969.CrossRef

Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnoy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.CrossRef

Grabowski, J., & Pempera, J. (2000). Sequencing of jobs in some production system. European Journal of Operational Research, 125, 535–550.CrossRef

Grabowski, J., & Pempera, J. (2007). The permutation flow shop problem with blocking. A tabu search approach. Omega, 35, 302–311.CrossRef

Gupta, J. N. D., & Stafford, E. F, Jr. (2006). Flowshop scheduling research after five decades. European Journal of Operational Research, 169, 699–711.CrossRef

Hall, N. G., & Sriskandarajah, C. (1996). A survey of machine scheduling problems with blocking and no-wait in process. Operations Research, 44, 510–525.CrossRef

Han, Y.-Y., Pan, Q.-K., Li, J.-Q., & Sang, H. (2012). An improved artificial bee colony algorithm for the blocking flowshop scheduling problem. The International Journal of Advanced Manufacturing Technology, 60(9–12), 1149–1159.CrossRef

Han, Y. Y., Liang, J. J., Pan, Q. K., et al. (2013). Effective hybrid discrete artificial bee colony algorithms for the total flowtime minimization in the blocking flowshop problem. International Journal of Advanced Manufacturing Technology, 67(1–4), 397–414.CrossRef

Han, Y.-Y., Gong, D., & Sun, X. (2015). A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking. Engineering Optimization, 47(7), 927–946.CrossRef

Han, Y., Gong, D., Li, J., & Zhang, Y. (2016). Solving the blocking flow shop scheduling problem with makespan using a modified fruit fly optimisation algorithm. International Journal of Production Research, 54, 6782–6797.CrossRef

Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61–68.CrossRef

Khorasanian, D., & Moslehi, G. (2012). An iterated greedy algorithm for solving the blocking flow shop scheduling problem with total flow time criteria. International Journal of Industrial Engineering & Production Research, 23(4), 301–308.

Leisten, R. (1985). Flowshop sequencing problems with limited buffer storage. International Journal of Production Research, 28, 2085–2100.CrossRef

Liang, J. J., Pan, Q.-K., Chen, T., & Wang, L. (2011). Solving the blocking flow shop scheduling problem by a dynamic multi-swarm particle swarm optimizer. International Journal of Advanced Manufacturing Technology, 55(5–8), 755–762.CrossRef

Lin, S. W., & Ying, K. C. (2013). Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm. Omega, 41(2), 383–389.CrossRef

Martinez, S., Dauzère-Pérès, S., Guéret, C., Mati, Y., & Sauer, H. (2006). Complexity of flowshop scheduling problems with a new blocking constraint. European Journal of Operational Research, 169, 855–864.CrossRef

Mccormick, S. T., Pinedo, M. L., Shenker, S., & Wolf, B. (1989). Sequencing in an assembly line with blocking to minimize cycle time. Operations Research, 37(6), 925–935.CrossRef

Moslehi, G., & Khorasanian, D. (2013). Optimizing blocking flow shop scheduling problem with total completion time criterio. Computers & Operations Research, 40(7), 1874–1883.CrossRef

Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11, 91–95.CrossRef

Nagano, M. S., Da Silva, A. A., & Lorena, L. A. N. (2012). A new evolutionary clustering search for a no-wait flow shop problem with set-up times. Engineering Applications of Artificial Intelligence, 25, 1114–1120.CrossRef

Nagano, M. S., Da Silva, A. A., & Lorena, L. A. N. (2014). An evolutionary clustering search for the no-wait flow shop problem with sequence dependent setup times. Expert Systems with Applications, 41, 3628–3633.CrossRef

Oliveira, A. C. M., & Lorena, L. A. N. (2004). Detecting promising areas by evolutionary clustering search. In A. L. C. Bazzan & S. Labidi (Eds.), Advances in artificial intelligence. Lecture notes in artificial intelligence (pp. 385–394). Berlin: Springer.

Oliveira, A. C. M., & Lorena, L. A. N. (2007). Hybrid evolutionary algorithms and clustering search. In C. Grosan, A. Abraham, & H. Ishibuchi (Eds.), Hybrid evolutionary systems–Studies in computational intelligence—Springer SCI series 75 (pp. 81–102). Berlin: Springer.

Pan, Q. K., & Wang, L. (2012). Effective heuristics for the blocking flowshop scheduling problem with makespan minimization. Omega, 40(2), 218–229.CrossRef

Pan, Q., Wang, L., Sang, H., Li, J., & Liu, M. (2013). A high performing memetic algorithm for the flowshop scheduling problem with blocking. IEEE Transactions on Automation Science and Engineering, 10, 741–756.CrossRef

Pinedo, M. (1995). Scheduling: theory, algorithms, and systems (2nd ed.). Upper Saddle River: Prentice-Hall.

Potts, C. N., & Van Wassenhove, L. N. (1982). A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 1, 177–81.CrossRef

Reddi, S. S., & Ramamoorthy, C. V. (1972). On the flowshop sequencing problem with no-wait in process. Operational Research Quarterly, 23, 323–330.CrossRef

Ribas, I., Companys, R., & Tort-Martorell, X. (2013). An efficient iterated local search algorithm for the total tardiness blocking flow shop problem. International Journal of Production Research, 51(17), 5238–5252.CrossRef

Ribas, I., & Companys, R. (2013). A competitive variable neighbourhood search algorithm for the blocking flow shop problem. European Journal of Industrial Engineering, 7(6), 729–754.CrossRef

Ribas, I., & Companys, R. (2015). Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization. Computers and Industrial Engineering, 87, 30–39.CrossRef

Ribas, I., Companys, R., & Tort-Martorell, X. (2011). An iterated greedy algorithm for the flowshop scheduling with blocking. Omega, 39, 293–301.CrossRef

Ribas, I., Companys, R., & Tort-Martorell, X. (2015). An efficient discrete artificial bee colony algorithm for the blocking flow shop problem with total flowtime minimization. Expert Systems with Applications, 42(15–16), 37–41.

Ribeiro Filho, G., Nagano, M. S., & Lorena, L. A. N. (2007a). Hybrid evolutionary algorithm for flowtime minimisation in no-wait flowshop scheduling. Lecture Notes in Artificial Intelligence, 4827, 1099–1109.

Ribeiro Filho, G., Nagano, M. S., & Lorena, L. A. N. (2007b). Evolutionary clustering search for flowtime minimization in permutation flow shop. Lecture Notes in Computer Science, 4771, 69–81.CrossRef

Ronconi, D. (2005). A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking. Annals of Operations Research, 138, 53–65.CrossRef

Ronconi, D. (2004). A note on constructive heuristics for the flowshop problem with blocking. International Journal of Production Economics, 87(1), 39–48.CrossRef

Ronconi, D., & Armentano, V. A. (2001). Lower bounding schemes for flowshops with blocking in-process. Journal of the Operational Research Society, 52, 1289–1297.CrossRef

Ronconi, D., & Henriques, L. R. S. (2009). Some heuristic algorithms for total tardiness minimization in a flowshop with blocking. Omega, 37, 272–281.CrossRef

Sanches, F. B., Takano, M. I., & Nagano, M. S. (2016). Evaluation of heuristics for a branch and bound algorithm to minimize the makespan in a flowshop with blocking. Acta Scientiarum. Technology, 38(3), 321–326.CrossRef

Suhami, I., & Mah, R. S. H. (1981). An implicit enumeration scheme for the flowshop problem with no intermediate storage. Computers and Chemical Engineering, 5, 83–91.CrossRef

Toumi, S., Jarboui, B., Eddaly, M., & Rebai, A. (2013a). Branch and bound algorithm for solving blocking flowshop scheduling problem with total completion time. In International conference on control, decision and information technologies (CoDIT) (pp. 746–749). IEEE

Toumi, S., Jarboui, B., Eddaly, M., & Rebai, A. (2013b). Lower bounds on the total tardiness and total weighted tardiness for scheduling flowshop with blocking. In International conference on advanced logistics and transport, ICALT (pp. 296–301).

Syswerda, G. (1989). Uniform crossover in genetic algorithms. In International conference on genetic algorithms (ICGA), Virginia, USA (pp. 2–9).

Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278–285.CrossRef

Tasgetiren, M. F., Pan, Q., Kizilay, D., & Gao, K. (2016). A variable block insertion heuristic for the blocking flowshop scheduling problem with total flowtime criterion. Algorithms, 9(4), 1–24.CrossRef

Tasgetiren, M. F., Kizilay, D., Pan, Q., & Suganthan, N. (2017). Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion. Computers and Operation Research, 77, 111–126.CrossRef

Wang, L., Pan, Q.-K., Suganthan, N., Wang, W.-H., & Wang, Y.-M. (2010a). A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems. Computers & Operations Research, 37, 509–520.CrossRef

Wang, L., Pan, Q.-K., & Tasgetiren, M. F. (2010b). Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms. Expert Systems with Applications, 37(12), 7929–7936.

Wang, L., Pan, Q.-K., & Tasgetiren, M. F. (2011). A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem. Computers & Industrial Engineering, 61, 76–83.CrossRef

Wang, C., Song, S., Gupta, J. D., & Wu, C. (2012). A three-phase algorithm for flowshop scheduling with blocking to minimize makespan. Computers and Operations Research, 39(11), 2880–2887.CrossRef

Wang, X., & Tang, L. (2012). A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking. Applied Soft Computing Journal, 12(2), 652–662.CrossRef

Titel: An evolutionary clustering search for the total tardiness blocking flow shop problem
verfasst von: Marcelo Seido Nagano
Adriano Seiko Komesu
Hugo Hissashi Miyata
Publikationsdatum: 24.08.2017
Verlag: Springer US
Erschienen in: Journal of Intelligent Manufacturing / Ausgabe 4/2019
Print ISSN: 0956-5515
Elektronische ISSN: 1572-8145
DOI: https://doi.org/10.1007/s10845-017-1358-7

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2019

Multiple failure behaviors identification and remaining useful life prediction of ball bearings

On the robustness of joint production and maintenance scheduling in presence of uncertainties

Metacognitive learning approach for online tool condition monitoring

Multi-phase sequential preventive maintenance scheduling for deteriorating repairable systems

Diameter prediction and optimization of hot extrusion-synthesized polypropylene filament using statistical and soft computing techniques

Association rule mining and cognitive pairwise rating based portfolio analysis for product family design

Premium Partner

Marktübersichten