Evolutionary Algorithm for the Earliness Tardiness Project Scheduling Problem
Abstract
Completing too early or too late can cause damage to the project. For example, in transporting goods to the
seaports, if the shipping arrives too early, it will take time and cost to stay at the dock. In the other case, shipping too late will reduce the quality of the product and break the contract. The goal of this paper is to minimize the tardiness and earliness of those projects. First, some related studies are briefly introduced, thereby showing the role and practical applications of the MS-RCPSP (Multi-Skill Resource Constrained Project Scheduling Problem) problem and the two factors of earliness and delay in scheduling problems. The roles of earliness and tardiness in scheduling problems are also described. At the same time, the new contribution of this research is also highlighted, which is the proposal for the latest problem E-RCPSP (Earliness tardiness MS-RCPSP). This problem is the first problem in the MS-RCPSP family that considers the sum of earliness and tardiness as the objective, which has never been considered in previous studies. Then, the mathematical
model of the proposed E-RCPSP problem, which includes the objective function, project components and constraints is introduced. To solve the proposed problem, two approximate algorithms based on the evolutionary algorithms GA (Genetic Algorithm) and DE (Differential Evolution) are introduced. In the last section of the article, the performance of these two algorithms is verified and compared with each other through experiments conducted on the iMOPSE benchmark dataset.
References
H. Najafzad, H. Davari-Ardakani, R. Nemati-Lafmejani, "Multi-skill project scheduling problem under time-of-use electricity tariffs and shift differential payments", In Energy Journal, vol. 168, pp. 619-636, Elsevier, 2019.
P.B. Myszkowski, M. Laszczyk, I. Nikulin, M. Skowro, "iMOPSE: a library for bicriteria optimization in Multi-Skill
Resource-Constrained Project Scheduling Problem", In Soft Computing Journal, 23: 32397, 2019.
P.B. Myszkowski, M. Skowro´nski, L. Olech, K. O´ slizło, " Hybrid Ant Colony Optimization in solving Multi–Skill
Resource–Constrained Project Scheduling Problem", In Soft Computing Journal, Volume 19, Issue 12, pp.3599–3619, 2015.
S. Javanmard, B. Afshar-Nadjafi, S.T. Niaki, "Preemptive multi-skilled resource investment project scheduling prob lem: Mathematical modeling and solution approaches," In Computers & Chemical Engineering, 96, pp. 55-68, 2017.
Skowronski M., Myszkowski P.B., " Specialized genetic operators for Multi–Skill Resource–Constrained Project
Scheduling Problem", In 19th Inter, Conference on Soft Computing- Mendel 2013, pp. 57-62, 2013
Y. Khoshjahan, A.A. Najafi, B.A. Nadjafi, "Resource constrained project scheduling problem with discounted
earliness-tardiness penalties: Mathematical modeling and solving procedure", In Computers & Industrial Engineering, 2013.
V. A. Strusevich, K. Rustogi, "Scheduling with Times Changing Effects and Rate-Modifying Activities", In
Springer International Publishing, 2017.
Kramer, A., Subramanian, A., " A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems", In Journal of Scheduling, vol. 22, 2019.
A.H. Hosseinian, V. Baradaran, " An Evolutionary Algorithm Based on a Hybrid Multi-Attribute Decision Mak
ing Method for the Multi-Mode Multi-Skilled Resource Constrained Project Scheduling Problem", In Journal of
Optimization in Industrial Engineering, 12.2, pp. 155-178, 2019.
A.H. Hosseinian, V. Baradaran," Detecting communities of workforces for the multi-skill resource-constrained project scheduling problem: A dandelion solution approach", In Journal of Industrial and Systems Engineering, pp. 72-99, 12.2019.
A.H. Hosseinian, V. Baradaran," P-GWO and MOFA: two new algorithms for the MSRCPSP with the deterioration effect and financial constraints (case study of a gas treating company)", In Applied Intelligence, 50, pp. 2151-2176, 2020.
Younis, Muhanad Tahrir, and Shengxiang Yang, "Hybrid meta-heuristic algorithms for independent job scheduling in grid computing", In Applied soft computing, vol.72, pp. 498 517, 2018.
Maghsoudlou, Hamidreza, Behrouz Afshar-Nadjafi, and Seyed Taghi Akhavan Niaki," Multi-skilled project schedul ing with level-dependent rework risk; three multi-objective mechanisms based on cuckoo search", In Applied Soft Computing, vol. 54, pp. 46-61, 2017.
Bibiks, Kirils, et al.," Improved discrete cuckoo search for the resource-constrained project scheduling problem", In Applied Soft Computing, vol. 69, pp. 493-503, 2018.
Zhu, Lei, Jian Lin, Zhou-Jing Wang, "A discrete oppositional multi-verse optimization algorithm for multi-skill resource constrained project scheduling problem", In Applied Soft Computing, vol. 85, 2019.
Mario Vanhoucke, Erik Demeulemeester, and Willy Herroelen," An Exact Procedure for the Resource-Constrained In Kluwer Academic Publishers. Manufactured in The Netherlands, 2001.
Maarten Otten, Aleida Braaksma, Richard J. Boucherie, "Minimizing Earliness/Tardiness costs on multiple machines with an application to surgery scheduling", Operations Research for Health Care, vol. 22, 2019.
S. Akande, G. Ajisegiri, " Three classes of Earliness Tardiness (E/T) scheduling problems", In Fuel Communica
tions, vol. 10, 2022.
S. Akande, Ajisegiri GO, " Single machine multi-criteria scheduling problem: total completion time, maximum lateness, and maximum earliness performance measures", In International Journal of Planning and Scheduling, vol. 3, 2021.
K.Price, R.Storn, J.Lampinen: "Differential Evolution- A Practical Approach to Global Optimization", In Springer, Berlin, Germany, 2005.
