A branch and bound algorithm for project scheduling problem with spatial resource constraints. (English) Zbl 1394.90276
Summary: With respect to the block assembly schedule in a shipbuilding enterprise, a spatial resource constrained project scheduling problem (SRCPSP) is proposed, which aims to minimize the makespan of a project under the constraints of the availability of a two-dimensional spatial resource and the precedence relationship between tasks. In order to solve SRCPSP to the optimum, a branch and bound algorithm (BB) is developed. For the BB-SRCPSP, first, an implicitly enumerative branch scheme is presented. Secondly, a precedence based lower bound, as well as an effective dominance rule, is employed for pruning. Next, a heuristic based algorithm is used to decide the order of a node to be selected for expansion such that the efficiency of the algorithm is further improved. In addition, a maximal space based arrangement is applied to the configuration of the areas required each day in an available area. Finally, the simulation experiment is conducted to illustrate the effectiveness of the BB-SRCPSP.
References:
| [1] | Hartmann, S.; Briskorn, D., A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 207, 1, 1-14, (2010) · Zbl 1205.90123 · doi:10.1016/j.ejor.2009.11.005 |
| [2] | Brucker, P.; Knust, S., Linear programming and constraint propagation-based lower bound for the RCPSP, European Journal of Operational Research, 127, 2, 355-362, (2000) · Zbl 0990.90055 · doi:10.1016/S0377-2217(99)00489-0 |
| [3] | Kolisch, R.; Padman, R., An integrated survey of deterministic project scheduling, Omega, 29, 3, 249-272, (2001) · doi:10.1016/S0305-0483(00)00046-3 |
| [4] | He, Z.; Wang, N.; Jia, T.; Xu, Y., Simulated annealing and tabu search for multi-mode project payment scheduling, European Journal of Operational Research, 198, 3, 688-696, (2009) · Zbl 1176.90260 · doi:10.1016/j.ejor.2008.10.005 |
| [5] | Mika, M.; Waligóra, G.; Weglarz, J., Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times, European Journal of Operational Research, 187, 3, 1238-1250, (2008) · Zbl 1137.90508 · doi:10.1016/j.ejor.2006.06.069 |
| [6] | Hartmann, S., A self-adapting genetic algorithm for project scheduling under resource constraints, Naval Research Logistics, 49, 5, 433-448, (2002) · Zbl 1013.90062 · doi:10.1002/nav.10029 |
| [7] | Agarwal, A.; Colak, S.; Erenguc, S., A Neurogenetic approach for the resource-constrained project scheduling problem, Computers and Operations Research, 38, 1, 44-50, (2011) · Zbl 1231.90170 · doi:10.1016/j.cor.2010.01.007 |
| [8] | Agarwal, R.; Tiwari, M. K.; Mukherjee, S. K., Artificial immune system based approach for solving resource constraint project scheduling problem, The International Journal of Advanced Manufacturing Technology, 34, 5-6, 584-593, (2007) · doi:10.1007/s00170-006-0631-2 |
| [9] | Chen, W.; Zhang, J.; Chung, H. S.; Huang, R. Z.; Liu, O., Optimizing discounted cash flows in project scheduling-an ant colony optimization approach, IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, 40, 1, 64-77, (2010) · doi:10.1109/TSMCC.2009.2027335 |
| [10] | Zhang, H.; Li, X.; Li, H.; Huang, F., Particle swarm optimization-based schemes for resource-constrained project scheduling, Automation in Construction, 14, 3, 393-404, (2005) · doi:10.1016/j.autcon.2004.08.006 |
| [11] | Ranjbar, M.; De Reyck, B.; Kianfar, F., A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling, European Journal of Operational Research, 193, 1, 35-48, (2009) · Zbl 1152.90464 · doi:10.1016/j.ejor.2007.10.042 |
| [12] | Klein, R.; Scholl, A., PROGRESS: optimally solving the generalized resource-constrained project scheduling problem, Mathematical Methods of Operations Research, 52, 3, 467-488, (2000) · Zbl 1023.90028 · doi:10.1007/s001860000093 |
| [13] | Coelho, J.; Vanhoucke, M., Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers, European Journal of Operational Research, 213, 1, 73-82, (2011) · Zbl 1237.90086 · doi:10.1016/j.ejor.2011.03.019 |
| [14] | Lova, A.; Tormos, P.; Cervantes, M.; Barber, F., An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes, International Journal of Production Economics, 117, 2, 302-316, (2009) · doi:10.1016/j.ijpe.2008.11.002 |
| [15] | Hu, S. C.; Xu, X. F., A production scheduling algorithm for cost optimization, Computer Integrated Manufacturing Systems, 9, 9, 735-739, (2003) |
| [16] | Sobel, M. J.; Szmerekovsky, J. G.; Tilson, V., Scheduling projects with stochastic activity duration to maximize expected net present value, European Journal of Operational Research, 198, 3, 697-705, (2009) · Zbl 1176.90264 · doi:10.1016/j.ejor.2008.10.004 |
| [17] | Neumann, K.; Zimmermann, J., Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints, European Journal of Operational Research, 127, 2, 425-443, (2000) · Zbl 0990.90058 · doi:10.1016/S0377-2217(99)00498-1 |
| [18] | Waligóra, G., Discrete-continuous project scheduling with discounted cash flows—a tabu search approach, Computers & Operations Research, 35, 7, 2141-2153, (2008) · Zbl 1177.90189 · doi:10.1016/j.cor.2006.09.022 |
| [19] | Yin, Y.; Cheng, T. C. E.; Wu, C.-C., Scheduling with time-dependent processing times, Mathematical Problems in Engineering, 2014, (2014) · doi:10.1155/2014/201421 |
| [20] | Yin, Y. Q.; Wu, W. H.; Cheng, T. C. E.; Wu, C. C., Single-machine scheduling with time-dependent and position-dependent deteriorating jobs, International Journal of Computer Integrated Manufacturing, (2014) · doi:10.1080/0951192X.2014.900872 |
| [21] | Yin, Y.; Cheng, S.-R.; Wu, C.-C., Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties, Information Sciences, 189, 282-292, (2012) · Zbl 1247.90165 · doi:10.1016/j.ins.2011.11.035 |
| [22] | Yin, Y.; Xu, D.; Sun, K.; Li, H., Some scheduling problems with general position-dependent and time-dependent learning effects, Information Sciences, 179, 14, 2416-2425, (2009) · Zbl 1166.90342 · doi:10.1016/j.ins.2009.02.015 |
| [23] | Yin, Y. Q.; Liu, M.; Hao, J. H.; Zhou, M. C., Single-machine scheduling with job-position-dependent learning and time-dependent deterioration, IEEE Transactions on Systems, Man, and Cybernetics: Systems and Humans, 42, 1, 192-200, (2012) · doi:10.1109/TSMCA.2011.2147305 |
| [24] | Lee, K. J.; Lee, J. K.; Choi, S. Y., A spatial scheduling system and its application to shipbuilding: DAS-CURVE, Expert Systems with Applications, 10, 3-4, 311-324, (1996) · doi:10.1016/0957-4174(96)00010-3 |
| [25] | Park, C.; Chung, K.-H.; Park, J.-C.; Cho, K.-K.; Baek, T.-H.; Son, E.-I., A spatial scheduling application at the block paint shop in shipbuilding: the HYPOS project, Production Planning and Control, 13, 4, 342-354, (2002) · doi:10.1080/095372802760108309 |
| [26] | Varghese, R.; Yoon, D. Y., Dynamic spatial block arrangement scheduling in shipbuilding industry using genetic algorithm, Proceedings of the IEEE 3rd International Conference on Industrial Informatics (INDIN ’05), IEEE · doi:10.1109/INDIN.2005.1560417 |
| [27] | Koh, S.; Logendran, R.; Choi, D.; Woo, S., Spatial scheduling for shape-changing mega-blocks in a shipbuilding company, International Journal of Production Research, 49, 23, 7135-7149, (2011) · doi:10.1080/00207543.2010.535863 |
| [28] | Steiger, C.; Walder, H.; Platzner, M., Operating systems for reconfigurable embedded platforms: online scheduling of real-time tasks, IEEE Transactions on Computers, 53, 11, 1393-1407, (2004) · doi:10.1109/TC.2004.99 |
| [29] | Dell’Amico, M.; Díaz, J. C. D.; Iori, M., The bin packing problem with precedence constraints, Operations Research, 60, 6, 1491-1504, (2012) · Zbl 1269.90092 · doi:10.1287/opre.1120.1109 |
| [30] | Kolisch, R.; Sprecher, A., PSPLIB—a project scheduling problem library, European Journal of Operational Research, 96, 1, 205-216, (1997) · Zbl 0947.90587 · doi:10.1016/S0377-2217(96)00170-1 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
