Comparative analysis on approximation algorithms for the resource constrained project scheduling problem

Coelho, José; Valadares, Luis Tavares

http://hdl.handle.net/10400.2/1940

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
PMS2002.pdf		166.16 KB	Adobe PDF	Download

Send Feedback

Authors

Coelho, José

Valadares, Luis Tavares

Abstract(s)

In Resource Constrained Project Scheduling Problem (RCPSP) exact algorithms can only solve small instances, and several approximation algorithms have been proposed that can solve large instances with a quasi-optimal solution. So far there is no comparative analysis of several algorithms running on the same machine, with equal time limit and large instances; this is our main goal. A new performance indicator is proposed that is not affected by the presence of simple problems in the instance set. The instance set was built by assembling the main sets in the literature and also JobShop and FlowShop instances transformed to RCPSP. In this work 30 meta-heuristics were implemented, obtaining a total of 159.364.665 solutions evaluated of RCPSP.

Description

Project Management and Scheduling - PMS. Valência, 3-5 Abril de 2002

Keywords

RCPSP Comparative analysis Performance indicator

URI

http://hdl.handle.net/10400.2/1940

Citation

Coelho, José; Tavares, Luis Valadares - Comparative analysis on approximation algorithms for the resource constrained project scheduling problem, In "Eighth International Workshop on Project Management and Schduling". [S.l.]: Euro Working Group on Project Management and Scheduling, 2002. 6 p.