A data mining-based solution method for flow shop scheduling problems

Document Type : Article

Authors

1 Department of Industrial Engineering, Kocaeli University, Kocaeli, Turkey

2 Department of Information Systems, Statistics and Management Science, University of Alabama, USA

Abstract

The scheduling theme which determines where and when the manufacturing actions will be performed is important to perform the activities in time, efficiently and cost-effectively. In this paper, an algorithm is proposed for the solution of a flow shop scheduling problem which holds an important place in the scheduling literature. The path relinking algorithm and data mining are used together for the solution of the flow shop scheduling problem studied here. While data mining is used for globally searching the solution space, path relinking is used for local search. Data Mining is a method which is used to extract the embedded information in a cluster that includes implicit information. Path relinking is an algorithm which advances by making binary displacements in order to convert the initial solution to the guiding solution and repeats by assigning the best obtained solution within this process as to the starting point. The efficiency of the model was tested on Taillard’s flow shop scheduling problems. Consequently, it has been possible to solve the large-size problem without the considerable mathematical back round. The obtained results show that the proposed method is in the competitiveness level with the other metaheuristic methods.

Keywords


References
1. Information Resources Management Association, Arti-
cial Intelligence: Concepts, Methodologies, Tools, and
Applications, IGI Global Publishing, USA (2016).
2. Thuraisingham, B., Data Mining: Technologies, Techniques,
Tools, and Trends, CRC Press, Printed in
United States of America (2014).
3. Framinan, J.M., Leisten, R., and Garca, R.R., Manufacturing
Scheduling Systems: An Integrated View
on Models, Methods and Tools, Springer Science &
Business Media (2014).
4. URL-1: http://mistic.heig-vd.ch/taillard/problemes.
dir/ordonnancement.dir/ (Visit date: 20.04.2018).
5. Wu, M., Liu, K., and Yang, H. \Supply chain production
and delivery scheduling based on data mining",
Cluster Computing, 22, pp. 8541{8552 (2019).
https://doi.org/10.1007/s10586-018-1894-8
6. Santos, H.G., Ochi Marinho, L.S., and Drummond,
E.H. \Combining an evolutionary algorithm with data
mining to solve a single-vehicle routing problem",
Neurocomputing, 70, pp. 70{77 (2006).
7. Gupta, A. and Kumar, S. \Flow shop scheduling decisions
through Techniques for Order Preference by Similarity
to an Ideal Solution (TOPSIS)", International
Journal of Production Management and Engineering,
4(2), pp. 43{52 (2016). DOI: 10.4995/ijpme.2016.4102
8. Reeves, C.R. and Yamada, T. \Genetic algorithm,
path relinking and the
owshop sequencing problem",
Evolutionary Computation, 6, pp. 45{60 (1998).
9. Wang, C., Chu, C., and Proth, J.M. \Heuristic
approaches for n=m=F==PCi scheduling problems",
European Journal of Operational Research, 96, pp.
636{644 (1997).
10. Ho, J.C. \Flowshop sequencing with mean
owtime
objective", European Journal of Operational Research,
81(3), pp. 571{578 (1995).
11. Rajendran, C. and Ziegler, H. \An ecient heuristic
for scheduling in a
owshop to minimize total weighted

owtime of jobs", European Journal of Operational
Research, 103, pp. 129{138 (1997).
12. Woo, D.S. and Yim, H.S. \A heuristic algorithm
for mean
owtime objective in
owshop scheduling",
Computers and Operational Research, 25, pp. 175{182
(1998).
13. Aminnayeri, M. and Naderi, B. \Novel properties
along with solution methods for permutation
owshop
scheduling", Scientia Iranica, Transaction E, Industrial
Engineering, 23(5), pp. 2261{2276 (2016).
14. Liu, J. and Reeves, C.R. \Constructive and composite
heuristic solutions to the P==PCi scheduling problem",
European Journal of Operational Research, 132,
pp. 439{452 (2001).
15. Allahverdi, A. and Aldowaisan, T. \New heuristics
to minimize total completion time in m-machine

owshops", International Journal of Production Economics,
77, pp. 71{83 (2002).
16. Framinan, J.M., Leisten, R., and Ruiz-Usano, R.,
\Comparison of heuristics for minimisation in permutation

owshops", Computers and Operations Research,
32, pp. 1237{1254 (2005).
17. Jolai, F., Tavakkoli-Moghaddam, R., Rabiee, M., and
Gheisariha, E. \An enhanced invasive weed ptimization
for makespan minimization in a
exible
owshop
scheduling problem", Scientia Iranica, Transaction E,
Industrial Engineering, 21(3), pp. 1007{1020 (2014).
968 B. Ozcan et al./Scientia Iranica, Transactions E: Industrial Engineering 28 (2021) 950{969
18. Rajendran, C. and Ziegler, H. \Ant-colony algorithms
for permutation
owshop scheduling to minimize
makespan/total
owtime of jobs", European Journal
of Operational Research, 155, pp. 426{438 (2004).
19. Rajendran, C. and Ziegler, H. \Two ant-colony algorithms
for minimizing total
owtime in permutation

owshops", Computer and Industrial Engineering, 48,
pp. 789{797 (2005).
20. Tasgetiren, F., Liang, Y.C., Sevkli, M., and Gencyilmaz,
G. \A particle swarm optimization algorithm
for makespan and total
owtime minimization in the
permutation
owshop sequencing problem", European
Journal of Operational Research, 177, pp. 1930{1947
(2007).
21. Mohammadi, S., Cheraghalikhani, A., and Ramezanian,
R. \A joint scheduling of production and distribution
operations in a
ow shop manufacturing
system", Scientia Iranica, 25(2), pp. 911{930 (2018).
22. Akpnar, H. \Information discovery and data mining
in databases", Istanbul University Business School
Journal, 29, pp. 1{22 (2000).
23. Hui, S. and Jha, G. \Application data mining for customer
service support", Information and Management,
38, pp. 1{13 (2000).
24. Goebel, M. and Gruenwald, L. \A survey of data
mining and knowledge discovery software tools", ACM
SIGKDD Explorations Newsletter, 1, pp. 20{33 (1999).
25. Gonulol, S. \A data mining based intuitive approach
for the travel salesman problem", M.Sc. Thesis, Kocaeli
University, Institute of Science, Kocaeli (2009).
26. Koonce, D., Fang, C.H., and Tsai, S.C. \A data mining
tool for learning from manufacturing systems", Computers
Industrial Engineering, 33, pp. 27{30 (1997).
27. Koonce, D.A. and Tsai, S.C. \Using data mining to
nd patterns in genetic algorithm solutions to a job
shop schedule", Computers & Industrial Engineering,
38, pp. 361{374 (2000).
28. Kumar, S. and Rao, C.S.P. \Application of antcolony,
genetic algorithm and data mining-based techniques
for scheduling", Robotics and Computer-Integrated
Manufacturing, 25, pp. 901{908 (2009).
29. Olafsson, S. and Li, X. \Learning e ective new single
machine dispatching rules from optimal scheduling
data", International Journal of Production Economics,
128(1), pp. 118{126 (2010).
30. Martens, D., Baesens, B., and Fawcett, T. \Editorial
survey: Swarm intelligence for data mining", Machine
Learning, 82(1), pp. 1{42 (2011).
31. Karthikeyan, S., Asokan, P., Nickolas, S., and Page,
T. \Solving
exible job-shop scheduling problem using
hybrid particle swarm optimisation algorithm and
data mining", International Journal of Manufacturing
Technology and Management, 26(1), pp. 81{103
(2012).
32. Shahzad, A. and Mebarki, N. \Data mining based
job dispatching using hybrid simulation-optimization
approach for shop scheduling problem", Engineering
Applications of Arti cial Intelligence, 25(6), pp. 1173{
1181 (2012).
33. Wang, C.L., Rong, G., Weng, W., and Feng, Y.P.
\Mining scheduling knowledge for job shop scheduling
problem", FAC-PapersOnLine, 48(3), pp. 800{805
(2015).
34. Zahmani, M.H., Atmani, B., Bekrar, A., and Aissani,
N. \A real time data mining rules selection model for
the job shop scheduling problem", CIE45 Proceedings,
Metz, France (2015).
35. Mirshekarian, S. and Sormaz D.N. \Correlation of
job-shop scheduling problem features with scheduling
eciency", Expert Systems With Applications, 62, pp.
131{147 (2016).
36. Makrymanolakis, N., Marinaki, M., and Marinakis, Y.
\Data mining parameters' selection procedure applied
to a multi-start local search algorithm for the permutation

ow shop scheduling problem", Computational Intelligence
(SSCI), IEEE Symposium Series on (2016).
37. Senvar, O., Yalaoui, F., Dugardin, F., Lara, A.F.B.
\Data mining approaches for the methods to minimize
total tardiness in parallel machine scheduling problem",
IFAC Conference on Manufacturing Modelling,
Management and Control, Troyes, France (2016).
38. Shahzad, A. and Mebarki, N. \Learning dispatching
rules for scheduling: A synergistic view comprising decision
trees, tabu search and simulation", Computers,
5(1), pp. 1{16 (2016).
39. Wu, M., Liu, K., and Yang, H. \Supply chain production
and delivery scheduling based on data mining",
Cluster Computing, 22, pp. 8541{8552 (2019).
40. Poursabzi, O., Mohammadi, M., and Naderi, B. \An
improved model and heuristic for capacitated lot-sizing
and scheduling in job shop problems", Scientia Iranica,
25(6), pp. 3667{3684 (2018).
Volume 28, Issue 2
Transactions on Industrial Engineering (E)
March and April 2021
Pages 950-969
  • Receive Date: 19 May 2018
  • Revise Date: 04 March 2019
  • Accept Date: 03 August 2020