A New Approach to Solve the Software Project Scheduling Problem Based on Max–Min Ant System | SpringerLink
Skip to main content
Springer Nature Link
Log in

A New Approach to Solve the Software Project Scheduling Problem Based on Max–Min Ant System

  • Conference paper
  • First Online:
Modern Trends and Techniques in Computer Science

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 285))

  • 955 Accesses

Abstract

This paper presents a new approach to solve the Software Project Scheduling Problem. This problem is NP-hard and consists in finding a worker-task schedule that minimizes cost and duration for the whole project, so that task precedence and resource constraints are satisfied. Such a problem is solved with an Ant Colony Optimization algorithm by using the Max–Min Ant System and the Hyper-Cube framework. We illustrate experimental results and compare with other techniques demonstrating the feasibility and robustness of the approach, while reaching competitive solutions.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 22879
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 28599
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    http://tracer.lcc.uma.es/problems/psp/generator.html

References

  1. Abdallah, H., Emara, H.M., Dorrah, H.T., Bahgat, A.: Using ant colony optimization algorithm for solving project management problems. Expert Syst. Appl. 36(6), 10004–10015 (2009)

    Article  Google Scholar 

  2. Alba, E., Chicano, F.: Software project management with gas. Inf. Sci. 177(11), 2380–2401 (2007) (in press)

    Google Scholar 

  3. Barreto, A., Barros, MdO, Werner, C.M.L.: Staffing a software project: a constraint satisfaction and optimization-based approach. Comput. Oper. Res. 35(10), 3073–3089 (2008)

    Article  MATH  Google Scholar 

  4. Blum, C., Dorigo, M.: The hyper-cube framework for ant colony optimization. Syst. Man Cybern. Part B Cybern. IEEE Trans. 34(2), 1161–1172 (2004)

    Article  Google Scholar 

  5. Chang, C.K., yi Jiang, H., Di, Y., Zhu, D., Ge, Y.: Time-line based model for software project scheduling with genetic algorithms. Inf. Softw. Technol. 50(11), 1142–1154 (2008)

    Article  Google Scholar 

  6. Chen, W., Zhang, J.: Ant colony optimization for software project scheduling and staffing with an event-based scheduler. Softw. Eng. IEEE Trans. 39(1), 1–17 (2013)

    Article  MATH  Google Scholar 

  7. Crawford, B., Soto, R., Castro, C., Monfroy, E.: Extensible cp-based autonomous search. In: Proceedings of HCI International, vol. 173 of CCIS, pp. 561–565. Springer (2011)

    Google Scholar 

  8. Crawford, B., Soto, R., Johnson, F., Monfroy, E.: Ants can schedule software projects. In: Stephanidis, C. (ed.) HCI International 2013—Posters Extended Abstracts, volume 373 of Communications in Computer and Information Science, pp. 635–639. Springer, Berlin (2013)

    Google Scholar 

  9. Crawford, B., Soto, R., Monfroy, E., Palma, W., Castro, C., Paredes, F.: Parameter tuning of a choice-function based hyperheuristic using particle swarm optimization. Expert Syst. Appl. 40(5), 1690–1695 (2013)

    Article  Google Scholar 

  10. Dorigo, M. Di Caro, G.: Ant colony optimization: a new meta-heuristic. In: Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, vol. 2, p. 1477 (1999)

    Google Scholar 

  11. Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)

    Google Scholar 

  12. Dorigo, M., Stutzle, T.: Ant Colony Optimization. MIT Press, USA (2004)

    Book  MATH  Google Scholar 

  13. Johnson, F., Crawford, B., Palma, W.: Hypercube framework for ACO applied to timetabling. In: IFIP AI, pp. 237–246 (2006)

    Google Scholar 

  14. Liao, T.W., Egbelu, P., Sarker, B., Leu, S.: Metaheuristics for project and construction management a state-of-the-art review. Autom. Constr. 20(5), 491–505 (2011)

    Article  Google Scholar 

  15. Monfroy, E., Castro, C., Crawford, B., Soto, R., Paredes, F., Figueroa, C.: A reactive and hybrid constraint solver. J. Exp. Theor. Artif. Intell. 25(1), 1–22 (2013)

    Article  Google Scholar 

  16. Ozdamar, L., Ulusoy, G.: A survey on the resource-constrained project scheduling problem. IIE Trans. 27(5), 574–586 (1995)

    Article  Google Scholar 

  17. Stutzle, T., Hoos, H.H.: Maxmin ant system. Future Gener. Comput. Syst. 16(8), 889–914 (2000)

    Article  Google Scholar 

  18. Xiao, J., Ao, X.T., Tang, Y.: Solving software project scheduling problems with ant colony optimization. Comput. Oper. Res. 40(1), 33–46 (2013)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Pontificia Universidad Católica de Valparaíso, Valparaíso, Chile

    Broderick Crawford, Ricardo Soto & Franklin Johnson

  2. Universidad de Playa Ancha, Valparaíso, Chile

    Franklin Johnson

  3. Universidad Finis Terrae, Santiago, Chile

    Broderick Crawford

  4. Universidad Autónoma de Chile, Temuco, Chile

    Ricardo Soto

  5. CNRS, LINA, Université de Nantes, Nantes, France

    Eric Monfroy

  6. Universidad Diego Portales, Santiago, Chile

    Fernando Paredes

Authors
  1. Broderick Crawford
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ricardo Soto
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Franklin Johnson
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Eric Monfroy
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Fernando Paredes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Franklin Johnson .

Editor information

Editors and Affiliations

  1. Faculty of Applied Informatics, Tomas Bata University in Zlín, Zlín, Czech Republic

    Radek Silhavy

  2. Faculty of Applied Informatics, Tomas Bata University in Zlín, Zlín, Czech Republic

    Roman Senkerik

  3. Faculty of Applied Informatics, Tomas Bata University in Zlín, Zlín, Czech Republic

    Zuzana Kominkova Oplatkova

  4. Faculty of Applied Informatics, Tomas Bata University in Zlín, Zlín, Czech Republic

    Petr Silhavy

  5. Faculty of Applied Informatics, Tomas Bata University in Zlín, Zlín, Czech Republic

    Zdenka Prokopova

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this paper

Cite this paper

Crawford, B., Soto, R., Johnson, F., Monfroy, E., Paredes, F. (2014). A New Approach to Solve the Software Project Scheduling Problem Based on Max–Min Ant System. In: Silhavy, R., Senkerik, R., Oplatkova, Z., Silhavy, P., Prokopova, Z. (eds) Modern Trends and Techniques in Computer Science. Advances in Intelligent Systems and Computing, vol 285. Springer, Cham. https://doi.org/10.1007/978-3-319-06740-7_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-06740-7_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-06739-1

  • Online ISBN: 978-3-319-06740-7

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation