An Energy-efficient Mathematical Model for the Resource-constrained Project Scheduling Problem: An Evolutionary Algorithm

Document Type : Research Paper

Authors

Department of Industrial Engineering, Islamic Azad University, Tehran North Branch, Tehran, Iran

Abstract

In this paper, we propose an energy-efficient mathematical model for the resource-constrained project scheduling problem to optimize makespan and consumption of energy, simultaneously. In the proposed model, resources are speed-scaling machines. The problem is NP-hard in the strong sense. Therefore, a multi-objective fruit fly optimization algorithm (MOFOA) is developed. The MOFOA uses the VIKOR as a multi-criteria decision making (MCDM) method to rank solutions in vision-based search procedure. The proposed algorithm is applied to small, medium and large size problems to evaluate its performance. Comprehensive numerical tests are conducted to evaluate the performance of the MOFOA in comparison to three other meta-heuristics in terms of convergence, diversity and computation time. The experimental results significantly show that the proposed algorithm can surpass other methods in terms of most of the metrics. Besides, the results of meta-heuristics are compared with the outputs of GAMS software for small size problems.

Keywords

Main Subjects

References

Afruzi, E., Najafi, A. A., Roghanian, E., & Mazinani, M. (2014). A Multi-Objective Imperialist Competitive Algorithm for solving discrete time, cost and quality trade-off problems with mode-identity and resource-constrained situations. Computers & Operations Research, 50, 80-96.
Bampis, E., Dürr, C., Kacem, F., & Milis, I. (2012). Speed-scaling with power down scheduling for agreeable deadlines. Sustainable Computing: Informatics and Systems, 2(4), 184-189.
Bashiri, M., Badri, H., & Talebi, J. (2012). A new approach to tactical and strategic planning in production–distribution networks. Applied Mathematical Modelling, 36, 1703-1717.
Blazewicz, J., Lenstra, J. K., & Kan, A. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5, 11-24.
Che, A., Wu, X., Peng, J., & Yan, P. (2017). Energy-efficient bi-objective single-machine scheduling with power-down mechanism. Computers & Operations research, 85, 172-183.
Che, A., Zhang, S., & Wu, X. (2017). Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs. Journal of Cleaner Production, 156, 688-697.
Dai, M., Tang, D., Giret, A., Salido, M. A., & Li, W. D. (2013). Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing, 29(5), 418-429.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6, 182-197.
Ding, J. Y., Song, S. J., & Wu, C. (2016). Carbon-efficient scheduling of flow shops by multi-objective optimization. European Journal of Operational Research, 248(3), 758-771.
Fang, K., Uhan, N. A., Zhao, F., & Sutherland, J.W. (2011). A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. Journal of Manufacturing Systems, 30(4), 234-240.
Fang, K., Uhan, N. A., Zhao, F., & Sutherland, J. W. (2016). Scheduling on a single machine under time-of-use electricity tariffs. Annals of Operations Research, 238(1-2), 199-227.
Fang, C., & Wang, L. (2012). An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem. Computers & Operations Research, 39 (5), 890-901.
Gahm, C., Denz, F., Dirr, M., & Tuma, A. (2016). Energy-efficient scheduling in manufacturing companies: A review and research framework. European Journal of Operational Research, 248(3), 744-757.
Gao, J., Chen, R., & Deng, W. (2013). An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem. International Journal of Production Research, 51, 641-651.
Huang, L., Wang, G. C., Bai, T., & Wang, Z. (2017). An improved fruit fly optimization algorithm for solving traveling salesman problem. Frontiers of Information Technology & Electronic Engineering, 18(10), 1525-1533.
Kadri, R. L., & Boctor, F. F. (2018). An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case. European Journal of Operational Research, 265(2), 454-462.
Kolisch, R., & Sprecher, A. (1996). PSPLIB - A project scheduling problem library. European Journal of Operational Research, 96(1), 205-216.
Liu, G. S., Zhou, Y., & Yang, H. D. (2017). Minimizing energy consumption and tardiness penalty for fuzzy flow shop scheduling with state-dependent setup time. Journal of Cleaner Production, 147, 470-484.
Liu, Y., Dong, H., Lohse, N., Petrovic, S., & Gindy, N. (2014). An investigation into minimising total energy consumption and total weighted tardiness in job shops. Journal of Cleaner Production, 65, 87-96.
Lu, C., Gao, L., Li, X., Pan, Q., & Wang, Q. (2017). Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm. Journal of Cleaner Production, 144, 228-238.
Luo, H., Du, B., Huang, G. Q., Chen, H., & Li, X. (2013). Hybrid flow shop scheduling considering machine electricity consumption cost. International Journal of Production Economics, 146(2), 423-439.
Mansouri, S. A., Aktas, E., & Besikci, U. (2016). Green scheduling of a two-machine flowshop: Trade-off between makespan and energy consumption. European Journal of Operational Research, 248(3), 772-788.
Mehdizadeh, E., Niaki, S.T.A, Hemati, M. (2018). A bi-objective aggregate production planning problem with learning effect and machine deterioration: Modeling and solution. Computers & Operations research, 91, 21-36.
Merkert, L., Harjunkoski, I., Isaksson, A., Saynevirta, S., Saarela, A., & Sand, G. (2015). Scheduling and energy – Industrial challenges and opportunities. Computers & Chemical Engineering, 72, 183-198.
Mokhtari, H., & Hasani, A. (2017). An energy-efficient multi-objective optimization for flexible job-shop scheduling problem. Computers & Chemical Engineering, 104, 339-352.
Mori, M., Fujishima, M., Inamasu, Y., & Oda, Y. (2011). A study on energy efficiency improvement for machine tools. CIRP Annals – Manufacturing Technology, 60(1), 145-148.
Mouzon, G., & Yildirim, M. B. (2008). A framework to minimize total energy consumption and total tardiness on a single machine. International Journal of Sustainable Engineering, 1(2), 105-116.
Opricovic, S., & Tzeng, G. H. (2007). Extended VIKOR method in comparison with outranking methods. European Journal of Operational Research, 178, 514–529.
Pargar, F., Zandieh, M., Kauppila, O., & Kujala, J. (2018). The effective of worker learning on scheduling jobs in a hybrid flow shop: A bi-objective approach. Journal of Systems Science and Systems Engineering, 27(3), 265-291.
Rahmati, S. H. A., Hajipour, V., & Niaki, S. T. A. (2013). A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem. Applied Soft Computing, 13, 1728-1740.
Schott, J. R. (1995). Fault tolerant design using single and multicriteria genetic algorithms optimization (unpublished master's thesis). Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA.
Shrouf, F., Ordieres-Mere, J., Garcia-Sanchez, A., & Ortega-Mier, M. (2014). Optimizing the production scheduling of a single machine to minimize total energy consumption costs. Journal of Cleaner Production, 67, 197-207.
Tang, D., Dai, M., Salido, M. A., & Giret, A. (2016). Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization. Computers in Industry, 81, 82-95.
Wang, S., Liu, M., Chu, F., & Chu, C. (2016). Bi-objective optimization of a single machine batch scheduling problem with energy cost consideration. Journal of Cleaner Production, 137, 1205-1215.
Wang, L., & Zheng, X. L. (2018). A knowledge-guided multi-objective fruit fly optimization algorithm for the multi-skill resource constrained project scheduling problem. Swarm and Evolutionary Computation, 38, 54-63.
Yan, J., Li, L., Zhao, F., Zhang, F., Zhao, Q. (2016). A multi-level optimization approach for energy-efficient flexible flow shop scheduling. Journal of Cleaner Production, 137, 1543-1552.
Zareei, M., & Hassan-Pour, H. A. (2015). A multi-objective resource-constrained optimization of time-cost trade-off problems in scheduling project. Iranian Journal of Management Studies, 8(4), 653-685.
Zhai, Y., Biel, K., Zhao, F., & Sutherland, J. W. (2017). Dynamic scheduling of a flow shop with on-site wind generation for energy cost reduction under real time electricity pricing. CIRP Annals, 66(1), 41-44.
Zhang, R., & Chiong, R. (2016). Solving the energy-efficient job shop scheduling problem: a multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption. Journal of Cleaner Production, 112, 3361-3375.
Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of multi objective evolutionary algorithms: Empirical results. Evolutionary Computation Journal, 8, 125–148.
Zitzler, E., & Thiele, L. (1998). Multi-objective optimization using evolutionary algorithms—a comparative case study. International Conference on Parallel Problem Solving from Nature. Springer, Berlin, Heidelberg, pp. 292–301, DOI: https://doi.org/10.1007/BFb0056872.
Interdisciplinary Journal of Management Studies (Formerly known as Iranian Journal of Management Studies)
Volume 12, Issue 1
January 2019
Pages 91-119

Files

Share

How to cite

Statistics