• Vol 10, No 2 (2019)
  • Industrial Engineering

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

Dana Marsetiya Utama, Dian Setiya Widodo, Wahyu Wicaksono, Leo Rizki Ardiansyah

Corresponding email: dana@umm.ac.id


Cite this article as:
Utama, D.M., Widodo, D.S., Wicaksono, W., Ardiansyah, L.R., 2019. A New Hybrid Metaheuristics Algorithm for Minimizing Energy Consumption in the Flow Shop Scheduling Problem. International Journal of Technology. Volume 10(2), pp. 320-331
168
Downloads
Dana Marsetiya Utama Department of Industrial Engineering, University of Muhammadiyah Malang, Jl. Raya Tlogomas 246 Malang, 65144, Indonesia
Dian Setiya Widodo Department of Manufacturing Technology, Vocational Faculty, University of 17 Agustus 1945 Surabaya, Jl. Semolowaru No. 45 Surabaya, 60118, Indonesia
Wahyu Wicaksono Department of Industrial Engineering, University of Muhammadiyah Malang, Jl. Raya Tlogomas 246 Malang, 65144, Indonesia
Leo Rizki Ardiansyah Department of Manufacturing Technology, Vocational Faculty, University of 17 Agustus 1945 Surabaya, Jl. Semolowaru No. 45 Surabaya, 60118, Indonesia
Email to Corresponding Author

Abstract
image

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

Introduction

Recently, Total Energy Consumption (TEC) in the manufacturing sector has received much attention from experts. This has been focused on highly TEC in the manufacturing sector. TEC in this sector requires almost half of the total energy needs in country. In the USA, it requires 33% of the total electricity of the country (Evans, 2003), while in Germany it requires 47% of electricity from all energy requirements (Dai et al., 2013). The electricity consumption of the sector needs fossil fuels for electricity generation; therefore, experts consider such consumption to be a problem because of the decreasing availability of these fuels. Some experts have made efforts to minimize TEC, one of which is scheduling, which refers to the arrangement of resources (machines) to complete the job (Surjandari et al., 2015). Generally, the goal of scheduling is to minimize completion time (Thawongklang & Tanwanichkul, 2016). However, some experts are now using scheduling to reduce TEC.

Several researchers have researched flow shop scheduling problems to reduce TEC. Zhang et al. (2014), Brundage et al. (2014) and Zanoni et al. (2014) have succeeded in minimizing TEC in simple flow shop problems, using a heuristic algorithm as a solution. Besides, heuristic algorithms are explicitly used to solve specific problems. In recent years, some meta-heuristic algorithm have also been used to solve the classic flow shop problem in order to minimize TEC. These algorithms include simulated annealing (SA) (Iqbal & Al-Ghamdi, 2018); a genetic algorithm (GA) (Liu et al., 2017); and particle swarm optimization (PSO) (Tang et al., 2016).  In hybrid flow shop problems, several studies to minimize TEC have been conducted by Luo et  

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.

Conclusion

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.

Acknowledgement

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.

References

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