Propuesta de heurística para minimizar el cuello de botella y el tiempo de espera en Flujo Continuo
Palabras clave:
Optimización, Flujo continuo, Heurística, Simplex, Metaheurísticas.Resumen
Este artículo presenta una propuesta de Heurística para minimizar dos situaciones que ocurren cuando las máquinas no terminan de procesar los lotes al mismo tiempo: 1) cuello de botella cuando una máquina toma más tiempo en terminar de procesar el lote y 2) tiempo de espera que un lote tiene que esperar para ser procesado por la máquina. Para minimizar ambas situaciones, los lotes deberán tener el mismo tiempo de procesamiento. Para resolver lo anterior, la propuesta de Heurística seleccionara el trabajo con el mayor tiempo de procesamiento y número de piezas. Cada pieza será un lote. El tiempo de procesamiento del lote es determinado por la pieza con el mayor tiempo de procesamiento. Para validar la eficiencia de la Heurística, se recolecto información de un caso de estudio de una compañía metal mecánica. La propuesta de Heurística se comparó con otras heurísticas que se han usado para resolver el procesamiento por lotes, tales como: Primera Entrada- Primera Salida (FIFO), Primera Salida-Primera Entrada (LIFO), Primer Ajuste (FF), Mejor Ajuste (BF), Primer Lote Ajustado (BFF), Primer Ajuste Tiempo de procesamiento más largo (FFLPT), Tamaño del Lote Decreciente (DECR), Orden creciente de la relación entre tiempo de procesamiento y tamaño del trabajo (PIAI) y Simplex. Los resultados mostraron reducción considerable del cuello de botella y tiempo de espera al usar la propuesta de Heurística comparado con las otras heurísticas mencionadas y método Simplex.
Referencias
[1]
X. Li y Y. Wang, «Scheduling Batch Processing Machine Using MAX-MIN Ant System Algorithm Improved by Local Search Method,» Hindawi-Mathematical Problems in Engineering, vol. 2018, pp. 1-10, 2018, doi:10.1155/2018/3124182.
[2] P. Chang y H. Wang, «A heuristic for a batch processing machine scheduled to minimise total completion time with non-identical job sizes,» The International Journal of Advanced Manufacturing Technology, vol. 24, pp. 614-620, 2004, doi:10.1007/s00170-003-1740-9.
[3] S. Molla-Alizadeh-Zavardehi, R. Tavakkoli-Moghaddam y F. Hosseinzadeh Lotfi, «Hybrid Metaheuristics for Solving a Fuzzy Single Batch-Processing Machine Scheduling Problem,» The Scientific World Journal, vol. 14, pp. 1-10, 2014, doi: 10.1155/2014/214615.
[4] E. G. Coffman Jr., M. R. Garey y D. S. Johnson, «Approximation Algorithms for Bin-Packing — An Updated Survey,» Algorithm Design for Computer System Design, vol. 284, pp. 49-106, 1984, doi: 10.1007/978-3-7091-4338-4_3.
[5] V. Chandru y R. Uzsoy, «Minimizing total completion time on a batch processing machine with job families,» Operations Research Letters, vol. 13, pp. 61-65, 1993, doi:10.1016/0167-6377(93)90030-K.
[6] A. Bellanger, A. Janiak, M. Y. Kovalyov y A. Oulamara, «Scheduling an unbounded batching machine with job processing time compatibilities,» Discrete Applied Mathematics, vol. 12, pp. 15-23, 2012, doi:10.1016/j.dam.2011.09.004.
[7] H. Y. Fuchigami y S. Rangel, «A survey of case studies in production scheduling: Analysis and perspectives,» Journal of Computational Science, vol. 25, pp. 425-436, 2018, 10.1016/j.jocs.2017.06.004.
[8] M. Mathirajan, R. Gokhale y M. Ramasubrama, «Modeling of Scheduling Batch Processor in Discrete Parts Manufacturing,» the Supply Chain Strategies, Issues and Models, London., Springer-Verlag, 2014, pp. 153-192, doi:10.1007/978-1-4471-5352-8_7.
[9] Y. Ikura y M. Gimple, «Efficient scheduling algorithms for a single batch processing machine,» Operations Research Letters, vol. 5, nº 2, pp. 61-65, 1986, doi:10.1016/0167-6377(86)90104-5.
[10] P. Damodaran, D. A. Diyadawagamage, O. Ghrayeb y M. C. Vélez-Gallego, «A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines,» International Journal of Advanced Manufacturing Technology, vol. 58, p. 1131–1140, 2012, doi:10.1007/s00170-011-3442-z.
[11] J. W. Fowler y L. Mönch, «A survey of scheduling with parallel batch (p-batch) processing,» European Journal of Operational Research, vol. 298, pp. 1-24, 22, doi: 10.1016/j.ejor.2021.06.012.
[12] R. Uzsoy, «Scheduling a single batch processing machine with non identical job sizes,» International Journal of Production Research, vol. 32, pp. 1615-1635, 1994, doi:10.1080/00207549408957026.
[13] F. J. Ghazvini y L. Dupont, «Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes,» International Journal of Production Economics, vol. 55, pp. 273-280, 1998, doi:10.1016/S0925-5273(98)00067-X.
[14] S. Li, G. Li, X. Wang y . Q. Liu, «Minimizing makespan on a single batching machine with release times and non-identical job sizes,» Operations Research Letters, vol. 33, pp. 157-164, 2005, doi:10.1016/j.orl.2004.04.009.
[15] H. Chen, D. Bing y G. Q. Huang, «Scheduling a batch processing machine with non-identical job sizes: a clustering perspective,» International Journal of Production Research, vol. 49, nº 19, pp. 5755-5778, 2011, doi:10.1080/00207543.2010.512620.
[16] X. Li, Y. Li y Y. Wang, «Minimizing makespan on a batch processing machine using heuristics improved by an enumeration scheme,» International Journal of Production Research, vol. 55, nº 1, pp. 176-186, 2016, doi:10.1080/00207543.2016.1200762.
[17] J. Miaomiao , . L. Xiaoxia y . L. Wenchang , «Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection,» Mathematics, nº 258, 2020, doi.10.3390/math8020258.
[18] M. Johson, «Optimal two- and three-stage production schedules with setup times included,» Naval Research Logistics Quarterly, nº 1, pp. 61-68, 1954, doi:org/10.1002/nav.3800010110.
[19] P. K. Manjeshwar, P. Damodaran y K. Srihari, «Minimizing makespan in a flow shop with two batch-processing machine using simulated annealing,» Robotics and Computer-Integrated Manufacturing, vol. 25, pp. 667-679, 2009, doi:10.1016/j.rcim.2008.05.003.
[20] L. Tang y P. Liu, «Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration,» Applied Mathematical Modelling, vol. 33, pp. 1187-1199, 2009, doi: 10.1016/j.apm.2008.01.013.
[21] H. S. Mirsanei, B. Karimi y F. Jolai, «Flow shop scheduling with two batch processing machines and nonidentical job sizes,» International Journal of Advanced Manufacturing Technology, vol. 45, nº 553, p. 45, 2009, doi: 10.1007/s00170-009-1986-y.
[22] R. Lin y C.-J. Liao, «A case study of batch scheduling for an assembly shop,» International Journal of Production Economics, vol. 139, pp. 473-483, 2012, doi:10.1016/j.ijpe.2012.05.002.
[23] A. Baskar, M. A. Xavior y . N. Na, «Analysis of a Few Simple Heuristics for the Permutation Flow Shop Scheduling Problems for any Batch Processing Industry,» Materials Today: Proceedings, vol. 5, p. 11762–11770, 2018, doi: 10.1016/j.matpr.2018.02.145.
[24] J.-H. Han y . J.-Y. Lee, «Heuristics for a Two-Stage Assembly-Type Flow Shop with Limited Waiting Time Constraints,» Applied Sciences, vol. 11, nº 23, 2021, doi: 10.3390/app112311240.
[25] T.-C. Lo y B. Lin, «Relocation Scheduling in a Two-Machine Flow Shop with Resource Recycling Operations,» Mathematics, vol. 9, nº 1527, 2021, doi: 10.3390/math9131527.
[26] H. A. E.-W. Khalifa, S. S. Alodhaibi y P. Kumar, «Solving Constrained Flow-Shop Scheduling Problem through Multistage Fuzzy Binding Approach with Fuzzy Due Dates,» Advances in Fuzzy Systems , p. 8, 2021, doi: 10.1155/2021/6697060.
[27] M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Fifth Edition, New York: Springer, 2016.
[28] R. L. Graham, E. L. Lawler, J. K. Lenstra y A. H. RinnooyKan, «Optimization and Approximation in Deterministic Sequencing and Scheduling: a SURVEY,» Annals of Discrete Mathematics, vol. 5, pp. 287-326, 1979, doi: 10.1016/S0167-5060(08)70356-X.
[29] A. H. Kashan, B. Karimi y F. Jolai, «Minimizing Makespan on a Single Batch Processing Machine with Non-identical Job Sizes: A Hybrid Genetic Approach,» de European Conference on Evolutionary Computation in Combinatorial Optimization, Budapest, 2006, doi: 10.1007/11730095_12.
[30] S.Zhou, M. Liu, H.Cheng y X. Li, «An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes,» International Journal of Production Economics, vol. 179, pp. 1-11, 2016, doi:10.1016/j.ijpe.2016.05.014.
[31] X. Li, Y. Huang, Q. Tan y H. Chen, «Scheduling unrelated parallel batch processing machines with non-identical job sizes,» Computers & Operations Research, vol. 12, pp. 2983-299, 2013, doi.org/10.1016/j.cor.2016.08.015.
[32] P. Damodaran y P.-Y. Chang, «Heuristics to minimize makespan of parallel batch processing machines,» The International Journal of Advanced Manufacturing Technology, vol. 37, p. 1005–1013, 2007, doi: 10.1007/s00170-007-1042-8.
[33] E. Talliard, «Benchmarks for basic scheduling problems,» European Journal of Operational Research, vol. 64, pp. 278-285, 1993, doi: 10.1016/0377-2217(93)90182-M.
[34] H. E. Khalifa, P. Kumar y S. Mirjalili, «A KKM approach for inverse capacitated transportation problem in neutrosophic environment,» Sādhanā- Springer Nature, vol. 46, nº 166, 2021, doi: 10.1007/s12046-021-01682-5.
[35] P. Kumar y H. A. El- Wahed Khalifa, «Solving fully neutrosophic linear programming problem with application to stock portfolio selection,» Croatian Operational Research Review, nº 11, pp. 165-176, 2020, doi:10.17535/crorr.2020.0014.
