More Web Proxy on the site http://driver.im/

research-article

Logic-based Benders decomposition with a partial assignment acceleration technique for avionics scheduling

Authors:

Elina RönnbergAuthors Info & Claims

Volume 146, Issue C

https://doi.org/10.1016/j.cor.2022.105916

Published: 01 October 2022 Publication History

Abstract

Pre-runtime scheduling of large-scale electronic systems, as those in modern aircraft, can be computationally challenging. In this paper, we study a distributed integrated modular avionic system of practical relevance where the scheduling includes to assign communication messages to time slots and to sequence tasks on modules. For this problem, the challenge is the huge number of tasks to be scheduled and the intricate interaction between the communication and task scheduling. We present a method based on Logic-Based Benders Decomposition (LBBD) to solve this problem. In a master problem, formulated as a mixed-integer program, communication messages are assigned to time slots and in a subproblem, formulated as a constraint program, tasks are scheduled.

Our LBBD scheme is accelerated by using cut strengthening, a subproblem relaxation, and components for preprocessing and initialisation of the scheme. The cut strengthening is of the kind that systematically investigates subsets of variables to include in the cut by solving additional subproblems. To further enhance the efficiency of the scheme, we propose a new strategy that extends cut strengthening to also try to construct feasible solutions by using information from solving the additional subproblems. Our computational evaluation is based on publicly available instances with up to 2530 messages and 54,731 tasks. It shows that our method outperforms previous methods for the problem with respect to both solution times and RAM usage. A further evaluation of the different components in the method shows that our new acceleration strategy is important to achieve these results.

Highlights

•

A MIP-CP hybrid LBBD method for an assignment and scheduling problem.

•

Acceleration technique extending cut strengthening to search for feasible solutions.

•

Solve relaxation subproblems to find stronger cuts.

•

Solve restriction subproblems to find feasible solutions.

•

Outperforms previous methods for industrially relevant avionics scheduling problem.

References

[1]

Atlihan M.K., Schrage L., Generalized filtering algorithms for infeasibility analysis, Comput. Oper. Res. 35 (5) (2008) 1446–1464,.

Digital Library

[2]

Bajestani M.A., Beck J.C., Scheduling an aircraft repair shop, in: Bacchus F., Domshlak C., Edelkamp S., Helmbert M. (Eds.), Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling, AAAI Press, 2011, pp. 10–17.

[3]

Benini L., Lombardi M., Mantovani M., Milano M., Ruggiero M., Multi-stage Benders decomposition for optimizing multicore architectures, in: Perron L., Trick M. (Eds.), CPAIOR 2008: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Springer-Verlag Berlin Heidelberg, 2008, pp. 36–50,.

[4]

Blikstad M., Karlsson E., Lööw T., Rönnberg E., An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system, Optim. Eng. 19 (4) (2018) 977–1004,.

[5]

Cambazard H., Hladik P.-E., Déplance A.-M., Jussien N., Trinquet Y., Decomposition and learning for a hard real time task allocation problem, in: Wallace M. (Ed.), Principles and Practice of Constraint Programming – CP 2004, Springer-Verlag Berlin Heidelberg, 2004, pp. 153–167,.

Digital Library

[6]

Chinneck J.W., Dravnieks E.W., Locating minimal infeasible constraint sets in linear programs, ORSA J. Comput. 3 (2) (1991) 157–168,.

[7]

Coban E., Hooker J.N., Single-facility scheduling by logic-based Benders decomposition, Ann. Oper. Res. 210 (1) (2013) 245–272,.

[8]

Codato G., Fischetti M., Combinatorial Benders’ cuts for mixed-integer linear programming, Oper. Res. 54 (4) (2006) 756–766,.

[9]

Emde S., Polten L., Gendreau M., Logic-based benders decomposition for scheduling a batching machine, Comput. Oper. Res. 113 (1) (2020),.

Digital Library

[10]

Emeretlis A., Theodoridis G., Alefragis P., Voros N., A logic-based Benders decomposition approach for mapping applications on heterogeneous multicore platforms, ACM Trans. Embed. Comput. Syst. 15 (1) (2016) 19:1–19:28,.

Digital Library

[11]

Gaska T., Watkin C., Chen Y., Integrated modular avionics – past, present, and future, IEEE Aerosp. Electron. Syst. Mag. 30 (9) (2015) 12–23,.

[12]

Gleixner A., Hendel G., Gamrath G., Achterberg T., Bastubbe M., Berthold T., Christophel P., Jarck K., Koch T., Linderoth J., Lübbecke M., Mittelmann H.D., Ozyurt D., Ralphs T.K., Salvagnin D., Shinano Y., MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library, Math. Prog. Comp. 13 (3) (2021) 443–490,.

[13]

GUROBI Optimizer, ., 2022.URL https://www.gurobi.com/products/gurobi-optimizer (Accessed: 17 May 2022).

[14]

He X., Yuan M., Gu Z., A hierarchical framework for design space exploration and optimization of TTP-based distributed embedded systems, IEEE Trans. Ind. Inf. 4 (4) (2008) 237–249,.

[15]

Hooker J.N., Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction, John Wiley & Sons, 2000,.

[16]

Hooker J.N., Planning and scheduling by logic-based Benders decomposition, Oper. Res. 55 (3) (2007) 588–602,.

Digital Library

[17]

Hooker J.N., Logic-based Benders decomposition for large-scale optimization, in: Velásquez-Bermúdez J.M., Khakifirooz M., Fathi M. (Eds.), Large Scale Optimization in Supply Chains and Smart Manufacturing: Theory and Applications, Springer International Publishing, 2019, pp. 1–26,.

[18]

Hooker J.N., Ottosson G., Logic-based Benders decomposition, Math. Program. 96 (1) (2003) 33–60,.

[19]

Junker, U., 2001. QuickXPlain: Conflict Detection for Arbitrary Constraint Propagation Algorithms. In: IJCAI01 Workshop on Modeling and Solving Problems with Constraints. CONS-1.

[20]

Junker U., QuickXPlain: Preferred explanations and relaxations for over-constrained problems, in: Cohn A.G. (Ed.), AAAI’04: Proceedings of the 19th National Conference on Artifical Intelligence, 2004, pp. 167–172.

[21]

Karlsson E., Rönnberg E., Strengthening of feasibility cuts in logic-based Benders decomposition, in: Stuckey P.J. (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2021, Springer International Publishing, 2021, pp. 45–61,.

Digital Library

[22]

Karlsson E., Rönnberg E., Instance dataset for a multiprocessor scheduling problem with multiple time windows and time lags: Similar instances with large differences in difficulty, 2022, Report.

[23]

Karlsson E., Rönnberg E., Stenberg A., Uppman H., A matheuristic approach to large-scale avionic scheduling, Ann. Oper. Res. 302 (2) (2021) 425–459,.

[24]

Kim H.-J., Hooker J.N., Solving fixed-charge network flow problems with a hybrid optimization and constraint programming approach, Ann. Oper. Res. 115 (1–4) (2002) 95–124,.

[25]

Laborie P., Rogerie J., Shaw P., Vilím P., IBM ILOG CP optimizer for scheduling, Constraints 23 (2) (2018) 210–250,.

Digital Library

[26]

Lam E., Gange G., Stuckey P.J., Van Hentenryck P., Dekker J.J., Nutmeg: a MIP and CP hybrid solver using branch-and-check, SN Oper. Res. Forum 1 (3) (2020) 22:1–22:27,.

[27]

Lindh E., Olsson K., Rönnberg E., Scheduling of an underground mine by combining logic-based Benders decomposition and a priority-based heuristic, in: De Causmaecker P., Özcan E., Vanden Berghe G. (Eds.), Accepted for Publication in the Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2022, 2022.

[28]

Lombardi M., Milano M., Optimal methods for resource allocation and scheduling: a cross-disciplinary survey, Constraints 17 (1) (2012) 51–85,.

Digital Library

[29]

Mittelmann H.D., The MIPLIB2017 benchmark instances, 2021, URL http://plato.asu.edu/ftp/milp.html (Accessed: 17 May 2022).

[30]

Parker M., Ryan J., Finding the minimum weight IIS cover of an infeasible system of linear inequalities, Ann. Math. Artif. Intell. 17 (1) (1996) 107–126,.

[31]

Rahmaniani R., Crainic T.G., Gendreau M., Rei W., The Benders decomposition algorithm: A literature review, European J. Oper. Res. 259 (3) (2017) 801–817,.

[32]

Raidl G.R., Decomposition based hybrid metaheuristics, Eur. J. Oper. Res. 244 (1) (2015) 66–76,. URL https://www.sciencedirect.com/science/article/pii/S0377221714009874.

[33]

Raidl G.R., Baumhauer T., Hu B., Boosting an exact logic-based Benders decomposition approach by variable neighborhood search, Electron. Notes Discrete Math. 47 (1) (2020) 149–156,.

[34]

Raidl G.R., Baumhauer T., Hu B., Speeding up logic-based Benders’ decomposition by a metaheuristic for a bi-level capacitated vehicle routing problem, in: Blesa M.J., Blum C., Voß S. (Eds.), Hybrid Metaheuristics: 9th International Workshop, HM 2014 Hamburg, Germany, June 11-13, 2014 Proceedings, Springer International Publishing Switzerland, 2021, pp. 183–197,.

[35]

Riedler M., Raidl G., Solving a selective dial-a-ride problem with logic-based Benders decomposition, Comput. Oper. Res. 96 (1) (2020) 30–54,.

[36]

Robati T., Gherbi A., El Kouhen A., Mullins J., Design and simulation of distributed IMA architectures using TTEthernet, J. Ambient Intell. Humaniz. Comput. 8 (3) (2017) 345–355,.

[37]

Saharidis G.K.D., Ierapetritou M.G., Improving benders decomposition using maximum feasible subsystem (MFS) cut generation strategy, Comput. Chem. Eng. 34 (8) (2010) 1237–1245,.

[38]

Sun D., Tang L., Baldacci R., A Benders decomposition-based framework for solving quay crane scheduling problems, Eur. J. Oper. Res. 273 (2) (2019) 504–515,.

[39]

Wang H., Niu W., A review of key technologies of the distributed integrated modular avionics system, Int. J. Wirel. Inf. Netw. 25 (3) (2018) 358–369,.

[40]

Xu J., Parnas D.L., Priority scheduling versus pre-run-time scheduling, Real-Time Syst. 18 (1) (2000) 7–23,.

[41]

Zhang M., Zhang N., Li H., Gu Z., A decomposition-based approach to optimization of TTP-based distributed embedded systems, J. Syst. Archit. 91 (1) (2018) 53–61,.

[42]

Zhou X., Xiong H., He F., Hybrid partition- and network-level scheduling design for distributed integrated modular avionics systems, Chin. J. Aeronaut. 33 (1) (2020) 308–323,.

Cited By

Varga JKarlsson ERaidl GRönnberg ELindsten FRodemann T(2023)Speeding Up Logic-Based Benders Decomposition by Strengthening Cuts with Graph Neural NetworksMachine Learning, Optimization, and Data Science10.1007/978-3-031-53969-5_3(24-38)Online publication date: 22-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-53969-5_3

Index Terms

Logic-based Benders decomposition with a partial assignment acceleration technique for avionics scheduling
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Index terms have been assigned to the content through auto-classification.

Recommendations

Stochastic Planning and Scheduling with Logic-Based Benders Decomposition
We apply logic-based Benders decomposition (LBBD) to two-stage stochastic planning and scheduling problems in which the second stage is a scheduling task. We solve the master problem with mixed integer/linear programming and the subproblem with constraint ...
Logic-based Benders decomposition for the preemptive flexible job-shop scheduling problem
Abstract
In this paper, we focus on exact methods to solve the preemptive flexible job-shop scheduling problem with makespan minimisation objective function. Mathematical and constraint programming models enable the resolution of this problem ...
Highlights
- The preemptive flexible job-shop scheduling problem is studied.
- We focus on ...
Planning and Scheduling by Logic-Based Benders Decomposition

We combine mixed-integer linear programming (MILP) and constraint programming (CP) to solve an important class of planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Operations Research

Computers and Operations Research Volume 146, Issue C

Oct 2022

429 pages

ISSN:0305-0548

Issue’s Table of Contents

The Author(s).

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 October 2022

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Varga JKarlsson ERaidl GRönnberg ELindsten FRodemann T(2023)Speeding Up Logic-Based Benders Decomposition by Strengthening Cuts with Graph Neural NetworksMachine Learning, Optimization, and Data Science10.1007/978-3-031-53969-5_3(24-38)Online publication date: 22-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-53969-5_3

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents