The Unrelated Parallel Machine Considering Multi-task Simultaneous Supervision Dual Resources Constraints to Minimize Makespan: Scheduling Model for Unrelated Parallel Machine Considering Multi-task Simultaneous Supervision Dual Resources Constraints (MTSSDRC) to Minimize Makespan

Akbar Rugova; Sukoyo; Muhammad Akbar

doi:10.61221/jriem.v2i1.28

Authors

Akbar Rugova Bandung Institude of Technology
Sukoyo
Muhammad Akbar

DOI:

https://doi.org/10.61221/jriem.v2i1.28

Keywords:

MTSSDRC, UPMSP

Abstract

To maximize their production, many companies invest their funds into a semi-automatic machine to help them reach their fullest potential. However, many forgot to also take into account the adjustments that have to be done to the preexisting schedule because of the idle time that operators have now that the new machine has arrived. Multi-task simultaneous supervision dual resource constraints (MTSSDRC) have been the go-to method to solve that problem. Nonetheless, there is still an absence in an MTSSDRC field that involves an Unrelated Parallel Machine Scheduling Problem (UPMSP). This research proposed a model of MTSSDRC that is in line with UPMSP where the machine is a complex system and variations of machining speed can happen from a certain machine to certain jobs. This research also brought MTSSDRC closer to its real-life counterpart as a shop floor that exists in many manufacturing industries.

References

Akbar, M., & Irohara, T. (2018a). Dual resource constrained scheduling considering operator working modes and moving in identical parallel machines using a permutation-based genetic algorithm. IFIP Advances in Information and Communication Technology, 535, 464–472. https://doi.org/10.1007/978-3-319-99704-9_57

Akbar, M., & Irohara, T. (2018b). Scheduling for sustainable manufacturing: A review. In Journal of Cleaner Production (Vol. 205, pp. 866–883). Elsevier Ltd. https://doi.org/10.1016/j.jclepro.2018.09.100

Akbar, M., & Irohara, T. (2020a). Metaheuristics for the multi-task simultaneous supervision dual resource-constrained scheduling problem. Engineering Applications of Artificial Intelligence, 96. https://doi.org/10.1016/j.engappai.2020.104004

Akbar, M., & Irohara, T. (2020b). NSGA-II variants for solving a social-conscious dual resource-constrained scheduling problem. Expert Systems with Applications, 162. https://doi.org/10.1016/j.eswa.2020.113754

Andrade-Pineda, J. L., Canca, D., Gonzalez-R, P. L., & Calle, M. (2020). Scheduling a dual-resource flexible job shop with makespan and due date-related criteria. Annals of Operations Research, 291(1–2), 5–35. https://doi.org/10.1007/s10479-019-03196-0

Aron, R., & Abraham, A. (2022). Resource scheduling methods for cloud computing environment: The role of meta-heuristics and artificial intelligence. In Engineering Applications of Artificial Intelligence (Vol. 116). Elsevier Ltd. https://doi.org/10.1016/j.engappai.2022.105345

Arroyo, J. E. C., & Leung, J. Y. T. (2017). Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times. Computers and Operations Research, 78, 117–128. https://doi.org/10.1016/j.cor.2016.08.015

Avgerinos, I., Mourtos, I., Vatikiotis, S., & Zois, G. (2023). Weighted tardiness minimization for unrelated machines with sequence-dependent and resource-constrained setups. http://arxiv.org/abs/2307.06671

Baptiste, P., Rebaine, D., & Zouba, M. (2017). FPTAS for the two identical parallel machine problem with a single operator under the free changing mode. European Journal of Operational Research, 256(1), 55–61. https://doi.org/10.1016/j.ejor.2016.05.062

Bazargan-Lari, M. R., Taghipour, S., Zaretalab, A., & Sharifi, M. (2022). Production scheduling optimization for parallel machines subject to physical distancing due to COVID-19 pandemic. Operations Management Research, 15(1–2), 503–527. https://doi.org/10.1007/s12063-021-00233-9

Berthier, A., Yalaoui, A., Chehade, H., Yalaoui, F., Amodeo, L., & Bouillot, C. (2022). Unrelated parallel machines scheduling with dependent setup times in textile industry. Computers and Industrial Engineering, 174. https://doi.org/10.1016/j.cie.2022.108736

Berti, N., Finco, S., Battaïa, O., & Delorme, X. (2021). Ageing workforce effects in Dual-Resource Constrained job-shop scheduling. International Journal of Production Economics, 237. https://doi.org/10.1016/j.ijpe.2021.108151

Chen, H., Guo, P., Jimenez, J., Dong, Z. S., & Cheng, W. (2023). Unrelated Parallel Machine Photolithography Scheduling Problem with Dual Resource Constraints. IEEE Transactions on Semiconductor Manufacturing, 36(1), 100–112. https://doi.org/10.1109/TSM.2022.3232108

Cheng, T. C. E., & Sin, C. C. S. (1990). A state-of-the-art review of parallel-machine scheduling research. In European Journal of Operational Research (Vol. 47).

Costa, A., Cappadonna, F. A., & Fichera, S. (2013). A hybrid genetic algorithm for job sequencing and worker allocation in parallel unrelated machines with sequence-dependent setup times. International Journal of Advanced Manufacturing Technology, 69(9–12), 2799–2817. https://doi.org/10.1007/s00170-013-5221-5

Cunha, M. M., Viegas, J. L., Martins, M. S. E., Coito, T., Costigliola, A., Figueiredo, J., Sousa, J. M. C., & Vieira, S. M. (2019). Dual resource constrained scheduling for quality control laboratories. IFAC-PapersOnLine, 52(13), 1421–1426. https://doi.org/10.1016/j.ifacol.2019.11.398

Eimaraghy, H. (2000). Scheduling of Manufacturing Systems Under Dual-Resource Constraints Using Genetic Algorithms. In ~ Journal of Manufacturing Systems (Vol. 19, Issue 3).

Fleszar, K., & Hindi, K. S. (2018). Algorithms for the unrelated parallel machine scheduling problem with a resource constraint. European Journal of Operational Research, 271(3), 839–848. https://doi.org/10.1016/j.ejor.2018.05.056

Ho, C.-J., & Lau, H.-S. (1992). Minimizing Total Cost in Scheduling Outpatient Appointments. Management Science, 38(12), 1750–1764. https://doi.org/10.1287/mnsc.38.12.1750

Karabegović, I., Husak, E., Karabegović, E., & Mahmić, M. (2016). The Role of Industrial Robots in the Development of Automotive Industry in China HOW THE CORE TECHNOLOGIES OF INDUSTRY 4.0 ARE CHANGING THE AUTOMOTIVE INDUSTRY IN THE WORLD, WITH A FOCUS ON CHINA. https://www.researchgate.net/publication/312376111

Koulamas, C. (1994). Total tardiness problem: review and extensions. Operations Research, 42(6), 1025–1041. https://doi.org/10.1287/opre.42.6.1025

Koulamas, C., & Kyparisis, G. J. (2023). A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems. In European Journal of Operational Research (Vol. 305, Issue 3, pp. 999–1017). Elsevier B.V. https://doi.org/10.1016/j.ejor.2022.03.043

Kumar, V. S. A., Marathe, M. V., Parthasarathy, S., & Srinivasan, A. (2009). A unified approach to scheduling on unrelated parallel machines. Journal of the ACM, 56(5). https://doi.org/10.1145/1552285.1552289

Lei, D., & Yang, H. (2022). Scheduling unrelated parallel machines with preventive maintenance and setup time: Multi-sub-colony artificial bee colony. Applied Soft Computing, 125. https://doi.org/10.1016/j.asoc.2022.109154

Lenstra, J. K., & Vakhania, N. (2023). On the complexity of scheduling unrelated parallel machines with limited preemptions. Operations Research Letters, 51(2), 187–189. https://doi.org/10.1016/j.orl.2023.02.004

Lin, D. Y., & Huang, T. Y. (2021). A hybrid metaheuristic for the unrelated parallel machine scheduling problem. Mathematics, 9(7). https://doi.org/10.3390/math9070768

Logendran, R., McDonell, B., & Smucker, B. (2007). Scheduling unrelated parallel machines with sequence-dependent setups. Computers and Operations Research, 34(11), 3420–3438. https://doi.org/10.1016/j.cor.2006.02.006

Maecker, S., Shen, L., & Mönch, L. (2023). Unrelated parallel machine scheduling with eligibility constraints and delivery times to minimize total weighted tardiness. Computers and Operations Research, 149. https://doi.org/10.1016/j.cor.2022.105999

Martins, M. S. E., Viegas, J. L., Coito, T., Firme, B., Costigliola, A., Figueiredo, J., Vieira, S. M., & Sousa, J. M. C. (2023). Minimizing total completion time in large-sized pharmaceutical quality control scheduling. Journal of Heuristics, 29(1), 177–206. https://doi.org/10.1007/s10732-023-09509-8

Martins, M. S. E., Viegas, J. L., Coito, T., Firme, B. M., Sousa, J. M. C., Figueredo, J., & Vieira, S. M. (2020). Reinforcement learning for dual-resource constrained scheduling. IFAC-PapersOnLine, 53, 10810–10815. https://doi.org/10.1016/j.ifacol.2020.12.2866

Mokotoff, E., Jimeno, L., & Guti~rrez, A. I. (2001). List Scheduling Algorithms to Minimize the Makespan on Identical Parallel Machines (Vol. 9, Issue 2).

Nelson, R. T. (1968). Dual-Resource Constrained Series Service Systems. Operations Research, 16(2), 324–341. https://doi.org/10.1287/opre.16.2.324

Pfund, M., Fowler, J. W., & Gupta, J. N. D. (2004). A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems. Journal of the Chinese Institute of Industrial Engineers, 21(3), 230–241. https://doi.org/10.1080/10170660409509404

Pinedo. (1995). Scheduling: Theory, Algorithms, and System.

Pulansari, F., & M., T. D. R. (2021). The Unrelated Parallel Machine Scheduling with a Dependent Time Setup using Ant Colony Optimization Algorithm. Jurnal Teknik Industri, 23(1), 65–74. https://doi.org/10.9744/jti.23.1.65-74

Sanati, H., Moslehi, G., & Reisi-Nafchi, M. (2023). Unrelated parallel machine energy-efficient scheduling considering sequence-dependent setup times and time-of-use electricity tariffs. EURO Journal on Computational Optimization, 11. https://doi.org/10.1016/j.ejco.2022.100052

Treleven, M. (1989). A review of the dual resource constrained system research. IIE Transactions (Institute of Industrial Engineers), 21(3), 279–287. https://doi.org/10.1080/07408178908966233

Van Den Akker, M., Hoogeveen, J. A., & Van Velde, S. L. D. E. (1999). Parallel machine scheduling by column generation ü. Operations Research, 47(6), 862–872. https://doi.org/10.1287/opre.47.6.862

Yang, B., & Geunes, J. (2007). A single resource scheduling problem with job-selection flexibility, tardiness costs and controllable processing times. Computers and Industrial Engineering, 53(3), 420–432. https://doi.org/10.1016/j.cie.2007.02.005

Zhu, X., Xu, J., Ge, J., Wang, Y., & Xie, Z. (2023). Multi-Task Multi-Agent Reinforcement Learning for Real-Time Scheduling of a Dual-Resource Flexible Job Shop with Robots. Processes, 11(1). https://doi.org/10.3390/pr11010267