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

research-article

Evolutionary algorithms for the project scheduling problem: runtime analysis and improved design

Authors:

Leandro L. Minku,

Xin YaoAuthors Info & Claims

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

Pages 1221 - 1228

https://doi.org/10.1145/2330163.2330332

Published: 07 July 2012 Publication History

Abstract

Even though genetic algorithms (GAs) have been used for solving the project scheduling problem (PSP), it is not well understood which problem characteristics make it difficult/easy for GAs. We present the first runtime analysis for the PSP, revealing what problem features can make PSP easy or hard. This allows to assess the performance of GAs and to make informed design choices. Our theory has inspired a new evolutionary design, including normalisation of employees' dedication for different tasks to eliminate the problem of exceeding their maximum dedication. Theoretical and empirical results show that our design is very effective in terms of hit rate and solution quality.

References

[1]

A. Agresti and B. Coull. Approximate is better than "exact" for interval estimation of binomial proportions. The American Statistician, 52:119--126, 1998.

[2]

E. Alba and J. F. Chicano. Software project management with GAs. Information Sciences, 177:2380--2401, 2007.

Digital Library

[3]

D. Barrero, B. Castano, M. R-Moreno, and D. Camacho. Statistical distribution of generation-to-success in GP: Application to model accumulated success probability. In EuroDP '11, pages 155--166. Springer, 2011.

Digital Library

[4]

C. K. Chang, M. J. Christensen, and T. Zhang. Genetic algorithms for project management. Annals of Software Engineering, 11:107--139, 2001.

Digital Library

[5]

C. K. Chang, H. Jiang, Y. Di, D. Zhu, and Y. Ge. Time-line based model for software project scheduling with genetic algorithms. Information and Software Technology, 50(11):1142 -- 1154, 2008.

Digital Library

[6]

C. Chao. SPMNET: A New Methodology for Software Management. PhD thesis, The University of Illinois at Chicago, 1995.

[7]

J. Demsar. Statistical comparisons of classifiers over multiple data sets. JMLR, 7:1--30, 2006.

Digital Library

[8]

B. Doerr, T. Jansen, D. Sudholt, C. Winzen, and C. Zarges. Optimizing monotone functions can be difficult. In PPSN '10, pages 42--51. Springer, 2010.

Digital Library

[9]

H. Hoos and T. Stützle. Local search algorithms for SAT: An empirical evaluation. Journal of Automated Reasoning, 24(4):421--481, 2000.

Digital Library

[10]

D. Johannsen. Random Combinatorial Structures and Randomized Search Heuristics. PhD thesis, Universität des Saarlandes, Saarbrücken, Germany and the Max-Planck-Institut für Informatik, 2010.

[11]

P. Kapur, A. Ngo-The, G. Ruhe, and A. Smith. Optimized staffing for product releases and its application at Chartwell Technology. Journal of Software Maintenance and Evolution: Research and Practice, 20(5):365--386, 2008.

Digital Library

[12]

M. Lukasiewycz, M. Glaß, F. Reimann, and J. Teich. Opt4J - A Modular Framework for Meta-heuristic Optimization. In Proc. of GECCO '11, pages 1723--1730. ACM, 2011.

Digital Library

[13]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[14]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[15]

P. S. Oliveto, J. He, and X. Yao. Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. Int'l Journal of Automation and Computing, 4(3):281--293, 2007.

Cited By

Nie PWan CZhu JLin ZChen YSu Z(2023)Coverage-directed Differential Testing of X.509 Certificate Validation in SSL/TLS ImplementationsACM Transactions on Software Engineering and Methodology10.1145/351041632:1(1-32)Online publication date: 22-Feb-2023
https://dl.acm.org/doi/10.1145/3510416
Barghi BSikari S(2022)Meta-heuristic Solution with Considering Setup Time for Multi-Skilled Project Scheduling ProblemOperations Research Forum10.1007/s43069-021-00117-53:1Online publication date: 1-Mar-2022
https://doi.org/10.1007/s43069-021-00117-5
Huynh QNguyen DDao TVu TVu TNguyen T(2019)Some Improvements of Using the NSGA-II Algorithm for the Problem of Resource Allocation and Scheduling and Its Applying to Inventory Management Strategies2019 11th International Conference on Knowledge and Systems Engineering (KSE)10.1109/KSE.2019.8919492(1-6)Online publication date: Oct-2019
https://doi.org/10.1109/KSE.2019.8919492
Show More Cited By

Index Terms

Evolutionary algorithms for the project scheduling problem: runtime analysis and improved design
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Empirical Analysis of Crossover-Based Evolutionary Algorithms on Rugged Landscape
GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation

The crossover is considered as an essential component of the evolutionary algorithms. There exist different ways of how to use it, and in this paper we compare two approaches commonly used in pseudo-Boolean optimization, the classic approach of (μ + 1)...
Comparative Analysis of Evolutionary Algorithms for the Problem of Parametric Optimization of PID Controllers

Six modern and promising evolutionary algorithms are described: genetic algorithm, differential evolution method, variational genetic algorithm, particle swarm optimization algorithm, bat-inspired method and firefly algorithm. For all algorithms brief ...
Evolving evolutionary algorithms using evolutionary algorithms
GECCO '07: Proceedings of the 9th annual conference companion on Genetic and evolutionary computation

A new model for automatic generation of Evolutionary Algorithms (EAs) by evolutionary means is proposed in this paper. The model is based on a simple Genetic Algorithm (GA). Every GA chromosome encodes an EA, which is used for solving a particular ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

July 2012

1396 pages

ISBN:9781450311779

DOI:10.1145/2330163

Editor:
Terence Soule
University of Idaho, USA
,
General Chair:
Jason H. Moore
Dartmouth College, USA

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '12

Sponsor:

SIGEVO

GECCO '12: Genetic and Evolutionary Computation Conference

July 7 - 11, 2012

Pennsylvania, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
235
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nie PWan CZhu JLin ZChen YSu Z(2023)Coverage-directed Differential Testing of X.509 Certificate Validation in SSL/TLS ImplementationsACM Transactions on Software Engineering and Methodology10.1145/351041632:1(1-32)Online publication date: 22-Feb-2023
https://dl.acm.org/doi/10.1145/3510416
Barghi BSikari S(2022)Meta-heuristic Solution with Considering Setup Time for Multi-Skilled Project Scheduling ProblemOperations Research Forum10.1007/s43069-021-00117-53:1Online publication date: 1-Mar-2022
https://doi.org/10.1007/s43069-021-00117-5
Huynh QNguyen DDao TVu TVu TNguyen T(2019)Some Improvements of Using the NSGA-II Algorithm for the Problem of Resource Allocation and Scheduling and Its Applying to Inventory Management Strategies2019 11th International Conference on Knowledge and Systems Engineering (KSE)10.1109/KSE.2019.8919492(1-6)Online publication date: Oct-2019
https://doi.org/10.1109/KSE.2019.8919492
Tirkolaee EGoli AHematian MSangaiah AHan T(2019)Multi-objective multi-mode resource constrained project scheduling problem using Pareto-based algorithmsComputing10.1007/s00607-018-00693-1101:6(547-570)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00607-018-00693-1
Yuan XLiu JHao X(2017)A moving block sequence-based evolutionary algorithm for resource investment project scheduling problemsBig Data and Information Analytics10.3934/bdia.20170072:1(39-58)Online publication date: Sep-2017
https://doi.org/10.3934/bdia.2017007
Sarro FFerrucci FHarman MManna ARen J(2017)Adaptive Multi-Objective Evolutionary Algorithms for Overtime Planning in Software ProjectsIEEE Transactions on Software Engineering10.1109/TSE.2017.265091443:10(898-917)Online publication date: 1-Oct-2017
https://doi.org/10.1109/TSE.2017.2650914
Javanmard SAfshar-Nadjafi BAkhavan Niaki S(2017)Preemptive multi-skilled resource investment project scheduling problem: Mathematical modelling and solution approachesComputers & Chemical Engineering10.1016/j.compchemeng.2016.11.00196(55-68)Online publication date: Jan-2017
https://doi.org/10.1016/j.compchemeng.2016.11.001
Stylianou CAndreou A(2016)Investigating the impact of developer productivity, task interdependence type and communication overhead in a multi-objective optimization approach for software project planningAdvances in Engineering Software10.1016/j.advengsoft.2016.04.00198:C(79-96)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.advengsoft.2016.04.001
Minku LSudholt DYao X(2014)Improved Evolutionary Algorithm Design for the Project Scheduling Problem Based on Runtime AnalysisIEEE Transactions on Software Engineering10.1109/TSE.2013.5240:1(83-102)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1109/TSE.2013.52
Jian Xiong Jing Liu Yingwu Chen Abbass H(2014)A Knowledge-Based Evolutionary Multiobjective Approach for Stochastic Extended Resource Investment Project Scheduling ProblemsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2013.228391618:5(742-763)Online publication date: Oct-2014
https://doi.org/10.1109/TEVC.2013.2283916
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents