Email this article 
Minimizing Total Flow Time in Permutation Flowshop Scheduling by Two-Phase Approach
(*) Corresponding author
DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)
Abstract
This work considered minimizing total flow time for general n-jobs and m-machines permutation flowshop scheduling problems, which are well-known to be NP-hard. The proposed approach used the combination of Decision Tree (DT) based heuristic algorithm and Scatter Search (SS) algorithm. Unlike existing heuristics available for flowshop scheduling, the DT based algorithm is used to represent the low level data into high level knowledge ie., in the form of IF-THEN else rules which are understandable by the semi-skilled worker. The SS has wide exploration of search space through diversification. The advantages of both DT and SS are utilized to form a two-phase approach. The seed solution generated from DT based approach is taken as input seed to SS algorithm to find good solution. The proposed approach is compared with most effective heuristics and recent meta-heuristics available in the literature. The proposed approach gives better solution as compared to existing composite heuristics and comparable with existing hybrid meta-heuristics.
Copyright © 2014 Praise Worthy Prize - All rights reserved.
Keywords
References
K. R. Baker, Introduction to sequencing and scheduling, (Wiley.1974).
R. Ruiz, C. Maroto, A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operational Research, Vol. 165, n. 2, pp.479-494, 2009.
J. N. D. Gupta, E. F. Stafford, Flowshop scheduling research after five decades, European Journal of Operational Research, Vol.169, n. 3, pp. 699-711, 2006.
C. Rajendran, A heuristic for scheduling in flowshop and flowline Based manufacturing cell with multi-criteria, International Journal of Production Research, Vol. 32, pp.2541-2558,1994.
Hamzas, M.F.M.A., Bareduan, S.A., Hussin, M.S., Hasnul, M.J., Sanuddin, A.B., Zailani, Z.A., Performance evaluation of m3 bottleneck based heuristic for M1M2M3 flow shop, (2012) International Review of Mechanical Engineering (IREME), 6 (6), pp. 1253-1256.
Hamzas, M.F.M.A., Bareduan, S.A., Tajul, L., Hussin, M.S., Zailani, Z.A., Hadi, H., Development of improved bottleneck-based heuristic for re-entrant flow shop with dominant machine at M1 and M4, (2012) International Review of Mechanical Engineering (IREME), 6 (3), pp. 501-506.
Shi Ling, Cheng Xue-guang, Two- machine flow shop scheduling problems with minimizing the total completion times, Applied Mathematical Sciences, Vol. 6, pp.3437-3441, 2012.
C. Rajendran, D. Chaudhuri, An efficient heuristic approach to the scheduling of jobs in a flow shop, European Journal of Operational Research, Vol. 61, n. 3, pp. 318–325, 1992.
C. Rajendran, Heuristic algorithm for scheduling in flow shop to minimize total flow time, International Journal of Production Economics, Vol.29, pp.65–73, 1993.
J. C. Ho, Flowshop sequencing with mean flowtime objective, European Journal of Operational Research, Vol.81, pp.571-578, 1995.
C. Wang, C. Chu. J. M. Proth, Heuristics approaches for n/m/F/∑Ci scheduling Problems, European Journal of Operational Research, Vol.96, pp. 636–644.1997.
C. Rajendran, H. Ziegler, An efficient heuristic for scheduling in flowshop to minimize total weighted flowtime of jobs, European Journal of Operational Research, Vol.103, pp.129-138.1997.
D. S. Woo, H. M. Yim, A heuristic algorithm for mean flow Time objective inflow shop scheduling, Computers and Operations Research, Vo.l.25, pp.175–182,1998.
J. M. Framinan, R. Leisten, An efficient constructive heuristic for flowtime minimization in permutation flow shops, Omega,Vol. 31, pp. 311-31, 2003.
J. Liu, C. R. Reeves, Constructive and composite heuristic solutions to the P││ΣCi scheduling problem, European Journal of Operational Research, Vol. 132, n.2, pp.439-452, 2001.
A. Allahverdi, T. Aldowaisan, New heuristics to minimize total completion time in m-machine Flowshops, International Journal of Production Economics, Vol. 77, pp.71-83, 2002.
J. M. Framinan, R. Leisten, R. Ruiz-Usano, Comparison of heuristics for minimisation in permutation Flowshops, Computers & Operations research, Vol. 32, pp.1237-1254, 2005.
Deepak Laha, Uday K. Chakraborty, An efficient heuristic approach to total flow time minimization in permutationflow shop scheduling, International Journal of Advanced Manufacturing Technology, Vol. 38, n.9-10, pp.1018-1025, 2008.
Xiaoping Li, Qian Wang, Cheng Wu, Efficient composite heuristics for total flowtime minimization in permutation flow shops, Omega, Vol.37, n.1, pp. 155-164,2009.
J. N. D. Gupta, A functional heuristic algorithm for the flowshop scheduling problem, Operational Research Quarterly, Vol.22,n.1, pp. 39-47,1971.
S. Miyazaki, N. Nishiyama, F. Hashimoto. An adjacent pairwise approach to the mean flowtime scheduling problem, Journal of the Operations Research Society of Japan, Vol. 21, pp.287-299,1978.
J. C. Ho, Y. L. Chang, A new heuristic for the n -Job m-machine flow-shop problem, European Journal of Operations Research,Vol.52, pp.194-202.
M. E. Nawaz, E. Enscore, I. Ham, A heuristic algorithm for the m- machine n- Job flowshop sequencing problem, Omega, Vol.11, pp. 91-95,1983.
Kaizhou Gao, Quanke Pan, P. N. Suganthan, Junqing Li, Efficient heuristics for the no-wait flow shop scheduling problem with total flow time minimization, International Journal of Advanced Manufacturing Technology, Vol. 66, n.9-12, pp.1563- 1572, 2013.
Behdin Vahedi-Nouri, Parviz Fattahi, Reza Ramezanian, Minimizing total flow time for the non-permutation flow shop scheduling problem with learning effects and availability constraints, Journal of Manufacturing Systems, Vol. 32, n.1, pp.167-173, 2013.
T. Yamada, C. R. Reeves, Solvingthe Csum permutation flow shop scheduling problem by genetic local Search, Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, pp.230-234,1998.
C. Rajendran, H. Ziegler, Ant-colony algorithms for Permutation flowshop scheduling to minimize makespan/ total flowtime of jobs, European Journal of Operational Research, Vol. 155, n.2, pp.426–438, 2004.
C. Rajendran, H. Ziegler, Two ant-colony algorithms for minimizing total flowtime in permutation Flowshops, Computer & Industrial Engineering, Vol.48, pp.789-797,2005.
M. F. Tasgetiren, Y. G. Liang, M. Sevkli, G. Gencyilmaz, A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, European Journal of Operational Research, Vol. 177, pp. 1930-1947,2007.
B. Jarboui, S. Ibrahim, P. Siarry, A. Rebai, A combinatorial particle swarm optimization for Solving permutation flowshop problems, Computers & Industrial Engineering, Vol. 54, pp.526- 538, 2008.
Yi Zhang. Xiaoping Li, Qian Wang, Hybrid Genetic Algorithm for permutation flowshop scheduling problems with total flowtime minimization, European Journal of Operational Research, Vol. 196, pp. 869-876,2009.
B. Jarboui, M. Eddaly, P. Siarry, An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems, Computers and Operations Research, Vol. 36, pp.2638-2646, 2009.
Lin-Yu Tseng, Ya-TaiLin, A genetic local search algorithm for minimizing total flowtime in the permutation flowshop scheduling problem, International Journal of Production Economics, Vol. 127, pp.121-128, 2010.
Xiao Xu, Zhenhao Xu, Xingsheng Gu, An asynchronous genetic local search algorithm for the Permutation flowshop scheduling problem with total flowtime minimization, Expert system with applications, Vol. 38, pp.7970-7979, 2011.
B. Kilundu, P. Dehombreux, Data Mining Techniques and Singular Spectrum Analysis for Tool Condition Monitoring in Metal Cutting, (2008) International Review of Mechanical Engineering (IREME), 2 (1), pp. 49-55.
L. Bremian, J. H. Friedman, R. A. Olshen, C. J. Stone, Classification and Regression trees, (Wadsworth, Belmont 1984).
J. R. Quinlan, Induction of Decision Trees, Machine Learning, Vol.1, n.1, pp. 81-106,1986.
Xiaonan Li, Sigurdur Olafsson. Discovering Dispatching Rules Using Data Mining, Journal of Scheduling, Vol. 8, pp. 515 527,2005.
Xiaonan Li, Sigurdur Olafsson. Learning Effective new single machine dispatching rules from optimal scheduling data, International Journal of Production Research, Vol. 128, pp.118- 126,2010.
D. A. Koonce, S. C. Tsai, Using data mining to find patterns in genetic algorithm solution to a job shop Schedule, Computers and Industrial Engineering, Vol. 38, pp.361-374.2010.
Hyun-Seon Choi, Ji-Su Kim, Dong-Ho Lee, 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, Vol. 38, pp.3514-352, 2011.
Atif Shahzad, Nasser Merbark, Data mining based job dispatching using hybrid simulation optimization approach for shop scheduling problem, Journal of Engineering Applications of Artificial Intelligence, Vol. 25, pp.1173-1181, 2012.
F. Glover, M. Laguna, R. Marti, Fundamentals of scatter search and path relinking, Control and Cybernetics, Vol. 29, n.3, pp.653–684,2000.
R. Marti, M. Laguna, V. Campos, Scatter search vs. genetic algorithms: an experimental evaluation with permutation problems. In: Rego C, Alidaee B (eds) Metaheuristic optimization via adaptive memory and evolution: tabu search and scatter search, Kluwer Academic Publishers, Norwell, Massachusetts, pp.263–282, 2005.
E. Taillard, Benchmarks for basic scheduling problems, European journal of Operational Research, Vol. 64, pp.278-285, 1993.
Refbacks
- There are currently no refbacks.
Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize
