Constructive heuristics for technology-driven Resource Constrained Scheduling Problem

• Autorzy: Paweł B. Myszkowski , Michał Przewoźniczek , Marek Skowroński
• Języki publikacji: EN

Abstrakty

EN

In this paper, we define a new practical technology-driven Resource Constrained Scheduling Problem (tRCPSP). We propose three approaches, applying constructive heuristics to tackle effectively the practical application of RCPSP. In the RCPSP formulation, the constraints are defined to design the tasks in the spaces constructed by non- and renewable resources, without violating the precedence relationships and technologies in real world problem that exists in Plastic and Rubber Processing company. The difficulty of t-RCPSP is NP-hard and we proposed three constructive specialized methods: duration based heuristics (DBH), locally optimal resource usage PEC and NEH heuristic adaptation. The paper presents results of computational experiments that show the effectiveness of the proposed approaches.(original abstract)

Słowa kluczowe

EN

Heuristics methods; Technology

PL

Metody heurystyczne; Technologia

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 5
• Strony: 119--127

Twórcy

autor

Paweł B. Myszkowski

• Wrocław University of Technology, Wrocław, Poland

autor

Michał Przewoźniczek

• Wrocław University of Technology MP2 company, Wrocław, Poland

autor

Marek Skowroński

• Wrocław University of Technology, Wrocław, Poland

Bibliografia

• Blazewicz J., Lenstra J.K., Rinnooy Kan A.H.G.; Scheduling subject to resource constraints: Classification and complexity, Discrete Applied Mathematics (5), pp. 11-24, 1983.
• Bouleimen K., Lecocq H.; A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version, Eur. J of Operational Research (149), pp. 268-281, 2003.
• Brucker P., Drexl A., Mohring R., Neumann K., Pesch E.; Resource- constrained project scheduling: Notation, classification, models, and methods, European Journal of Oper. Research (112), pp. 3-41, 1998.
• Dorigo M.; Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions of Evolutionary Computation (1/1), pp. 53-66, 1997.
• Hartmann S.; A competitive genetic algorithm for resource-constrained project scheduling, Naval Research Logistics (45), pp. 733-750, 1998.
• Hartmann S., Briskorn D., A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research 207(2010), pp.1-14. 2010.
• Kolisch R., Hartmann S., Experimental evaluation of state-of-the-art heuristics for the resource- constrained project scheduling problem, European Journal of Oper. Research (127), pp. 394-407, 2000.
• Kolisch R., Hartmann S., Experimental investigation of heuristics for resource-constrained project scheduling: An update, Euro. Journal of Oper. Research (174), pp. 23-37, 2006.
• Liang Y., Chen A., Kao W., Chyu C.; An Ant Colony approach to Resource-Constrained Project Scheduling Problems, Proc of the 5th Asia Pacific Indust. Eng. and Manag Systems Conf 2004, pp. 31.5.1- 31.5.10, 2004.
• Luo S., Wang C., Wang J.; Ant Colony Optimization for ResourceConstrained Project Scheduling with Generalized Precedence Relations, Proc of the 15th IEEE International Conference on Tools with A(ICTAI03), pp. 284-289, 2003.
• Merkle D., Mittendorf M., Schmeck H.; Ant Colony Optimization for Resource-Constrained Project Scheduling, IEEE Transactions on Evolutionary Computation (6/4), pp. 333-346, 2002.
• Myszkowski P.B., Skowroński M. E., Myszkowski P. B., Kwiatek P., Adamski M., Tabu Search approach for Multi-Skill ResourceConstrained Project Scheduling Problem, Annals of Computer Science and Information Systems Volume 1, Proc. of the 2013 FeDCSIS Confeences, pp. 153-158, 2013.
• Myszkowski P.B., Skowronski M.E., Olech Ł.P. and Oślizło K., Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem, Soft Computing Journal, Sep 2014.
• Nawaz, M., Enscore, J., Ham, I.: A Heuristic Algorithm for the M-machine, N-task Flow-shop Sequencing Problem. Omega-Int. J. Manage. S. 11(1), 91-95 (1983)
• Pan H.I., Hsaio P.W., Chen K.Y.; A study of project scheduling optimization using Tabu Search algorithm, Engineering Applications of Artificial Intelligence (21), pp. 1101-1112, 2008.
• Pan N.H., Lee M.L., Chen K.Y.; Improved Tabu Search Algorithm Application in RCPSP, Proceedings of the International MultiConference of Engineers and Computer Scientists (Vol I), 2009.
• Santos M., Tereso A. P.; On the multi-mode, multi-skill resource constrained project scheduling problem - computational results, Soft Computing in Industrial Applications, Advances in Intelligent and Soft Computing (96), pp. 239-248, 2011.
• Skowroński M. E., Myszkowski P. B., Specialized genetic operators for Multi-Skill Resource-Constrained Project Scheduling Problem, 19th Inter. Conference on Soft Computing Mendel 2013, pp. 57-62, 2013.
• Skowroński M. E., Myszkowski P. B., Podlodowski L., Novel heuristic solutions for Multi-Skill Resource- Constrained Project Scheduling Problem, Annals of Computer Science and Information Systems Volume 1, Proc. of the 2013 Federated Conference on Computer Science and Information Systems, pp. 159-166, 2013.
• Thomas P. R., Salhi S.; A Tabu Search Approach for the Resource Constrained Project Scheduling Problem, Journal of Heuristics (4), pp. 123-139, 1998.
• Valls V., Ballestin F., Quintanilla S.; A hybrid genetic algorithm for the resource-constrained project scheduling problem, European Journal of Operational Research (185), pp. 495-508, 2008.
• Zhang H., Xu H., Peng W., A Genetic Algorithm for Solving RCPSP, 2008 International Symposium on Computer Science and Computational Technology, pp. 246-249, 2008.
• Zhang H., Li H., Tam C.; Particle swarm optimization for resource- constrained project scheduling, In- ter. Jour. of Project Management (24), pp. 83-92, 2006.
• Zhang K., Zhao G., Jiang J.; Particle Swarm Optimization Method for Resource-Constrained Project Scheduling Problem, The Ninth International Conference on Electronic Measurement & Instruments ICEMI2009, pp. 792-796, 2009.
• Ziarati K., Akbari R., Zeighami V.; On the performance of bee algorithms for resource-constrained project scheduling problem, Applied Soft Computing (11), pp. 3720-3733, 2011

Identyfikatory

DOI

10.15439/2015F389