Abstract
This work proposes a hybrid approach for solving traditional flowshop scheduling problems to reduce the makespan (total completion time). To solve scheduling problems, a combination of Decision Tree (DT) and Scatter Search (SS) algorithms are used. Initially, the DT is used to generate a seed solution which is then given input to the SS to obtain optimal / near optimal solutions of makespan. The DT used the entropy function to convert the given problem into a tree structured format / set of rules. The SS provides an extensive investigation of the search space through diversification. The advantages of both DT and SS are used to form a hybrid approach. The proposed algorithm is tested with various benchmark datasets available for flowshop scheduling. The statistical results prove that the proposed method is competent and efficient for solving flowshop problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Agarwal, A., Colak, S. & Eryarsoy, E. (2006). Improvement heuristic for the flow-shop scheduling problem: an adaptive-learning approach. European Journal of Operational Research, 169 (3): 801–815.
Atif, S. & Nasser, M. (2012). Data mining based job dispatching using hybrid simulation-optimization approach for shop scheduling problem. Journal of Engineering Applications of Artificial Intelligence, 25 (6): 1173–1181.
Aytug, H., Bhattacharyya, S., Koehler, G.J. & Snowdon, J.L. (1994). A review of machine learning in scheduling. IEEE Transactions on Engineering Management, 41 (2): 165–171.
Baker, K.R. (1974). Introduction to Sequencing and Scheduling. New York: John Wiley & Sons, Inc.
Balasundaram, R., Valavan, D. & Baskar, N. (2014). Heuristic based approach for bi-criteria optimization of minimizing makespan and total flow time of flowshop scheduling. International Journal of Mechanical & Mechatronics Engineering, 14 (02): 1–11.
Balasundaram, R., Kannan, G., Baskar, N. & Shiva, S.R. (2015). Rule based heuristic based approach for minimizing total flow time in permutation flowshop scheduling. Tehnicki vjesnik, 22 (01):25–32.
Carlier, J. (1978). Ordonnancements a contraintes disjonctives. R.A.I.R.O. Recherche Operationelle/Operations Research, 12 (4): 333–350.
Gen, M. & Cheng, R. (1997). Genetic Algorithms and Engineering Design, New York: John Wiley & Sons, Inc.
Chen, S., Chang, P.C. & Zhang, Q. (2009). A self-guided genetic algorithm for flowshop scheduling problems. In: Proceedings of the Eleventh Conference on Congress on Evolutionary Computation, pp. 471–478.
Chen, S., Chang, P.C., Cheng, TCE. & Zhang, Q. (2012). A self-guided genetic algorithm for permutation flowshop scheduling problems. Computers & Operations Research, 39 (7): 1450–1457.
Chang, P.C., Hunag, W.H., Wu, J.L. & Cheng, TCE. (2013). A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem. International Journal of Production Economics, 141 (1): 45–55.
Choi, H.S., Kim, J.S. & Lee, D.H. (2011). Real-time scheduling for reentrant hybrid flow shops: a decision tree based mechanism and its application to a TFT-LCD line. Expert Systems with Applications, 38 (4): 3514–3521.
Gupta, J.N.D. & Stafford, E.F. (2006). Flowshop scheduling research after five decades. European Journal of Operational Research, 169 (3): 699–711.
Han, J. & Kamber, M. (2006). Data Mining: Concepts and Techniques, San Francisco: Morgan Kaufmann.
Ho, J.C. & Chang, Y.L. (1991). A new heuristic for the n-job, m-machine flow-shop problem. European Journal of Operational Research, 52(2):194–202.
Harding, J.A., Shahbaz, M. & Srinivas, K. A. (2006). Data mining in manufacturing: a review. Journal of Manufacturing Science and Engineering, 128 (4): 969–976.
Jarboui, B., Ibrahim, S., Siarry, P. & Rebai, A. (2008). A combinatorial particle swarm optimization for solving permutation flowshop problems. Computers & Industrial Engineering, 54 (3): 526–538.
Johnson, S.M. (1954). Two and three stage production schedules with setup times included. Naval Research Logistics Quarterly, 1 (1): 61–68.
Kalczynski, P.J. & Kamburowski, J. (2007). On the NEH heuristic for minimizing the makespan in permutation flow shops. OMEGA, The International Journal of Management Science, 35 (1): 53–60.
Kumar, S. & Rao, CSP. (2009). Applications of ant colony, genetic algorithm and data mining based technique for scheduling. Robotics and Computer-Integrated Manufacturing, 25 (6): 901–908.
Laha, D. & Chakraborty, U.K. (2009). An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling. International Journal of Advanced Manufacturing Technology, 44 (5): 559–569.
Li, X. & Olafsson, S. (2005). Discovering dispatching rules using data mining. Journal of Scheduling, 8 (6): 515–527.
Li, X. & Olafsson, S. (2010). Learning effective new single machine dispatching rules from optimal scheduling data. International Journal of Production Economics, 128 (1): 118–126.
Liu, B., Wang, L. & Jin, Y.H. (2007). An effective PSO-based memetic algorithm for flow shop scheduling. IEEE Transactions on Systems, Man and Cybernetics, Part B, 37 (1): 18–27.
Liu, F.Y. & Liu, S.Y. (2013). A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Applied Soft Computing, 13 (3): 1459–1463
Modrák, V. & Pandian, R.S. (2010). Flow shop scheduling algorithm to minimize completion time for n-jobs m-machines problem. Technical Gazette, 17 (3): 273–278.
Mircea, A. (2012). On solving flowshop scheduling problems. Proceeding of the Romanian Academy, Series A, 13 (1): 71–79.
Nawaz, M., Enscore, EE. & Ham, I. (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA-The International Journal of Management Science, 11 (1): 91–95.
Pan, Q., Tasgetiren, M. & Liang, Y. (2008). A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers & Industrial Engineering, 55(4):795–816.
Rad, S.F., Ruiz, R. & Boroojerdian, N. (2009). New high performing heuristics for minimizing makespan in permuation flow shops. OMEGA-The International Journal of Management Science, 37 (2): 331–345.
Rajendran, C. & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155: 426–438.
Rajkumar, R. & Shahabudeen, P. (2008). Performance evaluation of simulated annealing algorithm for flowshop scheduling problems. The International Journal of Applied Management and Technology, 5 (3): 172–189.
Reeves, C.R. (1995). A genetic algorithm for flow shop sequencing. Computers and Operations Research, 22(1):5–13.
Saravanan, M., Haq, N., Vivekraj, A.R. & Prasad, T. (2008). Performance evaluation of the scatter search method for permutation flowshop sequencing problems. International Journal of Advanced Manufacturing Technology, 37(11-12): 1200–1208.
Shukla, S.K., Tiwari, M.K. & Son, Y.J. (2008). Bidding-based multi-agent system for integrated process planning and scheduling: a data-mining and hybrid tabu-SA algorithm oriented approach. International Journal of Advanced Manufacturing Technology, 38 (1): 163–175.
Taillard, E. (1993). Benchmarks for basic scheduling instances. European Journal of Operational Research, 64 (2): 278–285.
Tasgetiren, M., Sevkli, M. & Liang, Y.C. (2004). Particle swarm optimization algorithm for permutation flowshop sequencing problem, in: M. Dorigo, et al. (eds.), Lecture Notes in Computer Science, vol. 3172, Springer-Verlag, New York, 2004, pp. 382–389.
Tasgetiren, M., Liang, Y., Sevkli, M. & Gencyilmaz, G. (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flow shop sequencing problem. European Journal of Operational Research, 177 (3): 1930–1947.
Wang, K. (2007). Applying data mining to manufacturing: the nature and implications. Journal of Intelligent Manufacturing, 18 (4): 487–495.
Wang, L. & Zheng, D.Z. (2003). An effective hybrid heuristic for flow shop scheduling. The International Journal of Advanced Manufacturing Technology, 21 (1): 38–44.
Ying, K.C & Liao, C.J. (2004). An ant colony system for permutation flow-shop sequencing. Computers & Operations Research, 31 (5): 791–801.
Acknowledgments
The authors are thankful to the referees for their suggestions and comments to improve the earlier version of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Kannan Govindan works as a professor and Head of Center for Sustainable Engineering Operations Management, Department of Technology and Innovation, University of Southern Denmark. He received B.E. (mechanical engineering) from Madurai Kamarajar University, M.E. (industrial engineering) from Bharathiyar University and Ph.D (supply chain management) from National Institute of Technology, Tiruchirappalli, India. He has published more than 150 papers in international journals. Currently Editor-in-Chief for International Journal of Advanced Operations Management, International Journal of Business Performance and Supply Chain Modelling, Inderscience Publishers, Switzerland and subject editor–Sustainable Supply Chain Management in Journal of Cleaner Production. He is a visiting professor at UNESP, Dalian University of Technology and Dalian Maritime University. His current area of research includes logistics, supply chain management (SCM), green and sustainable SCM, CSR, EPR and e-waste.
R. Balasundaram works as a professor of mechanical engineering at K.Ramakrishnan College of Engineering, Tiruchirappalli, India. He received B.E (mechanical engineering) from Madras University, M.E. (engineering design) from Bharathiyar University and Ph.D (mechanical engineering) from Anna University. He is having more than 18 years of teaching experience and current area of research includes optimization techniques, production planning & control and data mining.
N. Baskar works as a professor of mechanical engineering at Saranathan College of Engineering, Tiruchirappalli, India. He received B.E in mechanical engineering from Bharathidasan University, M.E in manufacturing technology & Ph.D in production engineering from Regional Engineering College, Tiruchirappalli. He has published more than 100 papers in international & national journals and conferences. He has more than 22 years of experience. His current research includes non-traditional techniques, machining process optimization and data mining.
P. Asokan works as a professor of production engineering at National Institute of Technology, Tiruchirappalli, India. He received B.E (mechanical engineering) & M.E (manufacturing technology) from Regional Engineering College and Ph.D (production engineering) from Bharathidasan University. He has published more than 50 papers in international & national Journals. He is having more than 25 years of experience. His current area of research includes operation management and optimization in manufacturing, scheduling, non-conventional machining etc.
Rights and permissions
About this article
Cite this article
Govindan, K., Balasundaram, R., Baskar, N. et al. A hybrid approach for minimizing makespan in permutation flowshop scheduling. J. Syst. Sci. Syst. Eng. 26, 50–76 (2017). https://doi.org/10.1007/s11518-016-5297-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11518-016-5297-1