A hybrid approach for minimizing makespan in permutation flowshop scheduling

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.

Keywords

Flowshop scheduling / makespan / decision tree algorithm / scatter search algorithm / hybrid algorithm

References

[1] Agarwal A., Colak S., Eryarsoy E.. Improvement heuristic for the flow-shop scheduling problem: an adaptive-learning approach. European Journal of Operational Research, 2006, 169(3): 801-815.

[2] Atif S., Nasser M.. Data mining based job dispatching using hybrid simulation-optimization approach for shop scheduling problem. Journal of Engineering Applications of Artificial Intelligence, 2012, 25(6): 1173-1181.

[3] Aytug H., Bhattacharyya S., Koehler G.J., Snowdon J.L.. A review of machine learning in scheduling. IEEE Transactions on Engineering Management, 1994, 41(2): 165-171.

[4] Baker K.R.. Introduction to Sequencing and Scheduling, 1974, New York: John Wiley & Sons, Inc

[5] Balasundaram R., Valavan D., Baskar N.. Heuristic based approach for bi-criteria optimization of minimizing makespan and total flow time of flowshop scheduling. International Journal of Mechanical & Mechatronics Engineering, 2014, 14(02): 1-11.

[6] Balasundaram R., Kannan G., Baskar N., Shiva S.R.. Rule based heuristic based approach for minimizing total flow time in permutation flowshop scheduling. Tehnicki vjesnik, 2015, 22(01): 25-32.

[7] Carlier J.. Ordonnancements a contraintes disjonctives. R.A.I.R.O. Recherche Operationelle/Operations Research, 1978, 12(4): 333-350.

[8] Gen M., Cheng R.. Genetic Algorithms and Engineering Design, 1997, New York: John Wiley & Sons, Inc

[9] Chen S., Chang P.C., Zhang Q.. A self-guided genetic algorithm for flowshop scheduling problems. Proceedings of the Eleventh Conference on Congress on Evolutionary Computation, 2009 471-478.

[10] Chen S., Chang P.C., Cheng T.C.E., Zhang Q.. A self-guided genetic algorithm for permutation flowshop scheduling problems. Computers & Operations Research, 2012, 39(7): 1450-1457.

[11] Chang P.C., Hunag W.H., Wu J.L., Cheng T.C.E.. A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem. International Journal of Production Economics, 2013, 141(1): 45-55.

[12] Choi H.S., Kim J.S., Lee D.H.. 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, 2011, 38(4): 3514-3521.

[13] Gupta J.N.D., Stafford E.F.. Flowshop scheduling research after five decades. European Journal of Operational Research, 2006, 169(3): 699-711.

[14] Han, J. & Kamber, M. (2006). Data Mining: Concepts and Techniques, San Francisco: Morgan Kaufmann.

[15] Ho J.C., Chang Y.L.. A new heuristic for the n-job, m-machine flow-shop problem. European Journal of Operational Research, 1991, 52(2): 194-202.

[16] Harding J.A., Shahbaz M., Srinivas K. A.. Data mining in manufacturing: a review. Journal of Manufacturing Science and Engineering, 2006, 128(4): 969-976.

[17] Jarboui B., Ibrahim S., Siarry P., Rebai A.. A combinatorial particle swarm optimization for solving permutation flowshop problems. Computers & Industrial Engineering, 2008, 54(3): 526-538.

[18] Johnson S.M.. Two and three stage production schedules with setup times included. Naval Research Logistics Quarterly, 1954, 1(1): 61-68.

[19] Kalczynski P.J., Kamburowski J.. On the NEH heuristic for minimizing the makespan in permutation flow shops. OMEGA, The International Journal of Management Science, 2007, 35(1): 53-60.

[20] Kumar S., Rao C.S.P.. Applications of ant colony, genetic algorithm and data mining based technique for scheduling. Robotics and Computer-Integrated Manufacturing, 2009, 25(6): 901-908.

[21] Laha D., Chakraborty U.K.. An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling. International Journal of Advanced Manufacturing Technology, 2009, 44(5): 559-569.

[22] Li X., Olafsson S.. Discovering dispatching rules using data mining. Journal of Scheduling, 2005, 8(6): 515-527.

[23] Li X., Olafsson S.. Learning effective new single machine dispatching rules from optimal scheduling data. International Journal of Production Economics, 2010, 128(1): 118-126.

[24] Liu B., Wang L., Jin Y.H.. An effective PSO-based memetic algorithm for flow shop scheduling. IEEE Transactions on Systems, Man and Cybernetics, Part B, 2007, 37(1): 18-27.

[25] Liu F.Y., Liu S.Y.. A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Applied Soft Computing, 2013, 13(3): 1459-1463.

[26] Modrák V., Pandian R.S.. Flow shop scheduling algorithm to minimize completion time for n-jobs m-machines problem. Technical Gazette, 2010, 17(3): 273-278.

[27] Mircea A.. On solving flowshop scheduling problems. Proceeding of the Romanian Academy, Series A, 2012, 13(1): 71-79.

[28] 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.

[29] Pan Q., Tasgetiren M., Liang Y.. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers & Industrial Engineering, 2008, 55(4): 795-816.

[30] Rad S.F., Ruiz R., Boroojerdian N.. New high performing heuristics for minimizing makespan in permuation flow shops. OMEGA-The International Journal of Management Science, 2009, 37(2): 331-345.

[31] Rajendran C., Ziegler H.. Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 2004, 155: 426-438.

[32] Rajkumar R., Shahabudeen P.. Performance evaluation of simulated annealing algorithm for flowshop scheduling problems. The International Journal of Applied Management and Technology, 2008, 5(3): 172-189.

[33] Reeves C.R.. A genetic algorithm for flow shop sequencing. Computers and Operations Research, 1995, 22(1): 5-13.

[34] Saravanan M., Haq N., Vivekraj A.R., Prasad T.. Performance evaluation of the scatter search method for permutation flowshop sequencing problems. International Journal of Advanced Manufacturing Technology, 2008, 37(11-12): 1200-1208.

[35] Shukla S.K., Tiwari M.K., Son Y.J.. 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, 2008, 38(1): 163-175.

[36] Taillard E.. Benchmarks for basic scheduling instances. European Journal of Operational Research, 1993, 64(2): 278-285.

[37] Tasgetiren M., Sevkli M., Liang Y.C., et al. Dorigo M., et al. Particle swarm optimization algorithm for permutation flowshop sequencing problem. Lecture Notes in Computer Science, 2004, New York: Springer-Verlag 382-389.

[38] Tasgetiren M., Liang Y., Sevkli M., Gencyilmaz G.. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flow shop sequencing problem. European Journal of Operational Research, 2007, 177(3): 1930-1947.

[39] Wang K.. Applying data mining to manufacturing: the nature and implications. Journal of Intelligent Manufacturing, 2007, 18(4): 487-495.

[40] Wang L., Zheng D.Z.. An effective hybrid heuristic for flow shop scheduling. The International Journal of Advanced Manufacturing Technology, 2003, 21(1): 38-44.

[41] Ying K.C., Liao C.J.. An ant colony system for permutation flow-shop sequencing. Computers & Operations Research, 2004, 31(5): 791-801.