A New Hybrid Metaheuristics Algorithm for Minimizing Energy Consumption in the Flow Shop Scheduling Problem

In this study, we discuss the problem of permutation flowshop scheduling problem (PFSP) to reduce total energy consumption (TEC). We offer a new hybrid meta-heuristic algorithm for solving the problem. The paper aims to combine the cross entropy and genetic algorithm (CEGA) with the simulated annealing (SA) algorithm. The CEGA is applied to find the best initial solution inside the SA algorithm and the proposed algorithm is compared to previous tests of the famous NSGA-II and GA-SA algorithm. During study of the numerical test, the proposed algorithm genuinely useful is compared certain efficient algorithms of the from previous research.

Algorithm; Energy consumption; Flow shop, Meta-heuristic

al. (2013), Dai et al. (2013) and Liu and  Huang (2014), who used meta-heuristic algorithms to solve energy consumption problems. In this article, we focus on the Permutation Flow-Shop Scheduling Problem (PFSP). Researchers claim that a solution to this problem cannot be found in polynomial time. Therefore, PFSP is considered an NP-Hard problem (Garey et al., 1976; Sayadi et al., 2010). Because of the importance of this problem, several efforts have been made by experts to develop algorithms to minimize TEC.

In recent years, SA, Cross-entropy (CE) and GA algorithms have been used to solve scheduling problems. The SA algorithm is a meta-heuristic algorithm, which were first introduced by Kirkpatrick et al. (1983) for optimization.  However, this algorithm is now used in most PFSP scheduling problems (Pinedo, 2016). Like the SA, GA is also a meta-heuristic algorithm based on mimicking natural selection and recombination (Holland, 1992). CE is another meta-heuristic algorithm applied to rare event simulations, continuous optimization, and combinatorial optimization (Deng, 2006). This algorithm is useful in solving complex combinatorial optimization problems (De Boer et al., 2005). In recent years, some experts have used meta-heuristic algorithms to solve PFSP, and some simple meta-heuristics have been applied to reduce TEC. However, classic meta-heuristics need a long time if used in large cases (Santosa et al., 2011). Recently, some hybrid meta-heuristic alternatives have been developed to solve PFSP. These algorithms include a hybrid GA with SA (Dai et al., 2013); a hybrid GA with TS (Sukkerd and Wuttipornpun, 2016); a hybrid of ABC and TS (Li and Pan, 2015); and a hybrid of CE and GA (Santosa et al., 2011).

Although many hybrid meta-heuristic algorithms have been developed to solve PFSP problems, they still display certain weaknesses, namely the long computing time for large-scale problems and optimal local solutions. Although they do need a long computation time, hybrid meta-heuristics give better performance compared to simple meta-heuristics. Many meta-heuristic algorithms have good global search capabilities, while some have local search capabilities. At present, few papers focus on minimizing TEC in PFSP. To our knowledge, none integrate CE and GA (CEGA) with SA. Therefore, this paper aims to combine CEGA with SA to reduce TEC, an approach we term CEGASA. This algorithm follows the rules for fixed energy consumption (FEC) Li et al. (2011). Hence, the paper focuses on minimizing TEC by following FEC rules. The remainder of this paper is organized as follows: Part 2 explains problem discription, example problem, proposes algorithms, and describes the experimental procedure. Section 3 then presents the computational experiments, experimental parameters, and comparison algorithms. Finally, the the conclusion is made in section 4.

We have discussed the problem of PFSP in reducing energy consumption and offer the CEGASA algorithm to solve this problem. The algorithm has been compared with other algorithms and numerical experiments have proven that it achieves optimum energy consumption. Some other research areas could be studied in future work. We propose that the CEGASA be used as an initial solution for other meta-heuristic algorithms, and ultimately be applied to the reduction of energy consumption in more complex PFSPs.

The authors would like to thank the Directorate of the Research University of Muhammadiyah Malang for support in conducting the research. We would also like to thank the Department of Industrial Engineering Optimation Laboratory for use of their facilities.

Brundage, M.P., Chang, Q., Li, Y., Xiao, G., Arinez, J., 2014. Energy Efficiency Management of an Integrated Serial Production Line and HVAC System. IEEE Transactions on Automation Science and Engineering, Volume 11(3), pp. 789–797

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, Volume 29(5), pp. 418–429

De Boer, P.T., Kroese, D.P., Mannor, S., Rubinstein, R.Y., 2005. A Tutorial on the Cross-entropy Method. Annals of Operations Research, Volume 134(1), pp. 19–67

Deng, L.Y., 2006. The Cross-entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning. Technometrics, Volume 48(1), pp. 147–148

Evans, L.B., 2003. Saving Energy in Manufacturing with Smart Technology. World, Volume 6(2), pp. 112–120

Garey, M.R., Johnson, D.S., Sethi, R., 1976. The Complexity of Flowshop and Jobshop Scheduling. Mathematics of Operations Research, Volume 1(2), pp. 117–129

Haddock, J., Mittenthal, J., 1992. Simulation Optimization using Simulated Annealing. Computers & Industrial Engineering, Volume 22(4), pp. 387–395

Holland, J.H., 1992. Genetic Algorithms. Scientific American, Volume 267(1), pp. 66–73

Iqbal, A., Al-Ghamdi, K.A., 2018. Energy-efficient Cellular Manufacturing System: Eco-friendly Revamping of Machine Shop Configuration. Energy, Volume 163, pp. 863–872

Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P., 1983. Optimization by Simulated Annealing. Science, Volume 220(4598), pp. 671–680

Li, J., Pan, Q., 2015. Solving the Large-scale Hybrid Flow Shop Scheduling Problem with Limited Buffers by a Hybrid Artificial Bee Colony Algorithm. Information Sciences, Volume 316, pp. 487–502

Li, J., Sang, H., Han, Y., Wang, C., Gao, K., 2018a. Efficient Multi-objective Optimization Algorithm for Hybrid Flow Shop Scheduling Problems with Setup Energy Consumptions. Journal of Cleaner Production, Volume 181, pp. 584–598

Li, S., Liu, F., Zhou, X., 2018b. Multi-objective Energy-saving Scheduling for a Permutation Flow Line. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, Volume 232(5), pp. 879–888

Li, W., Zein, A., Kara, S., Herrmann, C., 2011. An Investigation into Fixed Energy Consumption of Machine Tools. In: Hesselbach J., Herrmann C. (eds) Glocalized Solutions for Sustainability in Manufacturing. Springer, Berlin, Heidelberg, pp. 268–273

Liu, C., Huang, D., 2014. Reduction of Power Consumption and Carbon Footprints by Applying Multi-objective Optimisation via Genetic Algorithms. International Journal of Production Research, Volume 52(2), pp. 337–352

Liu, G., Zhou, Y., Yang, H., 2017. Minimizing Energy Consumption and Tardiness Penalty for Fuzzy Flow Shop Scheduling with State-dependent Setup Time. Journal of Cleaner Production, Volume 147, pp. 470–484

Luo, H., Du, B., Huang, G., Chen, H., Li, X., 2013. Hybrid Flow Shop Scheduling Considering Machine Electricity Consumption Cost. International Journal of Production Economics, Volume 146(2), pp. 423–439

Mirsanei, H., Zandieh, M., Moayed, M.J., Khabbazi, M. R., 2011. A Simulated Annealing Algorithm Approach to Hybrid Flow Shop Scheduling with Sequence-dependent Setup Times. Journal of Intelligent Manufacturing, Volume 22(6), pp. 965–978

Pinedo, M.L., 2016. Scheduling Theory, Algorithm, and Systems. Springer International Publishing, New York

Santosa, B., Budiman, M.A., Wiratno, S.E., 2011. A Cross Entropy-Genetic Algorithm for m-Machines No-wait Job-shop Scheduling Problem. Journal of Intelligent Learning Systems and Applications, Volume 3(03), pp 171–180

Sayadi, M., Ramezanian, R., GhaffariNasab, N., 2010. A Discrete Firefly Meta-heuristic with Local Search for Makespan Minimization in Permutation Flow Shop Scheduling Problems. International Journal of Industrial Engineering Computations, Volume 1(1), pp. 1–10

Sukkerd, W., Wuttipornpun, T., 2016. Hybrid Genetic Algorithm and Tabu Search for Finite Capacity Material Requirement Planning System in Flexible Flow Shop with Assembly Operations. Computers & Industrial Engineering, Volume 97, pp. 157–169

Surjandari, I., Rachman, A., Dhini, A., 2015. The Batch Sheduling Model for Dynamic Multiitem, Multilevel Production in an Assembly Job-shop with Parallel Machines. International Journal of Technology, Volume 1, pp. 84–96

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, Volume 81, pp. 82–95

Thawongklang, K., Tanwanichkul, L., 2016. Application of Production Scheduling Techniques for Dispatching Ready-mixed Concrete. International Journal of Technology, Volume 7(7), pp. 1163–1170

Zanoni, S., Bettoni, L., Glock, C.H., 2014. Energy Implications in a Two-stage Production System with Controllable Production Rates. International Journal of Production Economics, Volume 149, pp. 164–171

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, Volume 63(1), pp. 37–40