Solving a mixed-integer linear programming model for a multi-skilled project scheduling problem by simulated annealing


H. Kazemipoor, R. Tavakkoli-Moghaddam and P. Shahnazari-Shahrezaei


A multi-skilled project scheduling problem (MSPSP) has been generally presented to schedule a project with staff members as resources. Each activity in project network requires different skills and also staff members have different skills, too. This causes the MSPSP becomes a special type of a multi-mode resource-constrained project scheduling problem (MM-RCPSP) with a huge number of modes. Given the importance of this issue, in this paper, a mixed integer linear programming for the MSPSP is presented. Due to the complexity of the problem, a meta-heuristic algorithm is proposed in order to find near optimal solutions. To validate performance of the algorithm, results are compared against exact solutions solved by the LINGO solver. The results are promising and show that optimal or near-optimal solutions are derived for small instances and good solutions for larger instances in reasonable time.


DOI: j.msl.2011.10.010

Keywords: Project scheduling ,Simulated annealing ,Mixed integer linear programming , ,

How to cite this paper:

Kazemipoor, H., Tavakkoli-Moghaddam, R & Shahnazari-Shahrezaei, P. (2012). Solving a mixed-integer linear programming model for a multi-skilled project scheduling problem by simulated annealing.Management Science Letters, 2(2), 681-688.


References

Artigues, C., Demassey, S., & Neron, E. (2008). Resource constraint project scheduling problem. John Wiley and Sons.Blazewicz, J., Lenstra, J.K. & Rinnooy Kan, A.H.G. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5, 11–24.

Bellenguez-Morineau, O. Neron, E. (2005). Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills, in: E.K. Burke and M. Trick, Eds., Practice and theory of automated timetabling. Lecture Notes in Computer Science, 3616, 229-243.

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

Cerny, V. A. (1985). Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm. Journal of Optimization Theory and Applications, 45(1), 41–51

Dauzere-peres, S., Roux, W., & Lassere, J.B. (1996). Multi-resource shop scheduling with resource flexibility. European Journal of Operation Research, 107, 289-305.

Demeulemeester, E.L., & Herroelen, W.S. (2002). Project scheduling: A research handbook, Kluwer Academic Publisher.Dowsland, K.A. (1993). Simulated Annealing. In C. R. Reeves, editor, Modern Heuristic Techniques for Combinatorial Problems. John Wiley & Sons

Gutjahr, W.J., Katzensteiner, S., Raiter, P., Stummer, & C., Denk, M. (2008). Competence-driven project portfolio selection scheduling and staff assignment. Central European Journal of Operation Research, 16, 281-306.

Gürbüza E. (2010). Genetic algorithm for bi-objective multi-skill project scheduling problem with hierarchical levels of skills, Thesis on industrial engineering department. Middle East Technical University, Turkey

Herroelen, W., & Leus, R. (2005). Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research, 165, 289-306.

Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207, 1-14.

Heimerl, C., Kolisch, R. (2009). Scheduling and staffing multiple project with a multi-skilled workforce. OR Spectrum, 32 (2), 343-368.

Jurish, B. (1992). Scheduling jobs in shops with multi-purpose machines, PhD Thesis, University of Osnabruck, Germany.Kadrou, Y., & Najid, N.M. (2006). Tabu search algorithm for the MRCPSP with multi-skilled personnel, Computational Engineering in System Application, IMACS Multi Conference, 2(4-6), 1302-1309.

Kirkpatrick, S., Gellatt, C., & Vecchi., M. (1983). Optimization by Simulated Annealing. Science, 220 (4598), 671–680.

Metropolis, N., Rosenbluth, A., Rosenbluth, M. , Teller, A., & Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics, 21(6), 1087–1092.

Neron, E., & Boptista, D. (2002). Heuristics for the multi-skill project scheduling problem, International Symposium on Combinatorial Optimization, Paris.

Pessan, C., Bellenguez-Morineau, O., & Neron, E. (2007). Multi-skill project scheduling problem and total preventive maintenance, Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), 608-610, Paris, 28-31 August.Press, W. H. Flannery B. P., Teukolsky S. A., & Vetterling W. T. (1989). Numerical Recipes in Pascal. Cambridge University Press, Cambridge, UK

Sait S. M., Youseff H., & Ali H. (1999). Fuzzy Simulated Evolution Algorithm for Multi-objective Optimization of VLSI Placement, Congress on Evolutionary Computation, Washington, D.C., July IEEE Service Center. 91-97

Seifi, M. & Tavakkoli-Moghaddam, R. (2008). A new bi-objective model for a multi-mode resource-constrained project scheduling problem with discounted cash flows and four payment models. International Journal of Engineering, Transaction A: Basic, 21(4), 347-360.

Valls, V., Perez, A., & Quintanilla, S. (2009). Skilled workforce scheduling in service centres. European Journal of Operational Research, 193, 791-804.