Moving to higher directional scheduling schemes

Iranian Journal of Numerical Analysis and Optimization

مقاله 9، دوره 10، شماره 1 - شماره پیاپی 17، تیر 2020، صفحه 139-155   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.v10i1.73001

نویسندگان

H.R. Yousefzadeh^* ؛ M. Nasehi

Department of Mathematics, Payame Noor University (PNU), Iran.

چکیده

A general overview of the scheduling’s literature of some researches shows that among various factors, the priority rules and also the structure of projects are two main factors that can be affected on the performance of multidirectional scheduling schemes. In addition, a variation on the number of directors in scheduling schemes (e.g., single directional, bi-directional, and tri-directional scheduling scheme) produces different makespans. However, the question of when to move from the single direction to the multidirectional scheduling schemes remained open. In this paper, based on analytical and also empirical results, we show that when availability and distributions of resource measures such as the number of peaks and number of overflows or the average amount of overflows are increased, higher directional scheduling schemes can be produced smaller makespans. Hence, in the light of these resource measures, the multidirectional scheduling schemes can be reduced the dependency of the solution’s quality on the priority rules used.

کلیدواژه‌ها

Scheduling؛ Priority rule؛ Heuristic algorithms؛ Multidirectional scheduling schemes؛ Resource measure

مراجع

[1] Agarwal, R., Tiwari, M.K. and Mukherjee, S.K. Artificial immune system based approach for solving resource constraint project scheduling problem, Int. J. Adv. Manuf. Technol. 34(5-6) (2007), 584–593.

[2] Bouleimen, K. and Lecocq, H. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version, European J. Oper. Res. 149(2) (2003), 268–281.

[3] Browning, T.R. and Yassine, A.A. A random generator of resource constrained multi-project network problems, J. Sched. 13(2) (2010), 143–161.

[4] Brucker, P., Drexl, A., Möhring, R., Neumann, K. and Pesch, E. Resource-constrained project scheduling: Notation, classification, models, and methods, European J. Oper. Res. 112(1) (1999), 3–41.

[5] Brucker, P., Knust, S., Schoo, A. and Thiele, O. A branch and bound algorithm for the resource-constrained project scheduling problem, European J. Oper. Res. 107(2) (1998), 272–288.

[6] Cooper, D.F. Heuristics for Scheduling Resource-Constrained Projects: An Experimental Investigation, Manag. Sci. 22(11) (1976), 1186–1194. doi:10.1287/mnsc.22.11.1186.

[7] Creemers, S. Minimizing the expected makespan of a project with stochastic activity durations under resource constraints, J. Sched. 18(3) (2015), 263–273.

[8] Davis, E.W. and Patterson, J.H. A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project Scheduling, Manag. Sci. 21(8) (1975), 944–955.

[9] Goncharov, E.N. and Leonov, V.V. Genetic algorithm for the resource constrained project scheduling problem, (Russian); translated from Avtomat. i Telemekh. 2017, , no. 6, 173–189 Autom. Remote Control 78 (2017), no. 6, 1101–1114.

[10] Hartmann, S. A self-adapting genetic algorithm for project scheduling under resource constraints, Naval Res. Logist. 49(5) (2002), 433–448. doi:10.1002/nav.10029.

[11] Icmeli, O. and Rom, W.O. Solving the resource constrained project scheduling problem with optimization subroutine library, Comput. Oper. Res. 23(8) (1996), 801–817.

[12] Kanit, R., Ozkan, O. and Gunduz, M. Effects of project size and resource constraints on project duration through priority rule-base heuristics, Artif. Intell. Rev. 32(1-4) (2009), 115–123. doi:10.1007/s10462-009-9138-1.

[13] Klein, R. Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects, European J. Oper. Res. 127(3) (2000), 619–638.

[14] Klein, R. and Scholl, A. PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem, Special issue on project scheduling. Math. Methods Oper. Res. 52(3) (2000), 467–488.

[15] Kolisch, R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation, European J. Oper. Res. 90(2) (1996), 320–333.

[16] Kolisch, R., Schwindt, C. and Sprecher, A. Benchmark instances for project scheduling problems, In: Węglarz J. (eds) Project Scheduling. In ternational Series in Operations Research & Management Science, vol 14.

Springer, Boston, MA. (1999).

[17] Kolisch, R., Sprecher, A. and Drexl, A. Characterization and Generation of a General Class of Resource-Constrained Project Scheduling Problems, Manag. Sci. 41(10) (1995), 1693–1703.

[18] Kurtulus, I. Multi-project scheduling: Analysis of scheduling strategies under Unequal DealyPenalities, J. Oper. Manag. 5(3) (1985), 161–172.

[19] Kurtulus, I. and Davis, E.W. Multi-Project Scheduling: Categorization of Heuristic Rules Performance, Manag. Sci. 28(2) (1982), 161–172.

[20] Lenstra, J.K. and Rinnooy, K.A.H.G. Complexity of Scheduling under Precedence Constraints, Operations Res. 26(1) (1978), 22–35.

[21] Liang, Y., Cui, N., Wang, T. and Demeulemeester, E. Robust resource constrained max-NPV project scheduling with stochastic activity duration, OR Spectrum. 41(1) (2019), 219–254.

[22] Mortazavi Nejad, M., Tareghian, H.R. and Sari, Z. Payment scheduling under project crashing based on project progress, Iranian Journal of Numerical Analysis and Optimization, 7(2) (2017), 39–56.

[23] Petrović, R. Optimization of Resource Allocation in Project Planning, Operations Res. 16(3) (1968), 559–568.

[24] Raghavendra, B.V. Scheduling in parallel machines environment using genetic algorithm, J. Appl. Eng. Sci. 16(1) (2018), 36–42.

[25] Servranckx, T. and Vanhoucke, M. A tabu search procedure for the resource-constrained project scheduling problem with alternative sub graphs, European J. Oper. Res. 273(3) (2019), 841–860.

[26] Shukla, S.K., Son, Y.J. and Tiwari, M.K. Fuzzy-based adaptive sample sort simulated annealing for resource-constrained project scheduling, Int. J. Adv. Manuf. Technol. 36(9-10) (2008), 982–995.

[27] Sokolov, B., Tolpegin, O., Ipatov, Y. and Andrianov, Y. Polymodel description and qualitative analysis of problems for measurement computer operations planning in cyber-physical systems, J. Appl. Eng. Sci. 16(4)

(2018), 577–582.

[28] Ulusoy, G. and Özdamar, L. Heuristic Performance and Net work/Resource Characteristics in Resource-constrained Project Schedul ing, J. Oper. Res. Soc. 40(12) (1989), 1145–1152.

[29] Yoosefzadeh, H.R., Tareghian, H.R. and Farahi, M.H. Tri-directional Scheduling Scheme: Theory and Computation, J. Math. Model. Algorithms. 9(4) (2010), 357–373.

[30] Yoosefzadeh, H.R., Tareghian, H.R. and Farahi, M.H. Multidirectional scheduling scheme in resource-constrained project scheduling problem, Naval Res. Logist. 61(1) (2013), 44–55.

[31] Zamani, M. A high-performance exact method for the resource constrained project scheduling problem, Comput. Oper. Res. 28(14)(2001), 1387–1401.

[32] Zhu, X., Ruiz, R., Li, S., and Li, X. An effective heuristic for project scheduling with resource availability cost, European J. Oper. Res. 257(3) (2017), 746–762.