In this paper, we propose a new linear algorithm to tackle a specific class of unrelated machine scheduling problem, considered as an important real-life situation, which we called Batch Scheduling on Unrelated Machine (BSUM), where we have to schedule a batch of identical and non-preemptive jobs on unrelated parallel machines. The objective is to minimize the makespan (Cmax) of the whole schedule. For this, a mathematical formulation is made and a lower bound is computed based on the potential properties of the problem in order to reduce the search space size and thus accelerate the algorithm. Another property is also deducted to design our algorithm that solves this problem. The latter is considered as a particular case of RmCmax family problems known as strongly NP-hard, therefore, a polynomial reduction should realize a significant efficiency to treat them. As we will show, Batch BSUM is omnipresent in several kind of applications as manufacturing, transportation, logistic and routing. It is of major importance in several company activities. The problem complexity and the optimality of the algorithm are reported, proven and discussed.

[1] Adan J., Adan I., Akcay A., Van den Dobbelsteen R., and Stokkermans J., “A Hybrid Genetic Algorithm for Parallel Machine Scheduling At Semiconductor Back-End Production,” in Proceedings of the International Conference on Automated Planning and Scheduling,, vol. 28, pp. 298-302, 2018. DOI: https://doi.org/10.1609/icaps.v28i1.13913

[2] Afzalirad M. and Rezaeian J., “A Realistic Variant of Bi-Objective Unrelated Parallel Machine Scheduling Problem: NSGA-II and MOACO Approaches,” Applied Soft Computing, vol. 50, pp. 109-123, 2017. https://doi.org/10.1016/j.asoc.2016.10.039

[3] Afzalirad M. and Shafipour M., “Design of An Efficient Genetic Algorithm for Resource- Constrained Unrelated Parallel Machine Scheduling Problem with Machine Eligibility Restrictions,” Journal of Intelligent Manufacturing, vol. 29, no. 2, pp. 423-437, 2018. DOI:10.1007/s10845-015-1117-6

[4] Afzalirad M. and Rezaeian J., “Resource- Constrained Unrelated Parallel Machine Scheduling Problem With Sequence Dependent Setup Times, Precedence Constraints and Machine Eligibility Restrictions,” Computers and Industrial Engineering, vol. 98, pp. 40-52, 2016. https://doi.org/10.1016/j.cie.2016.05.020

[5] Allahverdi A., “The Third Comprehensive Survey on Scheduling Problems with Setup Times/Costs,” European Journal of Operational Research, vol. 246, no. 2, pp. 345-378, 2015. https://doi.org/10.1016/j.ejor.2015.04.004

[6] Allahverdi A., Ng C., Cheng T., Kovalyov M., “A Survey of Scheduling Problems with Setup Times or Costs,” European Journal of Operational Research, vol. 187, no. 3, pp. 985- 1032, 2008. https://doi.org/10.1016/j.ejor.2006.06.060

[7] Allahverdi A., “The Third Comprehensive Survey on Scheduling Problems with Setup Times/Costs,” European Journal of Operational Research, vol. 246, no. 2, pp. 345-378, 2015. https://doi.org/10.1016/j.ejor.2015.04.004

[8] Chen Z., “Parallel Machine Scheduling with Time Dependent Processing Times,” Discrete Applied Mathematics, vol. 70, no. 1, pp. 81-93, 1996. https://doi.org/10.1016/0166- 218X(96)00102-3

[9] Cheng T., Ding Q., and Lin B., “A Concise Survey of Scheduling with Time-Dependent Processing Times,” Discrete Applied Mathematics, vol. 152, no. 1, pp. 1-13, 2004. https://doi.org/10.1016/0166-218X(96)00102-3

[10] Ebenlendr T., Kral M., and Sgall J., “Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines,” in Proceedings of the nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, pp. 483-490, 2008. DOI:10.1145/1347082.1347135

[11] Fanjul-Peyro L. and Ruiz R., “Iterated Greedy Local Search Methods for Unrelated Parallel Machine Scheduling,” European Journal of Operational Research, vol. 207, no. 1, pp. 55-69, 2010. https://doi.org/10.1016/j.ejor.2010.03.030

[12] Fanjul-Peyro L. and Ruiz R., “Scheduling Exact Algorithm for Batch Scheduling on Unrelated Machine 623 Unrelated Parallel Machines with Optional Machines and Jobs Selection,” Computers and Operations Research, vol. 39, no. 7, pp. 1745- 1753, 2012. https://doi.org/10.1016/j.cor.2011.10.012

[13] Fanjul-Peyro L. and Ruiz R., “Size-Reduction Heuristics for the Unrelated Parallel Machines Scheduling Problem,” Computers and Operations Research, vol. 38, no. 1, pp. 301-309, 2011. https://doi.org/10.1016/j.cor.2010.05.005

[14] Gawiejnowicz S., Time-Dependent Scheduling, Springer, 2008.

[15] Goldwasser M. and Pedigo M., “Online, Non- Preemptive Scheduling of Equal-Length Jobs on Two Identical Machines,” in Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT), Riga, pp. 113-123, 2006.

[16] Ji M. and Cheng T., “Parallel-Machine Scheduling of Simple Linear Deteriorating Jobs,” Theoretical Computer Science, vol. 410, no. 38, pp. 3761-3768, 2009. https://doi.org/10.1016/j.tcs.2009.04.018

[17] Kononov A. and Gawiejnowicz S., “Np-Hard Cases in Scheduling Deteriorating Jobs on Dedicated Machines,” The Journal of the Operational Research Society, vol. 52, no. 6, pp. 708-717, 2001. https://www.jstor.org/stable/254283

[18] Kravchenko S. and Werner F., “Parallel Machine Problems with Equal Processing Times: A Survey,” Journal of Scheduling, vol. 14, pp. 435- 444, 2011. DOI:10.1007/s10951-011-0231-3

[19] Lenstra J., Shmoys D., and Tardos E., “Approximation Algorithms for Scheduling Unrelated Parallel Machines,” Mathematical Programming, vol. 46, pp. 259-271, 1990.

[20] Li S. and Yuan J., “Parallel-Machine Scheduling with Deteriorating Jobs and Rejection,” Theoretical Computer Science, vol. 411, no. 40, pp. 3642-3650, 2010. https://doi.org/10.1016/j.tcs.2010.06.008

[21] Mokotoff E., “Parallel Machine Scheduling Problems: A Survey,” Asia-Pacific Journal of Operational Research, vol. 18, no. 2, pp. 193- 202, 2001.

[22] Moser M., Musliu N., Schaerf A., and Winter F., “Exact and Metaheuristic Approaches for Unrelated Parallel Machine Scheduling,” Journal of Scheduling, vol. 25, no. 5, pp. 507-534, 2022. https://doi.org/10.1007/s10951-021-00714-6

[23] Mosheiov G., “Multi-Machine Scheduling with Linear Deterioration,” Information Systems and Operational Research, vol. 36, no. 4, pp. 205- 214, 1998. https://doi.org/10.1080/03155986.1998.11732359

[24] Munir E., Ijaz S., Anjum S., Khan A., Anwar W., and Nisar W., “Novel Approaches for Scheduling Task Graphs in Heterogeneous Distributed Computing Environment,” The International Arab Journal of Information Technology, vol. 12, no. 3, pp. 270-277, 2015. https://www.iajit.org/PDF/vol.12%2Cno.3/6131. pdf

[25] Ouazene Y. and Yalaoui F., “Identical Parallel Machine Scheduling with Time-Dependent Processing Time,” Theoretical Computer Science, vol. 721, pp. 70-77, 2018. https://doi.org/10.1016/j.tcs.2017.12.001

[26] Pinedo M., Scheduling, Theory, Algorithms, and Systems, Springer Science+Business Media, 2012. DOI 10.1007/978-3-319-26580-3

[27] Shchepin E. and Vakhania N., “An Optimal Rounding Gives A Better Approximation for Scheduling Unrelated Machines,” Operations Research Letters, vol. 33, no. 2, pp. 127-133, 2005. https://doi.org/10.1016/j.orl.2004.05.004

[28] Vakhania N., Werner F., and Alberto J., “Scheduling Unrelated Machines with Two Types of Jobs,” International Journal of Production Research, vol. 52, no. 13, pp. 3793- 3801, 2014. DOI:10.1080/00207543.2014.888789

[29] Yin N., Kang L., Sun T., Yue C., and Wang R., “Unrelated Parallel Machines Scheduling with Deteriorating Jobs and Resource Dependent Processing Times” Applied Mathematical Modelling, vol. 38, no. 19, pp. 4747-4755, 2014. https://doi.org/10.1016/j.apm.2014.03.022