{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:07:42Z","timestamp":1760148462262,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T00:00:00Z","timestamp":1683504000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Universidad Nacional de Colombia"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>The open shop scheduling problem (OSSP) is one of the standard scheduling problems. It consists of scheduling jobs associated with a finite set of tasks developed by different machines. In this case, each machine processes at most one operation at a time, and the job processing order on the machines does not matter. The goal is to determine the completion times of the operations processed on the machines to minimize the largest job completion time, called Cmax. This paper proves that each OSSP has associated a path algebra called Brauer configuration algebra whose representation theory (particularly its dimension and the dimension of its center) can be given using the corresponding Cmax value. It has also been proved that the dimension of the centers of Brauer configuration algebras associated with OSSPs with minimal Cmax are congruent modulo the number of machines.<\/jats:p>","DOI":"10.3390\/computation11050094","type":"journal-article","created":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T02:28:08Z","timestamp":1683599288000},"page":"94","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Algebraic Approach to the Solutions of the Open Shop Scheduling Problem"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6812-5131","authenticated-orcid":false,"given":"Agust\u00edn Moreno","family":"Ca\u00f1adas","sequence":"first","affiliation":[{"name":"Departamento de Matem\u00e1ticas, Universidad Nacional de Colombia, Edificio Yu Takeuchi 404, Kra 30 No. 45-03, Bogot\u00e1 11001000, Colombia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3953-2381","authenticated-orcid":false,"given":"Odette M.","family":"Mendez","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1ticas, Universidad Nacional de Colombia, La Nubia, Manizales 170003, Colombia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5719-2854","authenticated-orcid":false,"given":"Juan-Carlos","family":"Ria\u00f1o-Rojas","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1ticas, Universidad Nacional de Colombia, La Nubia, Manizales 170003, Colombia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8547-5491","authenticated-orcid":false,"given":"Juan-David","family":"Hormaza","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1ticas, Universidad Nacional de Colombia, La Nubia, Manizales 170003, Colombia"}]}],"member":"1968","published-online":{"date-parts":[[2023,5,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/s10479-015-1934-1","article-title":"The representation of partially-concurrent open shop problems","volume":"252","author":"Grinshpoun","year":"2017","journal-title":"Ann. Oper. Res."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1057\/s41278-019-00122-w","article-title":"Practical approaches to chemical tanker scheduling in ports: A case study on the port of houston","volume":"21","author":"Cankaya","year":"2019","journal-title":"Marit. Econ. Logist."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1016\/j.ijpe.2007.09.016","article-title":"The endoscopy scheduling problem: A case study with two specialised operating rooms","volume":"120","author":"Fei","year":"2009","journal-title":"Int. J. Prod. Econ."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/j.ejor.2021.03.026","article-title":"Four decades of research on the open-shop scheduling problem to minimize the makespan","volume":"295","author":"Ahmadian","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","unstructured":"Woeginger, G.J. (March, January 28). The open shop scheduling problem. Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/321978.321985","article-title":"Open shop scheduling to minimize finish time","volume":"23","author":"Gonzalez","year":"1976","journal-title":"JACM"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0167-6377(95)00043-7","article-title":"Open shop, satellite communication and a theorem by Egerv\u00e1ry (1931)","volume":"18","author":"Martello","year":"1996","journal-title":"Oper. Res. Lett."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","article-title":"Sequencing and scheduling: Algorithms and complexity","volume":"4","author":"Lawler","year":"1993","journal-title":"Handbooks Oper. Res. Manag. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF01585871","article-title":"Makespan minimization in open shops: A polynomial time approximation scheme","volume":"82","author":"Sevastianov","year":"1998","journal-title":"Math. Program."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1287\/moor.8.1.100","article-title":"An algorithm for the open-shop problem","volume":"8","author":"Fiala","year":"1983","journal-title":"Math. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1287\/opre.42.1.189","article-title":"Scheduling Unit-Time Open Shops with Deadlines","volume":"42","author":"Tautenhahn","year":"1994","journal-title":"Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/0377-2217(93)90182-M","article-title":"Benchmarks for basic scheduling problems","volume":"64","author":"Taillard","year":"1993","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s00186-006-0127-8","article-title":"Complexity of shop-scheduling problems with fixed number of jobs: A survey","volume":"65","author":"Brucker","year":"2007","journal-title":"Math. Meth. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Dempster, M.A.H., Lenstra, J.K., and Rinnooy Kan, A.H.G. (1982). Deterministic and Stochastic Scheduling, Springer.","DOI":"10.1007\/978-94-009-7801-0"},{"key":"ref_15","unstructured":"Slowinski, R., and Weglarz, J. (1989). Advances in Project Scheduling, Elsevier."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/s10951-013-0356-7","article-title":"A cyclical search for the two machine flow shop and open shop to minimise finishing time","volume":"18","author":"Soper","year":"2015","journal-title":"J. Sched."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"5438","DOI":"10.1016\/j.eswa.2010.10.010","article-title":"A new base colony optimization algorithm with idle-time based filtering scheme for open shop-scheduling problems","volume":"38","author":"Huang","year":"2011","journal-title":"Expert Syst."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.dam.2017.04.031","article-title":"Open shop scheduling problems with conflict graphs","volume":"227","author":"Tellache","year":"2017","journal-title":"Discret. Appl. Math."},{"key":"ref_19","first-page":"83","article-title":"Using max-plus algebra in the flow shop scheduling","volume":"20","author":"Subiono","year":"2009","journal-title":"J. Technol. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2717","DOI":"10.3182\/20110828-6-IT-1002.03095","article-title":"Cyclic job shop problem and max-plus algebra","volume":"18","author":"Houssin","year":"2011","journal-title":"IFAC Proc. Vol."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Barman, J.M., Martinez, C., and Verma, S.C. (2018, January 10\u201313). Max-plus to solve the cyclic job shop problem with time lags. Proceedings of the 5th International Conference on Control, Decision and Information Technologies, Thessaloniki, Greece.","DOI":"10.1109\/CoDIT.2018.8394918"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"35","DOI":"10.17535\/crorr.2019.0004","article-title":"A max-plus algebra approach for generating a non-delay schedule","volume":"10","author":"Peperko","year":"2019","journal-title":"Croat. Oper. Res. Rev."},{"key":"ref_23","unstructured":"Bermanei, H.A. (2021). Thesis: Applications of Max-Plus Algebra to Scheduling, \u00c5bo Akademy University Press."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"81","DOI":"10.13189\/ms.2021.090201","article-title":"On application of max-plus algebra to synchronized discrete event system","volume":"9","author":"Aminu","year":"2021","journal-title":"Math. Stat."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Chang, J., Yu, D., Hu, Y., He, W., and Yu, H. (2022). Deep reinforcement learning for dynamic flexible job shop scheduling with random job arrival. Processes, 10.","DOI":"10.3390\/pr10040760"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Bermanei, H.A., B\u00f6ling, J.M., and H\u00f6gn\u00e4s, G. (2023). Modeling and scheduling of production systems by using max-plus algebra. Flex. Serv. Manuf. J., 1\u20132.","DOI":"10.1007\/s10696-023-09484-z"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Sitahong, A., Yuan, Y., Li, M., Ma, J., Ba, Z., and Lu, Y. (2023). Designing dispatching rules via novel genetic programming with feature selection in dynamic job shop scheduling. Processes, 11.","DOI":"10.21203\/rs.3.rs-2283624\/v1"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Carnia, E., Wilopo, R., Napitupulu, H., Anggriani, N., and Supriatna, A.K. (2023). Modified Kleene star algorithm using max-plus algebra and its application in the railroad scheduling graphical interface. Computation, 11.","DOI":"10.3390\/computation11010011"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1016\/j.bulsci.2017.06.001","article-title":"Brauer configuration algebras: A generalization of Brauer graph algebras","volume":"121","author":"Green","year":"2017","journal-title":"Bull. Sci. Math."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Assem, I., and Trepode, S. (2018). Homological Methods, Representation Theory, and Cluster Algebras, CRM Short Courses, Springer.","DOI":"10.1007\/978-3-319-74585-5"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Ca\u00f1adas, A.M., Ballester-Bolinches, A., and Gaviria, I.D.M. (2022). Solutions of the Yang-Baxter equation arising from Brauer configuration algebras. Computation, 11.","DOI":"10.3390\/computation11010002"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Ca\u00f1adas, A.M., Rios, G.B., and Robinson-Julian, S. (2022). Snake graphs arising from groves with an application in coding theory. Computation, 10.","DOI":"10.3390\/computation10070124"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"23485","DOI":"10.1007\/s11042-020-10239-3","article-title":"Brauer configuration algebras for multimedia based cryptography and security applications","volume":"80","author":"Angarita","year":"2021","journal-title":"Multimed. Tools Appl."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Agudelo, N., Ca\u00f1adas, A.M., Gaviria, I.D.M., and Espinosa, P.F.F. (2021). {0,1}-Brauer configuration algebras and their applications in the graph energy theory. Mathematics, 9.","DOI":"10.3390\/math9233042"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.jalgebra.2018.06.002","article-title":"The dimension of the center of a Brauer configuration algebra","volume":"510","author":"Sierra","year":"2018","journal-title":"J. Algebra"},{"key":"ref_36","unstructured":"Calderon, J. (2020). Analyzing Necessity and Sufficiency Optimization Criteria to Study the Possibility of Generalizing Them to Topological Groups. [Master\u2019s Thesis, National University of Colombia]. (In Spanish)."},{"key":"ref_37","unstructured":"Andrews, G.E. (2010). The Theory of Partitions, Cambridge University Press."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/5\/94\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:31:43Z","timestamp":1760124703000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/5\/94"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,8]]},"references-count":37,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2023,5]]}},"alternative-id":["computation11050094"],"URL":"https:\/\/doi.org\/10.3390\/computation11050094","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2023,5,8]]}}}