Abstract: In the paper it is shown that time necessary to solve the NP-hard Resource-Constrained Project Scheduling Problem (RCPSP) could be considerably reduced using a low-cost multicomputer. We consider an extension of the problem when resources are only partially available and a deadline is given but the cost of the project should be minimized. In such a case finding an acceptable solution (optimal or even semi-optimal) is computationally very hard. To reduce this complexity a distributed processing model of a metaheuristic algorithm, previously adapted by us for working with human resources and the CCPM method, was developed. Then, a new implementation of the model on a low-cost multicomputer built from PCs connected through a local network was designed and compared with regular implementation of the model on a cluster. Furthermore, to examine communication costs, an implementation of the model on a single multi-core PC was tested, too. The comparative studies proved that the implementation is as efficient as on more expensive cluster. Moreover, it has balanced load and scales well.
B I B L I O G R A F I A[1] Alcaraz J., Maroto C., A robust genetic algorithm for resource allocation in project scheduling, Annals of Operations Research 102 (2001): 83 109.
[2] Bouleimen K., Lecocq H., A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple modes version, European Journal of Operational Research 149 (2003): 268 28,
[3] Brucker, P., Knust, S., Schoo, A., Thiele, O., A branch-and-bound algorithm for the resource-constrained project scheduling problem, European Journal of Operational Research 107 (1998):272 - 288.
[4] Demeulemeester, E. L., Herroelen, W. S., New benchmark results for the resource-constrained project scheduling problem, Management Science 43 (1997): 1485 - 1492.
[5] Demeulemeester, E. L., Herroelen, W. S., Project Scheduling. A Research Handbook, Springer (2002).
[6] Deniziak, S., Cost-efficient synthesis of multiprocessor heterogeneous systems, Control and Cybernetics 33 (2004): 341 355.
[7] Hartmann, S., A Competitive Genetic Algorithm for Resource Constrained Project Scheduling, Naval Research Logistics 45 (1998): 733 750.
[8] Hartmann, S., Kolisch, R., Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem, European Journal of Operational Research 127 (2000): 394 407
[9] Kolish R., Sprecher A., PSPLIB - A project scheduling library, European Journal of Operational Research 96 1996: 205-216.
[10] Kolisch R., Hartmann S., Experimental investigation of heuristics for resource-constrained project scheduling: An update, European Journal of Operational Research 174 (2006): 23 - 37.
[11] Mingozzi, A., Maniezzo, V., Ricciardelli, S., Bianco, L., An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation, Management Science 44 (1998): 714 - 729.
[12] Pawiński G., Sapiecha K., Resource allocation optimization in Critical Chain Method, Annales Universitatis Mariae Curie-Sklodowska sectio Informaticales 12(1) (2012): 17 - 29.
[13] Pawiński G., Sapiecha K., Cost-efficient Project Management Based on Distributed Processing Model, Proceedings of the 21th International Euromicro Conference on Parallel, Distributed and Network-Based Processing, IEEE Computer Society (2013): 157 - 163.
[14] Pawiński G., Sapiecha K., Cost-efficient project management based on critical chain method with partial availability of resources, Control and Cybernetics 43 (2014): 95 109.
[15] Niar, S., Freville, A., A parallel tabu search algorithm for the 0-1 multidimensional knapsack problem, Proceedings of the 11th International Parallel Processing Symposium (1997): 512- 516.
[16] Randall, M. Abramson, D., A General Parallel Tabu Search Algorithm for Combinatorial Optimization Problems, Proceedings of the 6th Australasian Conference on Parallel and Real Time Systems, Cheng, W. and Sajeev, A. (eds), Springer-Verlag (1999): 68-79.
[17] He,Y., Qiu, Y., Liu, G. Lei, K., A parallel adaptive tabu search approach for traveling salesman problems, Proceedings of 2005 IEEE International Conference on Natural Language Processing and Knowledge Engineering (2005): 796 801.
[18] Malek M., Guruswamy M., Pandya M., Owens H., Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem, Annals of Operations Research 21 (1989): 59 84.
[19] Steyn, H., An investigation into the fundamentals of critical chain project management, International Journal of Project Management 19 (2000): 363-369.
[20] Tomassini M., Parallel and distributed evolutionary algorithms: A review, In P. Neittaanmki K. Miettinen, M. Mkel and J. Periaux, editors, Evolutionary Algorithms in Engineering and Computer Science, J. Wiley and Sons, Chichester (1999): 113 133.
[21] Koza J.R., Genetic Programming: On the Programming of Computers by Means of Natural Selection, The MIT Press, Sixth printing (1998).
[22] Koza J.R., Keane M.A., Streeter M.J., Mydlowec W., Yu J.,Lanza G., Gentic Programming IV, Kluwer Academic Publishers (2003).
[23] Randall M., Lewis A., A Parallel Implementation of Ant Colony Optimization, Journal of Parallel and Distributed Computing 62(9) (2002): 1421 1432.
[24] Foster, I., Designing and building parallel programs: concepts and tools for parallel software engineering, Addison Wesley: Reading, MA (1995). 
Pełny tekst 
DOI