- -

Evaluation and comparison of integer programming solvers for hard real-time scheduling

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

Evaluation and comparison of integer programming solvers for hard real-time scheduling

Mostrar el registro sencillo del ítem

Ficheros en el ítem

dc.contributor.author Guasque Ortega, Ana es_ES
dc.contributor.author Balbastre, Patricia es_ES
dc.date.accessioned 2023-10-26T18:01:44Z
dc.date.available 2023-10-26T18:01:44Z
dc.date.issued 2022-10 es_ES
dc.identifier.issn 0916-8532 es_ES
dc.identifier.uri http://hdl.handle.net/10251/198867
dc.description.abstract [EN] In order to obtain a feasible schedule of a hard real-time system, heuristic based techniques are the solution of choice. In the last few years, optimization solvers have gained attention from research communities due to their capability of handling large number of constraints. Recently, some works have used integer linear programming (ILP) for solving mono processor scheduling of real-time systems. In fact, ILP is commonly used for static scheduling of multiprocessor systems. However, two main solvers are used to solve the problem indistinctly. But, which one is the best for obtaining a schedulable system for hard real-time systems? This paper makes a comparison of two well-known optimization software packages (CPLEX and GUROBI) for the problem of finding a feasible schedule on monoprocessor hard real-time systems. es_ES
dc.description.sponsorship This work was supported under Grant PLEC2021-007609 funded by MCIN/AEI/10.13039/501100011033 and by the "European Union NextGeneration EU/PRTR" es_ES
dc.language Inglés es_ES
dc.publisher Institute of Electronics, Information and Communications Engineers es_ES
dc.relation.ispartof IEICE Transactions on Information and Systems es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Integer linear programming es_ES
dc.subject Hard real-time scheduling es_ES
dc.subject Optimization es_ES
dc.subject.classification ARQUITECTURA Y TECNOLOGIA DE COMPUTADORES es_ES
dc.title Evaluation and comparison of integer programming solvers for hard real-time scheduling es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1587/transinf.2022EDP7073 es_ES
dc.relation.projectID info:eu-repo/grantAgreement/AEI//PLEC2021-007609//MOVILIDAD EN LA CIUDAD DEL FUTURO. PREPARAR A LAS CIUDADES PARA LA NUEVA MOVILIDAD 2030 A TRAVÉS DE LAS 4 UNIVERSIDADES POLITÉCNICAS ESPAÑOLAS/ es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Escuela Técnica Superior de Ingenieros Industriales - Escola Tècnica Superior d'Enginyers Industrials es_ES
dc.description.bibliographicCitation Guasque Ortega, A.; Balbastre, P. (2022). Evaluation and comparison of integer programming solvers for hard real-time scheduling. IEICE Transactions on Information and Systems. E105-D(10):1726-1733. https://doi.org/10.1587/transinf.2022EDP7073 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion http://dx.doi.org/10.1587/transinf.2022EDP7073 es_ES
dc.description.upvformatpinicio 1726 es_ES
dc.description.upvformatpfin 1733 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume E105-D es_ES
dc.description.issue 10 es_ES
dc.relation.pasarela S\472724 es_ES
dc.contributor.funder AGENCIA ESTATAL DE INVESTIGACION es_ES
dc.contributor.funder European Regional Development Fund es_ES
dc.contributor.funder Universitat Politècnica de València es_ES
dc.description.references [1] R. Anand, D. Aggarwal, and V. Kumar, “A comparative analysis of optimization solvers,” Journal of Statistics and Management Systems, vol.20, no.4, pp.623-635, 2017. 10.1080/09720510.2017.1395182 es_ES
dc.description.references [2] L.M. Hvattum, A. LÞkketangen, and F. Glover, “Comparisons of commercial mip solvers and an adaptive memory (tabu search) procedure for a class of 0-1 integer programming problems,” Algorithmic Operations Research, vol.7, 2012. es_ES
dc.description.references [3] P.G. Saghand and H. Charkhgard, “Exact solution approaches for integer linear generalized maximum multiplicative programs through the lens of multi-objective optimization,” Computers and Operations Research, vol.137, p.105549, 2022. 10.1016/j.cor.2021.105549 es_ES
dc.description.references [4] R. Linfati, G. Gatica, and J.W. Escobar, “A mathematical model for scheduling and assignment of customers in hospital waste collection routes,” Applied Sciences, vol.11, no.22, 2021. 10.3390/app112210557 es_ES
dc.description.references [5] G. Liuzzi, M. Locatelli, V. Piccialli, and S. Rass, “Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems,” Computational Optimization and Applications, vol.79, no.3, pp.561-599, July 2021. 10.1007/s10589-021-00282-7 es_ES
dc.description.references [6] C. Flores-Fonseca, R. Linfati, and J.W. Escobar, “Exact algorithms for production planning in mining considering the use of stockpiles and sequencing of power shovels in open-pit mines,” Operational Research, vol.22, no.3, pp.2529-2553, 2022. 10.1007/s12351-020-00618-x es_ES
dc.description.references [7] M. González, J.J. López-Espın, and J. Aparicio, “A parallel algorithm for matheuristics: A comparison of optimization solvers,” Electronics, vol.9, no.9, 2020. 10.3390/electronics9091541 es_ES
dc.description.references [8] A.P. Punnen, P. Pandey, and M. Friesen, “Representations of quadratic combinatorial optimization problems: A case study using quadratic set covering and quadratic knapsack problems,” Computers and Operations Research, vol.112, p.104769, 2019. 10.1016/j.cor.2019.104769 es_ES
dc.description.references [9] J. Jablonský, “Recent optimization packages and their comparison,” Hradec Economic Days, vol.7, no.1, 2017. es_ES
dc.description.references [10] S. Baruah, “Feasibility analysis of preemptive real-time systems upon heterogeneous multiprocessor platforms,” 25th IEEE International Real-Time Systems Symposium, pp.37-46, 2004. 10.1109/real.2004.20 es_ES
dc.description.references [11] I. Hong, D. Kirovski, G. Qu, M. Potkonjak, and M.B. Srivastava, “Power optimization of variable-voltage core-based systems,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol.18, no.12, pp.1702-1714, 1999. 10.1109/43.811318 es_ES
dc.description.references [12] V.A. Nguyen, D. Hardy, and I. Puaut, “Cache-conscious off-line real-time scheduling for multi-core platforms: algorithms and implementation,” Real-Time Systems, vol.55, no.4, pp.810-849, 2019. 10.1007/s11241-019-09333-z es_ES
dc.description.references [13] Y. Sun and M.D. Natale, “Weakly hard schedulability analysis for fixed priority scheduling of periodic real-time tasks,” ACM Trans. Embed. Comput. Syst., vol.16, no.5s, pp.1-19, 2017. 10.1145/3126497 es_ES
dc.description.references [14] T. Fleming and A. Burns, “Investigating mixed criticality cyclic executive schedule generation,” Proc. Workshop on Mixed Criticality (WMC), 2015. es_ES
dc.description.references [15] W. Zhang, Y. Hu, H. He, Y. Liu, and A. Chen, “Linear and dynamic programming algorithms for real-time task scheduling with task duplication,” The Journal of Supercomputing, vol.75, no.2, pp.494-509, 2019. 10.1007/s11227-017-2076-9 es_ES
dc.description.references [16] B. Rouxel, S. Derrien, and I. Puaut, “Tightening contention delays while scheduling parallel applications on multi-core architectures,” ACM Trans. Embed. Comput. Syst., vol.16, no.5s, pp.1-20, 2017. 10.1145/3126496 es_ES
dc.description.references [17] A. Azim, G. Carvajal, R. Pellizzoni, and S. Fischmeister, “Generation of communication schedules for multi-mode distributed real-time applications,” Proceedings of Design, Automation and Test in Europe (DATE), Grenoble, France, pp.1-6, March 2014. 10.7873/date2014.306 es_ES
dc.description.references [18] I.I. Cplex, “V12. 1: User's manual for cplex,” International Business Machines Corporation, 2019. es_ES
dc.description.references [19] M. Fischetti, F. Glover, and A. Lodi, “The feasibility pump,” Mathematical Programming, vol.104, no.1, pp.91-104, Sept. 2005. 10.1007/s10107-004-0570-3 es_ES
dc.description.references [20] Gurobi, Gurobi optimizer reference manual, Gurobi Optimization, 2019. es_ES
dc.description.references [21] P.K. Harter, Jr., “Response times in level-structured systems,” ACM Trans. Comput. Syst., vol.5, no.3, pp.232-248, Aug. 1987. 10.1145/24068.24069 es_ES
dc.description.references [22] M. Joseph and P. Pandya, “Finding response times in a real-time system,” The Computer Journal, vol.29, no.5, pp.390-395, 1986. 10.1093/comjnl/29.5.390 es_ES
dc.description.references [23] C.L. Liu and J.W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” J. ACM, vol.20, no.1, pp.46-61, Jan. 1973. 10.1145/321738.321743 es_ES
dc.description.references [24] P. Balbastre, I. Ripoll, J. Vidal, and A. Crespo, “A task model to reduce control delays,” Real-Time Syst., vol.27, no.3, pp.215-236, 2004. 10.1023/b:time.0000029049.50766.fa es_ES
dc.description.references [25] E. Bini and G.C. Buttazzo, “Measuring the performance of schedulability tests,” Real-Time Systems, vol.30, pp.129-154, 2005. 10.1007/s11241-005-0507-9 es_ES
dc.description.references [26] V. Brocal, P. Balbastre, R. Ballester, and I. Ripoll, “Task period selection to minimize hyperperiod,” ETFA2011, pp.1-4, 2011. 10.1109/etfa.2011.6059178 es_ES
upv.costeAPC 1000 es_ES


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem