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

Corresponding email: dana@umm.ac.id

Corresponding email: dana@umm.ac.id

**Published at : ** 25 Apr 2019

**Volume :** **IJtech**
Vol 10, No 2 (2019)

**DOI :** https://doi.org/10.14716/ijtech.v10i2.2194

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.

1,310

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 |

Abstract

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