Skip to main content
SpringerLink
Log in

A mixed integer linear programming model for reliability optimisation in the component deployment problem

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

Component deployment is a combinatorial optimisation problem in software engineering that aims at finding the best allocation of software components to hardware resources in order to optimise quality attributes, such as reliability. The problem is often constrained because of the limited hardware resources, and the communication network, which may connect only certain resources. Owing to the non-linear nature of the reliability function, current optimisation methods have focused mainly on heuristic or metaheuristic algorithms. These are approximate methods, which find near-optimal solutions in a reasonable amount of time. In this paper, we present a mixed integer linear programming (MILP) formulation of the component deployment problem. We design a set of experiments where we compare the MILP solver to methods previously used to solve this problem. Results show that the MILP solver is efficient in finding feasible solutions even where other methods fail, or prove infeasibility where feasible solutions do not exist.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3

Similar content being viewed by others

References

  • Afzal W and Torkar R (2011). On the application of genetic programming for software engineering predictive modeling: A systematic review. Expert Systems with Applications 38(9): 11984–11997.

    Article  Google Scholar 

  • Aleti A (2015). Designing automotive embedded systems with adaptive genetic algorithms. Automated Software Engineering 22(2): 199–240.

    Article  Google Scholar 

  • Aleti A, Buhnova B, Grunske L, Koziolek A and Meedeniya I (2013). Software architecture optimization methods: A systematic literature review. IEEE Transactions on Software Engineering 39(5): 658–683.

    Article  Google Scholar 

  • Aleti A and Grunske L (2015). Test data generation with a kalman filter-based adaptive genetic algorithm. Journal of Systems and Software 103(Special issue): 343–352.

    Article  Google Scholar 

  • Aleti A, Grunske L, Meedeniya I and Moser I (2009). Let the ants deploy your software—an ACO based deployment optimisation strategy. Proceedings of the 2009 IEEE/ACM International Conference on Automated Software Engineering (ASE’09). IEEE Computer Society, Washington DC, pp 505–509.

  • Aleti A and Meedeniya I (2011). Component deployment optimisation with bayesian learning. Proceedings of the 14th International ACM Sigsoft Symposium on Component Based Software Engineering. ACM, New York, NY, pp 11–20.

  • Assayad I, Girault A and Kalla H (2004). A bi-criteria scheduling heuristic for distributed embedded systems under reliability and real-time constraints. 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’04). IEEE Computer Society, Los Alamitos, CA, pp 347–356.

  • Bartz-Beielstein T, Lasarczyk C and Preuss M (2005). Sequential parameter optimization. 2005 IEEE Congress on Evolutionary Computation. IEEE, Scotland, UK, pp, 773–780.

  • Bowen NS, Nikolaou CN and Ghafoor A (1992). On the assignment problem of arbitrary process systems to heterogeneous distributed computer systems. Computers, IEEE Transactions on 41(3): 257–273.

    Article  Google Scholar 

  • Calinescu R and Kwiatkowska M (2009). Using quantitative analysis to implement autonomic IT systems. Proceedings of the 31st International Conference on Software Engineering (ICSE’09). IEEE Computer Society, Washington DC, pp 100–110.

  • Cheung RC (1980). A user-oriented software reliability model. IEEE Transactions on Software Engineering 6(2): 118–125.

    Article  Google Scholar 

  • Deb K (2001). Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons: New York.

    Google Scholar 

  • Deb K, Pratap A, Agarwal S and Meyarivan T (2000). A fast elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2): 182–197.

    Article  Google Scholar 

  • Dimov A and Punnekkat S (2005). On the estimation of software reliability of component-based dependable distributed systems. In: Reussner R, Mayer J, Stafford JA, Over-hage S, Becker S and Schroeder PJ (eds). Quality of Software Architectures and Software Quality, Lecture Notes in Computer Science. Vol. 3712. Springer: Berlin, Heidelberg, Germany, pp 171–187.

    Chapter  Google Scholar 

  • Dorigo M and Stűtzle T (2004). Ant Colony Optimization. MIT Press: Cambridge, MA.

    Google Scholar 

  • Ernst A, Jiang H and Krishnamoorthy M (2006). Exact solutions to task allocation problems. Management Science 52(10): 1634–1646.

    Article  Google Scholar 

  • Fonseca CM and Fleming PJ (1993). Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. Proceedings of the 5th International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Francisco, CA, pp 416–423.

  • Fredriksson J, Sandstrom K and Akerholm M (2005). Optimizing resource usage in component-based real-time systems. Component-Based Software Engineering, 8th International Symposium, LNCS, Vol. 3489. Springer, Berlin, Heidelberg, pp 49–65.

  • Gokhale SS, Philip T, Marinos PN and Trivedi KS (1996). Unification of finite failure non-homogeneous poisson process models through test coverage. 2013 IEEE 24th International Symposium on Software Reliability Engineering (ISSRE), IEEE Computer Society, Los Alamitos, CA, 299–307.

  • Goseva-Popstojanova K and Trivedi KS (2001). Architecture-based approach to reliability assessment of software systems. Performance Evaluation 45(2–3): 179–204.

    Article  Google Scholar 

  • Guntsch M and Middendorf M (2003). Solving multi-criteria optimization problems with population-based ACO. Evolutionary Multi-Criterion Optimization. Second International Conference, EMO 2003. Springer, Berlin, Heidelberg, pp 464–478.

  • Hadj-Alouane AB, Bean J and Murty K (1999). A hybrid genetic/optimisation algorithm for a task allocation problem. Journal of Scheduling 2(4): 189–201.

    Article  Google Scholar 

  • Hamlet D, Mason D and Woit D (2001). Theory of software reliability based on components. Proceedings ofthe 23rd International Conference on Software Engineering (ICSE ‘01), IEEE Computer Society, Toronto, Canada, pp 361–370.

  • Harman M (2007a). The current state and future of search based software engineering. In: Lionel C. Briand, Alexander L. Wolf (eds). International Conference on Software Engineering, ISCE 2007, Workshop on the Future of Software Engineering (FOSE’07), IEEE Computer Society, Washington, DC, 342–357.

  • Harman M (2007b). Search based software engineering for program comprehension. Proceedings of the 15th International Conference on Program Comprehension (ICPC’07). IEEE Computer Society, Washington DC, pp 3–13.

  • Harris I (2013). Embedded software for automotive applications. In: Oshana R and Kraeling M (eds). Software Engineering for Embedded Systems. Newnes, Oxford, pp 767–816.

    Chapter  Google Scholar 

  • Heydarnoori A and Mavaddat F (2006). Reliable deployment of component-based applications into distributed environments. 2014 11th International Conference on Information Technology: New Generations. IEEE Computer Society, Los Alamitos, CA, pp 52–57.

  • Kartik S and Murthy CSR (1997). Task allocation algorithms for maximizing reliability of distributed computing systems. Computers, IEEE Transactions on 46(6): 719–724.

    Article  Google Scholar 

  • Krishnamurthy S and Mathur AP (1997). On the estimation of reliability of a software system using reliabilities of its components. Proceedings of the Eighth International Symposium on Software Reliability Engineering, pp 146–155.

  • Kubat P (1989). Assessing reliability of modular software. Operations Research Letters 8(1): 35–41.

    Article  Google Scholar 

  • Kumar R, Izui K, Yoshimura M and Nishiwaki S (2009). Optimal multilevel redundancy allocation in series and series-parallel systems. Computers & Industrial Engineering 57(1): 169–180.

    Article  Google Scholar 

  • Leen G and Heffernan D (2002). Expanding automotive electronic systems. IEEE Computer 35(1): 88–93.

    Article  Google Scholar 

  • Liang Y-C and Smith AE (1999). An ant system approach to redundancy allocation. Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, Vol. 2. pp 1478–1484.

  • Lukasiewycz M, Glass M, Haubelt C and Teich J (2008). Efficient symbolic multi-objective design space exploration. Proceedings of the 2008 Asia and South Pacific Design Automation Conference (ASP-DAC 2008). IEEE Computer Society, Los Alamitos, CA, pp 691–696.

  • Mantere T and Alander JT (2005). Evolutionary software engineering, a review. Applied Soft Computing 5(3): 315–331.

    Article  Google Scholar 

  • Marriott K and Stuckey P (1998). Programming With Constraints. MIT Press: Cambridge, MA.

    Google Scholar 

  • Martens A and Koziolek H (2009). Automatic, model-based software performance improvement for component-based software designs. Electronic Notes in Theoretical Computer Science 253(1): 77–93.

    Article  Google Scholar 

  • McMinn P (2004). Search-based software test data generation: A survey. Softw. Test, Verif. Reliab 14(2): 105–156.

    Article  Google Scholar 

  • Medvidovic N and Malek S (2007). Software deployment architecture and quality-of-service in pervasive environments. International Workshop on the Engineering of Software Services for Pervasive Environements: In Conjunction with the 6th ESEC/FSE Joint Meeting (ESSPE’07). ACM, New York, NY, pp 47–51.

  • Meedeniya I, Aleti A, Avazpour I and Amin A (2012). Robust archeopterix: Architecture optimization of embedded systems under uncertainty. Software Engineering for Embedded Systems (SEES), 2012 2nd International Workshop on. 23–29 doi: 10.1109/SEES.2012.6225486.

  • Meedeniya I, Bühnova B, Aleti A and Grunske L (2011). Reliability-driven deployment optimization for embedded systems. Journal of Systems and Software 84(5): 835–846.

    Article  Google Scholar 

  • Mikic-Rakic M, Malek S, Beckman N and Medvidovic N (2004). A tailorable environment for assessing the quality of deployment architectures in highly distributed settings. International Working Conference on Component Deployment (CD’04), LNCS, vol. 3083. Springer, Berlin, Heidelberg, 1–17.

  • Moser I and Montgomery J (2011). Population-ACO for the automotive deployment problem. Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO ‘11), ACM, New York, 777–784.

  • Moser I and Mostaghim S (2010). The automotive deployment problem: A practical application for constrained multiobjective evolutionary optimisation. 2010 IEEE Congress on Evolutionary Computation (CEC). pp 1–8.

  • Papadopoulos Y and Grante C (2005). Evolving car designs using model-based automated safety analysis and optimisation techniques. Journal of Systems and Software 76(1): 77–89.

    Article  Google Scholar 

  • Reussner R, Schmidt HW and Poernomo I (2003). Reliability prediction for component-based software architectures. Journal of Systems and Software 66(3): 241–252.

    Article  Google Scholar 

  • Sharma VS, Jalote P and Trivedi KS (2005). Evaluating performance attributes of layered software architecture. Component-Based Software Engineering, 8th International Symposium (CBSE’05), LNCS, vol. 3489. Springer, Berlin, Heidelberg, pp 66–81.

  • Sheikhalishahi M, Ebrahimipour V, Shiri H, Zaman H and Jeihoonian M (2013). A hybrid gapso approach for reliability optimization in redundancy allocation problem. The International Journal of Advanced Manufacturing Technology 68(1–4): 317–338.

    Article  Google Scholar 

  • Singh H, Cortellessa V, Cukic B, Gunel E and Bharadwaj V (2001). A bayesian approach to reliability prediction and assessment of component based systems. Proceedings of the 12th International Symposium of Software Reliability Engineering (ISSRE’01). IEEE Computer Society, Washington DC, pp 12–21.

  • Thiruvady D, Moser I, Aleti A and Nazari A (2014). Constraint programming and ant colony system for the component deployment problem. Procedia Computer Science 29: 1937–1947, http://www.sciencedirect.com/science/article/pii/S187705091400355X.

    Article  Google Scholar 

  • Zhang Y, Finkelstein A and Harman M (2008). Search based requirements optimisation: Existing work and challenges. In: Paech B and Rolland C (eds). Requirements Engineering: Foundation for Software Quality, Springer, Berlin, Heidelberg, pp 88–94.

Download references

Acknowledgements

The authors gratefully acknowledge the constructive comments and helpful feedback from the anonymous reviewers, which have improved the quality of this work. This research was supported under Australian Research Council’s Discovery Projects funding scheme, project number DE 140100017.

Author information

Authors and Affiliations

  1. CSIRO Computational Informatics, Victoria, Australia

    Asef Nazari & Dhananjay Thiruvady

  2. Bayesian Intelligence, Victoria, Australia

    Dhananjay Thiruvady

  3. Monash University, Victoria, Australia

    Aldeida Aleti

  4. Swinburne University of Technology, Victoria, Australia

    Irene Moser

Authors
  1. Asef Nazari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dhananjay Thiruvady
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Aldeida Aleti
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Irene Moser
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nazari, A., Thiruvady, D., Aleti, A. et al. A mixed integer linear programming model for reliability optimisation in the component deployment problem. J Oper Res Soc 67, 1050–1060 (2016). https://doi.org/10.1057/jors.2015.119

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2015.119

Keywords

Search

Navigation