Solving Multi-Mode Resource-Constrained Multi-Project Scheduling Problem with Combinatorial Auction Mechanisms

10.6186/IJIMS.201906_30(2).0004

Chi-Bin Cheng；Chiao-Yu Lo；Chih-Ping Chu

Multi-project scheduling ； resource dedication ； bi-level decentralized programming ； combinatorial optimization ； fuzzy logic

International Journal of Information and Management Sciences

30卷2期（2019 / 06 / 01）

143 - 167

英文

This study solves a multi-project, multi-mode, and resource-constrained project scheduling problem. Multi-mode means that the activities in a project can be accomplished in one out of several execution modes, each of which represents an alternative combination of resource requirement of the activity. The present study considers the case that the resources need to be allocated first to individual projects by the upper-level manager, and then the project manager of each project schedules the project to optimize its outcome. In view of such a hierarchical decision-making structure, this study uses bi-level decentralized programming to model the problem. The proposed solution procedure employs combinatorial auction mechanisms to determine resource allocations to projects. A regular combinatorial auction and a fuzzy combinatorial auction are used, respectively, for cases of hard and soft capacity constraints. The proposed solution procedure is evaluated by comparison with the results reported in the literature.

1. Adhau, S.,Mittal, M. L.(2012).A Multiagent Based System for Resource Allocation and Scheduling of Distributed Projects.International Journal of Modeling and Optimization,2,524.
2. Adhau, S.,Mittal, M. L.,Mittal, A.(2012).A multi-agent system for distributed multi-project scheduling: An auction-based negotiation approach.Engineering Applications of Artificial Intelligence,25,1738-1751.
3. Adhau, S.,Mittal, M. L.,Mittal, A.(2013).A multi-agent system for decentralized multi-project scheduling with resource transfers.International Journal of Production Economics,146,646-661.
4. Aiyoshi, E.,Shimizu, K.(1981).Hierarchical decentralized systems and its new solution by a barrier method.IEEE Transactions on Systems, Man, and Cybernetics,11,444-449.
5. Alcaraz, J.,Maroto, C.,Ruiz, R.(2003).Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms.Journal of the Operational Research Society,54,614-626.
6. Anandalingam, G.,Apprey, V.(1991).Multi-level programming and conflict resolution.European Journal of Operational Research,51,233-247.
7. Bagherinejad, J.,Majd, Z. R.(2014).Solving the MRCPSP/max with the objective of minimizing tardiness/earliness cost of activities with double genetic algorithms.International Journal of Advanced Manufacturing Technology,70,573-582.
8. Barrios, A.,Ballestin, F.,Valls, V.(2011).A double genetic algorithm for the MRCPSP/max.Computers & Operations Research,38,33-43.
9. Bellman, R. E.,Zadeh, L. A.(1970).Decision-making in a fuzzy environment.Management Science,17,B141-B164.
10. Ben-Ayed, O.,Blair, C. E.(1990).Computational difficulties of bilevel linear programming.Operations Research,38,556-560.
11. Beşikci, U.,Bilge, U.,Ulusoy, G.(2015).Multi-mode resource constrained multi-project scheduling and resource portfolio problem.European Journal of Operational Research,240,22-31.
12. Beşikci, U,Bilge, U.,Ulusoy, G.(2013).Resource dedication problem in a multi-project environment.Flexible Services and Manufacturing Journal,25,206-229.
13. Bracken, J.,McGill, J. M.(1974).Defense applications of mathematical programs with optimization problem in the constraints.Operations Research,22,1086-1096.
14. Can, A.,Ulusoy, G.(2014).Multi-project scheduling with two-stage decomposition.Annals of Operations Research,217,95-116.
15. Chen, R.-M.,Sandnes, F. E.(2014).An efficient particle swarm optimizer with application to man-day project scheduling problems.Mathematical Problems in Engineering,2014,1-9.
16. Cheng, C.-B.(2011).Reverse auction with buyer-supplier negotiation using bi-level distributed programming.European Journal of Operational Research,211,601-611.
17. Cheng, C.-B.,Wu, H.-C.,Chan, C.-C. H.(2012).Design of a combinational auction mechanism for television advertising market in Taiwan.Research Journal of Applied Sciences Engineering and Technology,4,4105-4111.
18. Chien, T.-T.,Lin, Y.-I.,Tien, K.-W.(2013).Agent-based negotiation mechanism for multi-project human resource allocation.Journal of Industrial and Production Engineering,30,518-527.
19. de Vries, S.,Vohra, R.(2003).Combinatorial auctions: A survey.INFORMS Journal on Computing,15(3),284-309.
20. Economist Intelligence Unit(2009).Closing the gap: The link between project management excellence and long-term success.Economist Intelligence Unit Limited.
21. Elloumi, S.,Fortemps, P.(2010).A hybrid rank-based evolutionary algorithm applied to multimode resource-constrained project scheduling problem.European Journal of Operational Research,205,31-41.
22. Epstein, R.,Henrquez, L.,Cataln, J.,Weintraub, G. Y.,Martnez, C.(2002).A combinational auction improves school meals in Chil.Interfaces,32,1-14.
23. Goncalves, J. F.,Mendes, J. J. M.,Resende, M. G. C.(2008).A genetic algorithm for resource constrained multiproject scheduling problem.European Journal of Operational Research,189,1171-1190.
24. Hartmann, S.(2001).Project scheduling with multiple modes: a genetic algorithm.Annals of Operations Research,102,111-135.
25. Hartmann, S.,Drexl, A.(1998).Project scheduling with multiple modes: a comparison of exact algorithms.Networks,32,283-297.
26. Jackson, C.(1976).Cambridge, MA,Department of Electronical Engineering, Massachusetts Institute of Technology.
27. Kim, K. W.,Yun, Y.,Yoon, J.,Gen, M.,Yamazaki, G.(2005).Hybrid genetic algorithm with adaptive abilities for resource-constrained multiple project scheduling.Computers in Industry,56,143-160.
28. Kolisch, R.,Drexl, A.(1997).Local search for nonpreemptive multi-mode resource-constrained project scheduling.IIE Transactions,29,987-999.
29. Kolisch, R.,Padman, R.(2001).An integrated survey of deterministic project scheduling.OMEGA,29,249-272.
30. Kolisch, R.,Sprecher, A.(1996).PSPLIB a project scheduling problem library.European Journal of Operational Research,96,205-216.
31. Kurtulus, I. S.,Narula, S. C.(1985).Multi-project scheduling: analysis of project performance.IIE Transactions,17,58-66.
32. Lai, Y.-J.(1996).Hierarchical optimization: a satisfactory solution.Fuzzy Seta and Systems,77,321-335.
33. Lawrence, S. R.,Morton, T. E.(1993).Resource-constrained multi-project scheduling with tardycosts: comparing myopic, bottleneck, and resource pricing heuristics.European Journal of Operational Research,64,168-187.
34. Lova, A.,Maroto, C.,Tormos, P.(2000).A multicriteria heuristic method to improve resource allocation in multiproject environment.European Journal of Operational Research,127,408-424.
35. Lova, A.,Tormos, P.,Cervantes, M.,Barber, F.(2009).Efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes.International Journal of Production Economics,117,302-316.
36. McMillian, J.(1994).Selling spectrum rights.Journal of Economic Perspectives,8,145-162.
37. Messelis, T,De Causmaecker, P.(2014).An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem.European Journal of Operational Research,233,511-528.
38. Mori, M.,Tseng, C. C.(1997).A genetic algorithm for multi-mode resource constrained project scheduling problem.European Journal of Operational Research,100,134-141.
39. Park, S.,Rothkopf, M. H.(2001).Auctions with endogenously determined allowable combinations, RUTCOR research report 3-2001.New Brunswick, NJ:Rutgers University.
40. Prez, E.,Posada, M.,Lorenzana, A.(2015).Taking advantage of solving the resource constrained multi-project scheduling problems using multi-modal genetic algorithms.Soft Computing.
41. Pritsker, A. A. B.,Watters, L. J.,Wolfe, P. M.(1969).Multiproject scheduling with limited resources: a zero-one programming approach.Management Science,16,93-108.
42. Rassenti, S. J.,Smith, V. L.,Bulfin, R. L.(1982).A Combinatorial Auction Mechanism for Airport Time Slot Allocation.The Bell Journal of Economics,13,402-417.
43. Rothkopf, M. H.,Pekeč, A.,Harstad, R. M.(1998).Computationally manageable combinatorial auctions.Management Science,44,1131-1147.
44. Sandholm, T.(2002).Algorithm for optimal winner determination in combinatorial auctions.Artificial Intelligence,135,1-54.
45. Sandholm, T.(2000).Approaches to winner determination in combinatorial auctions.Decision Support Systems,28,165-176.
46. Schneeweiss, C.(2003).Distributed Decision Making.Berlin:Springer-Verlag.
47. Shih, H.-S.,Lai, Y.-J.,Lee, E. S.(1996).Fuzzy approach for multi-level programming problems.Computers and Operations Research Vol,23,73-91.
48. Slowinski, R.(1980).Two approaches to problems of resource allocation among project activities: a comparative study.Journal of Operations Research Society,31,711-723.
49. Slowinski, R.,Soniewicki, B.,Weglarz, J.(1994).DSS for multiobjective project scheduling.European Journal of Operational Research,79,220-229.
50. Speranza, M. G.,Vercellis, C.(1993).Hierachical models for multi-project planning and scheduling.European Journal of Operational Research,64,312-325.
51. Sprecher, A.,Drexl, A.(1998).Solving multi-mode resource-constrained project scheduling prob- lem by a simple, general and powerful sequencing algorithm.European Journal of Operational Research,107,431-450.
52. Sprecher, A.,Hartmann, S.,Drexl, A.(1997).An exact algorithm for project scheduling with multiple modes.OR Spectrum,19,195-203.
53. Talbot, F. B.(1982).Resource-constrained project scheduling with timeresource tradeoffs: the nonpreemptive case.Management Science,28,1199-1210.
54. Tseng, C.-C.(2008).Two heuristic algorithms for a multi-mode resource-constrained multi-project scheduling problem.Journal of Science and Engineering Technology,4,63-74.
55. Tsubakitani, S.,Deckro, R. F.(1990).A heuristic approach for multi-project scheduling with limited resources in the housing industry.European Journal of Operational Research,49,80-91.
56. Van Peteghem, V.,Vanhoucke, M.(2014).Van Peteghem An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances.European Journal of Operational research,235,62-72.
57. Van Peteghem, V.,Vanhoucke, M.(2010).Van Petegh A genetic algorithm for the preemptive and nonpreemptive multi-mode resource-constrained project scheduling problem.European Journal of Operational Research,201,409-418.
58. Vartouni, A. M.,Khanli, L. M.(2014).A hybrid genetic algorithm and fuzzy set applied to multimode resource-constrained project scheduling problem.Journal of Intelligent and Fuzzy Systems,26,1103-1112.
59. Wauters, T.,Verbeeck, K.,De Causmaecker, P.,Berghe, G. V.(2015).A learning-based optimization approach to multi-project scheduling.Journal of Scheduling,18,61-74.
60. Wen, U.-P.,Hsu, S.-T.(1991).Linear bi-level programming problems-a review.Journal of Operational Research Society,42,25-133.
61. Werner, B.(1987).An interactive fuzzy programming system.Fuzzy Sets and Systems,23,131-147.
62. Yang K.-K.,Sum, C.-C.(1997).An evaluation of due date, resource allocation, project release, and activity scheduling rules in a multiproject environment.European Journal of Operational Research,103,139-154.
63. Yang, K.-K.,Sum, C.-C.(1993).A comparison of resource allocation and activity scheduling rules in a dynamic multi-project scheduling environment.Journal of Operations Management,11,207-218.
64. Zheng, Z.,Guo, Z.,Zhu, Y.,Zhang, X.(2014).A critical chains based distributed multi-project scheduling approach.Neurocomputing,143,282-293.