A Heuristic proposal to minimize bottleneck and waiting time in a Flow Shop
Keywords:
Optimization, Flow shop, Heuristic, Simplex, Metaheuristic.Abstract
This article presents a Heuristic proposal to minimize two situations that occur when machines do not finish processing batches at the same time: 1) bottleneck when a machine takes more time to finish a batch and 2) waiting time that a batch must wait before being processed by the machine. To minimize both situations, batches must have the same processing time. To solve the above, the Heuristic proposal will select the job with the longest processing time and the number of pieces. Each piece will be a batch. The batch processing time is determined by the piece with the longest processing time. To validate the efficiency of the heuristic, information was collected from a case study of a metal-mechanic company. The Heuristic proposal was compared with other heuristics that have been used to solve the batch processing such as: First in-First Out (FIFO), Last in-First out (LIFO), Best Fit (BFF), First Fit (FF), Batch First Fit (BFF), First Fit Longest Processing Time (FFLPT), Decreasing Batch Size (DECR), Processing time to job size ratio increasing order (PIAI) and the Simplex method. The results showed an considerable reduction of bottleneck and waiting time using the Heuristic proposal compared with the others mentioned heuristic and the Simplex method.
References
[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.
