Document Type : Research Paper


M.Sc. in Industrial Engineering, Faculty of Industrial Engineering, Bu-Ali Sina University, Hamadan, Iran


In general, numerous studies have paid a special attention to machine planning, job allocating and job sequencing in scheduling problems to optimize makespan. Due to the relation among economy, energy and environmental concerns, energy use is one of the most important issues in different systems planning. In this paper, a scheduling of heterogeneous parallel machines is studied, in which the job process speed on every machine is settable. Since there is a direct link between used energy of machines and process speed, the purpose of the paper is to minimize total used energy and tardiness-related costs in delivering customers' demand. In order to optimizing the problem, two meta-heuristic algorithms, Memetic algorithm and Genetic algorithm, are developed, finally the results of both algorithms are analyzed and then compared to each other as well as to the results of the GAMS optimization software.


فخرزاد، محمد باقر. رجائی، بهنام. (1396). « نگهداری پیشگیرانه در زمانبندی ماشین­های موازی نامرتبط با احتساب اثر زوال و زمان آماده سازی». مجله مطالعات مدیریت صنعتی، دوره 15، شماره 45.
Ada Che, Shibohua Zhang, Xueqi Wu. (2017). Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs. Journal of cleaner production.
Ali Husseinzadeh Kashan, Behrooz Karimi. 2008. A discrete particle swarm optimization algorithm for scheduling parallel machines. Computers & Industrial Engineering 56 (2009) 216–223.
Anghinofi, D., & Paolucci, M. (2007). Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach. Computers & Operations Research, 34(11), 3471–3490.
Balin, S. (2011). Non-identical parallel machine scheduling using genetic algorithm. Expert System with Applications, 38, 6814–6821.
Despeisse, M., Ball, P.D., Evans, S., Levers, A., 2012. Industrial ecology at factory level e a conceptual model. J. Clean. Prod. 31, 30e39.
Ding, J.Y., Song, S., Zhang, R., Chiong, R., (2016). Parallel machine scheduling under time-of-use electricity prices: new models and optimization approaches. IEEE Transactions on Automation Science & Engineering 13(2), 1138-1154.
Dror, M., Stern, H.I., and Lenstra, J.K. (1987), "Parallel machine scheduling: Processing rates dependent on number of jobs in operation", Management Science 33, 1001-1009.
Fadi Shrouf, Joaquin Ordieres-Meré, Alvaro García-Sánchez, Miguel Ortega-Mier.2013. Optimizing the production scheduling of a single machine to minimize total energy consumption costs.
Fang, K., Uhan, N., Zhao, F., Sutherland, J.W., 2011. A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. J. Manuf. Syst. 30, 234e240.
Fanjul-Peyro, L., Perea, F., Ruiz, R. (2017). Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources. European Journal of Operational Research 000 (2017) 1–12.
Garey, MR., & Johnson, DS. (1978). ‘‘Strong’’ NP-completeness results: Motivation, examples, and implications. Journal of the Association for Computing Machinery, 25(3), 499–508.
Hoogeveen, H., 2005. Multicriteria scheduling. Eur. J. Oper. Res. 167, 592e623.
Kim, D-W., Kim, K-H., Jang, W., & Chen, F. (2002). Unrelated parallel machine scheduling with setup times using simulated annealing. Robotics and ComputerIntegrated Manufacturing, 18, 223–231.
Kuei-Tang Fang, Bertrand M.T. Lin.2012. Parallel-machine scheduling to minimize tardiness penalty and power cost. Computers & Industrial Engineering 64 (2013) 224–234.
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.
Lin, C.-H., Liao, C.-J., 2008. Makespan minimization for multiple uniform machines. Comput. Ind. Eng. 54, 983e992.
Lin, Y. K., Pfund, M. E., & Fowler, J. W. (2011). Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problem. Computers & Operations Research, 38(6), 901–916.
Liu, Y., Dong, H., Lohse, N., Petrovic, S., Gindy, N., 2013. An investigation into minimizing total energy consumption and total weighted tardiness in job shops. J. Clean. Prod., 1e10.
Moon, J.Y., Shin, K., Park, J., (2013). Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency. International Journal of Advanced Manufacturing Technology 68, 523-535.
Mouzon, G., Yildirim, M.B., Twomey, J., 2007. Operational methods for minimization of energy consumption of manufacturing equipment. Int. J. Prod. Res. 45, 4247e 4271.
Muramatsu, R., Ishii, K., and Takahashi (1985), "Some ways to increase flexibility in manufacturing systems", International Journal of Production Research 23, 691-703.
Ong.Y. S,Lim M. H.,Zhu N. and Wong. K. W.. 2006. 'Classification of Adaptive Memetic Algorithms: A Comparative Study', IEEE Transactions On Systems, Man and Cybernetics - Part B, Vol. 36, No. 1, pp. 141-152.
Rodriguez, F. J., Lozano, M., Blum, C., & Garcia-Martinez, C. (2013). An iterated greedy algorithm for the large-scale unrelated parallel machine scheduling problem. Computers & Operations Research, 40, 1829–1841.
Rogendran, R., & Subur, F. (2004). Unrelated parallel machine scheduling with job splitting. IIE Transaction, 36, 356–372.
Sharma, A., Zhao, F., Sutherland, J.W., (2015). Econological scheduling of a manufacturing enterprise operating under a time-of-use electricity tariff. Journal of Cleaner Production 108, 256-270.
Smith J. E. 2007. "Co-evolving memetic algorithms: A review and progress report", IEEE Trans. Syst., Man Cybern., Part B: Cybern., vol. 37, p.6.
Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., & Sassani, F. (2009). Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research, 36, 3224–3230.
Vallada, E., & Ruiz, R. (2011). A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, 211, 612–622.
Vredeveld, T., & Hurkens, C. (2002). Experimental comparison of approximation algorithms for scheduling unrelated parallel machines. Informs Journal on Computing, 14(2), 175–189.
Zhang, H., Zhao, F., Fang, K., Sutherland, J.W., (2014). Energy-conscious flow shop scheduling under time-of-use electricity tariffs. CIRP Annals – Manufacturing Technology, 63, 37–40.