Preemptive multi-skilled resource constrained project scheduling problem with hard/soft interval due dates
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 5, pp. 1877-1898.

This paper considers a preemptive multi-skilled resource constrained project scheduling problem in a just-in-time environment where each activity has an interval due date to be completed. In this problem setting, resuming a preempted activity requires an extra setup cost, while each time unit violation from the given due date incurs earliness or tardiness penalty. Also, processing cost of each skill to execute any activity depends on the assigned staff member to accomplish the skill. The objective function of the model aims to minimize the total cost of allocating staff to skills, earliness–tardiness penalties and preemption costs. Two integer formulations are proposed for the model which are compared in terms of number of variables, constraints and elapsed run-time to optimality. Furthermore, an ant colony based metaheuristic is developed to tackle real life scales of the proposed model. This algorithm relies on two intelligent local search heuristics. Parameters of the algorithm are calibrated using Taguchi method. The results of the experiments for the proposed algorithm confirm that the proposed algorithm has satisfying performance.

DOI : 10.1051/ro/2018103
Classification : 90B35, 90C11, 90C59
Mots-clés : Multi-skilled, project scheduling, due date, preemption, ant colony optimization
Maghsoudlou, Hamidreza 1 ; Afshar-Nadjafi, Behrouz 1 ; Niaki, Seyed Taghi Akhavan 1

1 
@article{RO_2019__53_5_1877_0,
     author = {Maghsoudlou, Hamidreza and Afshar-Nadjafi, Behrouz and Niaki, Seyed Taghi Akhavan},
     title = {Preemptive multi-skilled resource constrained project scheduling problem with hard/soft interval due dates},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1877--1898},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {5},
     year = {2019},
     doi = {10.1051/ro/2018103},
     mrnumber = {4021873},
     zbl = {1431.90068},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018103/}
}
TY  - JOUR
AU  - Maghsoudlou, Hamidreza
AU  - Afshar-Nadjafi, Behrouz
AU  - Niaki, Seyed Taghi Akhavan
TI  - Preemptive multi-skilled resource constrained project scheduling problem with hard/soft interval due dates
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 1877
EP  - 1898
VL  - 53
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018103/
DO  - 10.1051/ro/2018103
LA  - en
ID  - RO_2019__53_5_1877_0
ER  - 
%0 Journal Article
%A Maghsoudlou, Hamidreza
%A Afshar-Nadjafi, Behrouz
%A Niaki, Seyed Taghi Akhavan
%T Preemptive multi-skilled resource constrained project scheduling problem with hard/soft interval due dates
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 1877-1898
%V 53
%N 5
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018103/
%R 10.1051/ro/2018103
%G en
%F RO_2019__53_5_1877_0
Maghsoudlou, Hamidreza; Afshar-Nadjafi, Behrouz; Niaki, Seyed Taghi Akhavan. Preemptive multi-skilled resource constrained project scheduling problem with hard/soft interval due dates. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 5, pp. 1877-1898. doi : 10.1051/ro/2018103. http://www.numdam.org/articles/10.1051/ro/2018103/

B. Afshar-Nadjafi, M. Majlesi, Resource constrained project scheduling problem with setup times after preemptive processes. Comput. Chem. Eng. 69 (2014) 16–25. | DOI

B. Afshar-Nadjafi and S. Shadrokh, An algorithm for the weighted earliness-tardiness unconstrained project scheduling problem. J. Appl. Sci. 8 (2008) 1651–1659. | DOI

F.S. Al-Anzi, K. Al-Zame and A. Allahverdi, Weighted multi-skill resources project scheduling. J. Softw. Eng. Appl. 3 (2010) 1125–1130. | DOI

C. Artigues, R. Leus and F.T. Nobibon, Robust optimization for resource-constrained project scheduling with uncertain activity durations. Flex. Serv. Manuf. J. 25 (2013) 175–205. | DOI

F. Ballestin, A. Barrios and V. Valls, An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time lags. J. Sched. 14 (2011) 391–406. | DOI | MR | Zbl

F. Ballestin, V. Valls and S. Quintanilla, Preemption in resource-constrained project scheduling. Eur. J. Oper. Res. 189 (2008) 1136–1152. | DOI | Zbl

O. Bellenguez-Morineau, Methods to solve the multi-skill project scheduling problem, 4OR 6 (2008) 85–88. | DOI | Zbl

O. Bellenguez-Morineau and E. Neron, Lower Bounds for the multi-skill project scheduling problem with hierarchical levels of skills. In practice and theory of automated timetabling. Lectures Notes Comput. Sci. 3616 (2005) 229–243. | DOI

O. Bellenguez-Morineau and E. Neron, A branch-and-bound method for solving multi-skill project scheduling problems. RAIRO: OR 41 (2007) 155–170. | DOI | Numdam | MR | Zbl

D.G. Cabrero and D.N. Ranasinghe, Fine-tuning the Ant Colony System Algorithm Through Particle Swarm Optimization. Technical Report-University of Valencia, Spain (2005).

W.N. Chen and J. Zhang, Scheduling multi-mode projects under uncertainty to optimize cash flows: a Monte Carlo ant colony system approach. J. Comput. Sci. Technol. 27 (2012) 950–965. | DOI | Zbl

W.N. Chen, J. Zhang, H.S.H. Chung, R.Z. Huang and O. Liu, Optimizing discounted cash flows in project scheduling – an ant colony optimization approach. IEEE Trans. Syst. Man Cybern. Part C (Appl. Rev.) 40 (2010) 64–77. | DOI

H. Cheng and X. Chu, Task assignment with multi-skilled employees and multiple modes for product development projects. Int. J. Adv. Manuf. Technol. 61 (2012) 391–403. | DOI

C.W. Chiang, Y.Q. Huang and W.Y. Wang, Ant colony optimization with parameter adaptation for multi-mode resource-constrained project scheduling. J. Intell. Fuzzy Syst. 19 (2008) 345–358. | Zbl

S. Christodoulou, Scheduling resource-constrained projects with ant colony optimization artificial agents. J. Comput. Civ. Eng. 24 (2009) 45–55. | DOI

I. Correia, L. Lourenco and F. Saldanha-Da-Gama, Project scheduling with flexible resources: formulation and inequalities. OR Spectr. 34 (2012) 635–663. | DOI | MR | Zbl

I. Correia and F. Saldanha-Da-Gama, The impact of fixed and variable costs in a multi-skill project scheduling problem: An empirical study. Comput. Ind. Eng. 72 (2014) 230–238. | DOI

C. Dhib, A. Soukhal and E. Neron, Mixed-integer linear programming formulation and priority-rule methods for a preemptive project staffing and scheduling problem, edited byC. Schwindt and J. Zimmermann. In: Handbook on Project Management and Scheduling. Springer (2015) 603–617. | DOI

M. Dorigo, Optimization, learning and natural algorithms. Ph.D. thesis, Politecnico di Milano, Milano, Italy, 1992.

A. Drexl, R. Nissen, J.H. Patterson and F. Salewski, ProGen/πx – An instance generator for resource constrained project scheduling problems with partially renewable resources and further extensions. Eur. J. Oper. Res. 125 (2000) 59–72. | DOI | MR | Zbl

M. Frat and C.A.J. Hurkens, An improved MIP-based approach for a multi-skill workforce scheduling problem. J. Sched. 15 (2012) 363–380. | DOI | MR | Zbl

C. Heimerl and R. Kolisch, Scheduling and staffing multiple projects with a multi-skilled workforce. OR Spectr. 32 (2010) 343–368. | DOI | MR | Zbl

C.A. Hurkens, Incorporating the strength of MIP modeling in schedule construction. RAIRO: OR 43 (2009) 409–420. | DOI | Numdam | Zbl

Y. Kadrou and N.M. Najid, A new heuristic to solve RCPSP with multiple execution modes and multi-skilled labor. Comput. Eng. Syst. Appl. IMACS Multi Conf. 2 (2006) 1302–1309.

H. Kazemipoor, R. Tavakkoli-Moghaddam, P. Shahnazari-Shahrezaei and A. Azaron, A differential evolution algorithm to solve multi-skilled project portfolio scheduling problems. Int. J. Adv. Manuf. Technol. 64 (2013) 1099–1111. | DOI

C. Kellenbrink and S. Helber, Scheduling resource-constrained projects with a flexible project structure. Eur. J. Oper. Res. 246 (2015) 379–391. | DOI | Zbl

Y. Khoshjahan, A.A. Najafi and B. Afshar-Nadjafi, Resource constrained project scheduling problem with discounted earliness–tardiness penalties: mathematical modeling and solving procedure. Comput. Ind. Eng. 66 (2013) 293–300. | DOI

O. Koné, C. Artigues, P. Lopez and M. Mongeau, Comparison of mixed integer linear programming models for the resource-constrained project scheduling problem with consumption and production of resources. Flex. Serv. Manuf. J. 25 (2013) 25–47. | DOI

H. Li and K. Womer, Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm. J. Sched. 12 (2009) 281–298. | DOI | MR | Zbl

H. Li and H. Zhang, Ant colony optimization-based multi-mode scheduling under renewable and nonrenewable resource constraints. Autom. Constr. 35 (2013) 431–438. | DOI

S.S. Liu and C.J. Wang, Optimizing linear project scheduling with multi-skilled crews. Autom. Constr. 24 (2012) 16–23. | DOI

H. Maghsoudlou, B. Afshar-Nadjafi and S.T.A. Niaki, A multi-objective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained project scheduling problem. Comput. Chem. Eng. 88 (2016) 157–169. | DOI

D. Merkle, M. Middendorf and H. Schmeck, Ant colony optimization for resource-constrained project scheduling. IEEE Trans. Evol. Comput. 6 (2002) 333–346. | DOI

C. Montoya, O. Bellenguez-Morineau, E. Pinson and D. Rivreau, Branch-and-price approach for the multi-skill project scheduling problem. Optim. Lett. 8 (2013) 1721–1734. | DOI | MR | Zbl

A. Moukrim, A. Quilliot and H. Toussaint, An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal Interval order enumeration. Eur. J. Oper. Res. 244 (2015) 360–368. | DOI | MR | Zbl

E. Néron and D. Baptista, Heuristics for multi-skill project scheduling problem. Int. Symp. Comb. Optim. (CO’2002) (2002).

H. Okubo, T. Miyamoto, S. Yoshida, K. Mori, S. Kitamura and Y. Izui, Project scheduling under partially renewable resources and resource consumption during setup operations. Comput. Ind. Eng. 83 (2015) 91–99. | DOI

M. Ranjbar, M. Khalilzadeh, F. Kianfar and K. Etminani, An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem. Comput. Ind. Eng. 62 (2012) 264–270. | DOI

H. Rolfe, Qualifications and international mobility: a case study of the European chemicals industry. Nat. Inst. Econ. Rev. 175 (2001) 85–94. | DOI

G. Taguchi, Introduction to Quality Engineering. Asian Productivity Organization, Tokyo (1986).

Cité par Sources :