article

Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB

Authors:

Shih-Tang LoAuthors Info & Claims

Expert Systems with Applications: An International Journal, Volume 37, Issue 3

Pages 1899 - 1910

https://doi.org/10.1016/j.eswa.2009.07.024

Published: 01 March 2010 Publication History

Abstract

This investigation proposes an improved particle swam optimization (PSO) approach to solve the resource-constrained scheduling problem. Two proposed rules named delay local search rule and bidirectional scheduling rule for PSO to solve scheduling problem are proposed and evaluated. These two suggested rules applied in proposed PSO facilitate finding global minimum (minimum makespan). The delay local search enables some activities delayed and altering the decided start processing time, and being capable of escaping from local minimum. The bidirectional scheduling rule which combines forward and backward scheduling to expand the searching area in the solution space for obtaining potential optimal solution. Moreover, to speed up the production of feasible solution, a critical path is adopted in this study. The critical path method is used to generate heuristic value in scheduling process. The simulation results reveal that the proposed approach in this investigation is novel and efficient for resource-constrained class scheduling problem.

References

[1]

A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research. v140 i2. 268-281.

[2]

Buyya, R., Abramson, D.,&Giddy, J. (2000). Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid. The Fourth International Conference on High-Performance Computing in the Asia-Pacific Region, 1, 283.

[3]

A new aircrew-scheduling model for short-haul routes. Journal of Air Transport Management. v8 i4. 249-260.

[4]

Chen, R. M., Lo, S. T., Wang, C. J.,&Wu, C. L. (2006). Multiprocessor system scheduling with precedence and resources constraints by ant colony system. 2006 ICS Conference.

[5]

Chen, T., Zhang, B., Hao, X.,&Dai, Y. (2006). Task scheduling in grid based on particle swarm optimization. Parallel and distributed computing, 2006. ISPDC '06. The fifth international symposium on (pp. 238-245).

Digital Library

[6]

Combining competitive scheme with slack neurons to solve real-time job scheduling problem. Expert Systems with Applications. v33 i1. 75-85.

Digital Library

[7]

Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation. v1 i1. 53-66.

Digital Library

[8]

Fleming, P. J.,&Fonseca, C. M. (1993). Genetic algorithms in control systems engineering: a brief introduction. IEE colloquium on genetic algorithms for control systems engineering (pp. 1/1-1/5).

[9]

Glover F. (1989). Tabu Search - Part I. ORSA JOURNAL ON COMPUTING, 1(3), 190-206.

[10]

Genetic algorithms and classifier systems: foundations and future directions. Proceedings of the second international conference on genetic algorithms on genetic algorithms and their application. 82-89.

Digital Library

[11]

Neural computation of decision in optimization problems. Biological Cybernetics. v52. 141-152.

[12]

Scheduling multiprocessor job with resource and timing constraints using neural network. IEEE Transactions on System, Man and Cybernetics. Part B. v29 i4. 490-502.

Digital Library

[13]

Jalilvand, A., Khanmohammadi, S.,&Shabaninia, F. (2005). Scheduling of sequence-dependant jobs on parallel multiprocessor systems using a branch and bound-based Petri net. In Emerging technologies, proceedings of the IEEE symposium (pp. 334-339).

[14]

Kennedy, J.,&Eberhart, R. C. (1995). Particle swarm optimization. In Proceedings IEEE international conference on neural networks (Vol. 4, pp. 1942-1948).

[15]

Optimization by Simulated Annealing. Science. v220 i4598. 671-680.

[16]

Li, C., Bettati, R.,&Zhao, W. (1997). Static priority scheduling for ATM networks. In 18th IEEE real-time systems symposium (RTSS '97) (pp. 264-273).

Digital Library

[17]

An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research. v56. 370-379.

[18]

GA-based resource-constrained project scheduling with the objective of minimizing activities' cost. Lecture Notes in Computer Science. v3644. 937-946.

Digital Library

[19]

Luo, X., Wang, D., Tang, J.,&Tu, Y. (2006). An improved PSO algorithm for resource-constrained project scheduling problem, intelligent control and automation, 2006. In The sixth world congress on WCICA 2006 (Vol. 1, pp. 3514-3518).

[20]

Lupetti, S.,&Zagorodnov, D. (2006). Data popularity and shortest-job-first scheduling of network transfers. International Conference on Digital Telecommunications (ICDT'06), p. 26.

Digital Library

[21]

Course and classroom scheduling: An interactive computer graphics approach. Journal of Systems and Software. v15. 149-157.

Digital Library

[22]

Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation. v6 i4. 333-346.

[23]

Ohki, M.,&Morimoto, A.,&Miyake, K. (2006). Nurse Scheduling by using cooperative GA with efficient mutation and mountain-climbing operators. In Third international IEEE conference on intelligent systems (pp. 164-169).

[24]

Project Scheduling Problem Library - PSPLIB: <http://www.129.187.106.231/psplib/>.

[25]

Noise Strategies for Improving Local Search. Proceedings of the twelfth national conference on artificial intelligence. v1. 337-343.

Digital Library

[26]

Shaw, K. J., Nortcliffe, A. L., Thompson, M., Love, J., Fleming, P. J.,&Fonseca, C. M. (1999). Assessing the performance of multiobjective genetic algorithms for optimization of a batch process scheduling problem. In Proceedings of the 1999 congress on evolutionary computation, CEC 99 (Vol. 7, p. 45).

[27]

Simulation scheduling in food industry application. Mathematical and statistical methods. Food Processing and Preservation. v20 i1. 31-37.

[28]

A Tabu search approach for the resource-constrained project scheduling problem. Journal of Heuristics. v4 i2. 123-139.

Digital Library

[29]

Zhai, X., Tiong, R. L. K., Bjornsson, H. C., Chua, D. K. H. (2006). A simulation-ga based model for production planning in precast plant. In Proceedings of the 38th conference on winter simulation winter simulation conference (pp. 1796-1803).

Digital Library

[30]

An improved particle swarm optimization algorithm for flowshop scheduling problem. Information Processing Letters. v108 i4. 204-209.

Cited By

Ghoroqi MGhoddousi PMakui AShirzadi Javid ATalebi S(2024)Integration of resource supply management and scheduling of construction projects using multi-objective whale optimization algorithm and NSGA-IISoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-09467-028:11-12(6983-7001)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00500-023-09467-0
(2018)A novel discrete particle swarm optimisation for scheduling projects with resource-constraintsInternational Journal of Cognitive Performance Support10.1504/IJCPS.2018.0930781:2(103-116)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1504/IJCPS.2018.093078
He SXiao LWang YLiu XYang CLu JGui WSun Y(2017)A novel fault diagnosis method based on optimal relevance vector machineNeurocomputing10.1016/j.neucom.2017.06.024267:C(651-663)Online publication date: 6-Dec-2017
https://dl.acm.org/doi/10.1016/j.neucom.2017.06.024
Show More Cited By

Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Particle swarm optimization with justification and designed mechanisms for resource-constrained project scheduling problem

Research highlights This study generated schedules by both forward and backward scheduling particle swarms. This work applies justification technique to further shorten the makespan of the yield schedule. To synchronize the justified schedules, a ...
A hybrid particle swarm optimization for job shop scheduling problem

A hybrid particle swarm optimization (PSO) for the job shop problem (JSP) is proposed in this paper. In previous research, PSO particles search solutions in a continuous solution space. Since the solution space of the JSP is discrete, we modified the ...
Application of particle swarm optimization and simulated annealing algorithms in flow shop scheduling problem under linear deterioration

This paper studies a permutation flow shop scheduling problem with deteriorating jobs. Deteriorating jobs are the jobs which the processing time depends on the waiting time before process starts. A particle swarm optimization algorithm with and without ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Expert Systems with Applications: An International Journal

Expert Systems with Applications: An International Journal Volume 37, Issue 3

March, 2010

901 pages

ISSN:0957-4174

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2009.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 March 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghoroqi MGhoddousi PMakui AShirzadi Javid ATalebi S(2024)Integration of resource supply management and scheduling of construction projects using multi-objective whale optimization algorithm and NSGA-IISoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-09467-028:11-12(6983-7001)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00500-023-09467-0
(2018)A novel discrete particle swarm optimisation for scheduling projects with resource-constraintsInternational Journal of Cognitive Performance Support10.1504/IJCPS.2018.0930781:2(103-116)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1504/IJCPS.2018.093078
He SXiao LWang YLiu XYang CLu JGui WSun Y(2017)A novel fault diagnosis method based on optimal relevance vector machineNeurocomputing10.1016/j.neucom.2017.06.024267:C(651-663)Online publication date: 6-Dec-2017
https://dl.acm.org/doi/10.1016/j.neucom.2017.06.024
Lin YChong C(2017)Fast GA-based project scheduling for computing resources allocation in a cloud manufacturing systemJournal of Intelligent Manufacturing10.1007/s10845-015-1074-028:5(1189-1201)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10845-015-1074-0
Kumar NVidyarthi D(2016)A model for resource-constrained project scheduling using adaptive PSOSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1606-820:4(1565-1580)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s00500-015-1606-8
Qi JLiu YJiang PGuo B(2015)Schedule generation scheme for solving multi-mode resource availability cost problem by modified particle swarm optimizationJournal of Scheduling10.1007/s10951-014-0374-018:3(285-298)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s10951-014-0374-0
Hu WWang HPeng CWang HLiang HDu B(2015)An outer---inner fuzzy cellular automata algorithm for dynamic uncertainty multi-project scheduling problemSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-014-1395-519:8(2111-2132)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1007/s00500-014-1395-5
Crawford BSoto RJohnson FVargas MMisra SParedes F(2015)A Scheduling Problem for Software Project Solved with ABC MetaheuristicProceedings, Part IV, of the 15th International Conference on Computational Science and Its Applications -- ICCSA 2015 - Volume 915810.1007/978-3-319-21410-8_48(628-639)Online publication date: 22-Jun-2015
https://dl.acm.org/doi/10.1007/978-3-319-21410-8_48
Tavana MAbtahi AKhalili-Damghani K(2014)A new multi-objective multi-mode model for solving preemptive time-cost-quality trade-off project scheduling problemsExpert Systems with Applications: An International Journal10.1016/j.eswa.2013.08.08141:4(1830-1846)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1016/j.eswa.2013.08.081
Subashini GBhuvaneswari M(2012)Task allocation in distributed computing systems using adaptive particle swarm optimisationInternational Journal of Computer Applications in Technology10.1504/IJCAT.2012.05011744:4(293-302)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1504/IJCAT.2012.050117

View Options

View options

Get Access

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

Media

Figures

Other

Tables

View Issue’s Table of Contents