A Low-cost Multicomputer for solving the RCPSP

• Autorzy: Pawiński G. , Sapiecha K.

Identyfikatory

DOI

10.17951/ai.2016.16.1.50

• Języki publikacji: EN

Abstrakty

EN

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 nding 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 ecient as on more expensive cluster. Moreover, it has balanced load and scales well.

Słowa kluczowe

EN

multicomputer; RCPSP

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2016
• Tom: Vol. 16, no. 1
• Strony: 50--61
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Pawiński G.

• Department of Computer Science, Kielce University of Technology

autor

Sapiecha K.

• Department of Computer Science, Kielce University of Technology

Bibliografia

• [1] Alcaraz J., Maroto C., A robust genetic algorithm for resource allocation in project scheduling, Annals of Operations Research 102 (2001): 83109.
• [2] Bouleimen K., Lecocq H., A new ecient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple modes version, European Journal of Operational Research 149 (2003): 26828,
• [3] Brucker, P., Knust, S., Schoo, A., Thiele, O., A branch-andbound algorithm for the resource-constrained project scheduling problem, European Journal of Operational Research 107 (1998): 272288.
• [4] Demeulemeester, E. L., Herroelen, W. S., New benchmark results for the resource-constrained project scheduling problem, Management Science 43 (1997): 14851492.
• [5] Demeulemeester, E. L., Herroelen, W. S., Project Scheduling. A Research Handbook, Springer (2002).
• [6] Deniziak, S., Cost-ecient synthesis of multiprocessor heterogeneous systems, Control and Cybernetics 33 (2004): 341355.
• [7] Hartmann, S., A Competitive Genetic Algorithm for Resource-Constrained Project Scheduling, Naval Research Logistics 45 (1998): 733750.
• [8] Hartmann, S., Kolisch, R., Experimental evaluation of state-ofthe-art heuristics for the resource-constrained project scheduling problem, European Journal of Operational Research 127 (2000): 394407.
• [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): 2337.
• [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): 714729.
• [12] Pawiński G., Sapiecha K., Resource allocation optimization in Critical Chain Method, Annales Universitatis Mariae Curie- Sklodowska sectio Informaticales 12(1) (2012): 1729.
• [13] Pawiński G., Sapiecha K., Cost-ecient 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): 157163.
• [14] Pawiński G., Sapiecha K., Cost-ecient project management based on critical chain method with partial availability of resources, Control and Cybernetics 43 (2014): 95109.
• [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 Optimisation 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): 796801.
• [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): 5984.
• [19] Steyn, H., An investigation into the fundamentals of critical chain project management, International Journal of Project Management 19 (2000): 363-369.
• [20] TomassiniM., 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): 113133.
• [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 Optimisation, Journal of Parallel and Distributed Computing 62(9) (2002): 14211432.
• [24] Foster, I., Designing and building parallel programs: concepts and tools for parallel software engineering, Addison Wesley: Reading, MA (1995).

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).