In this paper we present a hybrid strategy developed using genetic algorithms (GAs), simulated annealing (SA), and quantum simulated annealing techniques (QSA) for the discrete time–cost trade-off problem (DTCTP). In the hybrid algorithm (HA), SA is used to improve hill-climbing ability of GA. In addition to SA, the hybrid strategy includes QSA to achieve enhanced local search capability. The HA and a sole GA have been coded in Visual C++ on a personal computer. Ten benchmark test problems with a range of 18 to 630 activities are used to evaluate performance of the HA. The benchmark problems are solved to optimality using mixed integer programming technique. The results of the performance analysis indicate that the hybrid strategy improves convergence of GA significantly and HA provides a powerful alternative for the DTCTP.
In scheduling of construction projects, the project duration can be compressed (crashed) by expediting some of its activities in several ways including; increasing crew size above the normal level, working overtime, or using alternative construction methods. The crashing alternatives come at an additional cost. This trade-off between time and cost has been studied extensively since development of the critical path method (Vanhoucke & Debels, 2007). The objective of time–cost trade-off problem is to identify the set (or sets) of time–cost alternatives that will provide the optimal schedule.
The early time–cost trade-off studies assumed the relation between time and cost to be continuous. However, in construction projects resources are usually available in discrete units, such as the number of equipment or the number of crews. Working overtime or implementing alternative construction methods also usually provide discrete crashing options. Due to its practical relevance, numerous methods have been suggested to solve the discrete time–cost trade-off problem (DTCTP). The methods can be classified in two groups; mathematical methods which search for exact solutions, and heuristic methods which search for near optimum solutions. Mixed integer programming is commonly implemented to find an exact solution for the DTCTP (Burns et al., 1996, Chassiakos and Sakellaropoulos, 2005, De et al., 1995 and Moussourakis and Haksever, 2004). Although DTCTP can be solved to optimality by mixed integer programming technique, it has been shown that DTCTP is strongly NP-hard and, any exact solution algorithm would very likely exhibit exponential worst-case complexity (De, Dunne, Ghosh, & Wells, 1997). As a result, numerous researches in recent years have focused on adopting meta-heuristic procedures to achieve optimal or near-optimal solutions for the DTCTP.
Genetic algorithms (GAs) are among the most commonly implemented meta-heuristics for the DTCTP (El-Rayes and Kandil, 2005, Fallah-Mehdipour et al., 2012, Feng et al., 1997, Hegazy, 1999, Li and Love, 1997 and Zheng et al., 2005). GAs are important meta-heuristic optimization algorithms but they have limited hill climbing ability for escaping from local minima hence, they may suffer from premature convergence (Leung et al., 1997 and Rudolph, 1994). Previous research results indicate that the sole GAs usually performs poorly for solving the DTCTP compared to alternative meta-heuristics. In a comparison of five evolutionary based algorithms, GAs showed the worse performance for the DTCTP (Elbeltagi, Hegazy, & Grierson, 2005). Comparison of GAs with the ant colony optimization (ACO) revealed similar results, indicating poor performance of GAs for achieving successful optimal or near-optimal results (Ng and Zhang, 2008 and Xiong and Kuang, 2008). Hence, alternative meta-heuristics have been suggested in recent years for the DTCTP. Yang, Yuan, Yuan, and Mao (2007) and Zhang and Li (2010) employed particle swarm optimization, Xiong and Kuang, 2008 and Ng and Zhang, 2008, and Afshar, Ziaraty, Kaveh, and Sharifi (2009) applied ant colony optimization for the DTCTP.
This paper presents a hybrid strategy based on genetic algorithms, simulated annealing, and quantum simulated annealing techniques for the DTCTP. The main goal of hybrid strategy is to achieve a successful algorithm for the DTCTP by including the complementary strengths of several algorithms. The remainder of the paper is organized as follows: In Section 2, the hybrid strategy is presented. Benchmark problems are described in Section 3 and computational tests are included in Section 4. Finally, concluding remarks are made in Section 5.
