On the n-job, m-machine permutation flow shop scheduling problems with makespan criterion and rework

Document Type : Article


1 Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran

2 Department of Industrial Engineering, Babol Noshirvani University of Technology, Babol, Iran


This paper addresses an n-job, m-machine permutation flow shop scheduling problem (PFSSP) with unlimited intermediate buffers and rework activities. The concept of rework means that processing of a job on a machine may not meet a predefined quality level through its first process. Thus we have a probabilistic cycle of operations for jobs on different machines which is based on two concepts: (1) a failure probability of a job on a machine and, (2) a descent rate that reduces the processing times for rework phase. In this case, the processing times of jobs on machines become random variables with a known probability distribution. The aim of this paper is to examine possible solution approaches for generating the efficient job sequences with the least potential makespan. A wide range of simulation-based approaches are applied to address the proposed problem. These methods contain mathematical formulation, heuristic algorithms, and metaheuristics. The mechanism of the solution approaches is based on firstly using expected processing times to find a job sequence; then evaluating the obtained job sequences by several simulated trials. Using the one-way ANOVA test, these methods have been compared together, and the results show the superiority of metaheuristics, especially simulated annealing, over the other methods


Main Subjects

1. Flapper, S.D.P. and Teunter, R.H. Logistic planning
of rework with deteriorating work-in-process", International
Journal of Production Economics, 88, pp. 51-59
2. Cao, Y., Subramaniam, V., and Chen, R. Performance
evaluation and enhancement of multistage
manufacturing systems with rework loops", Computers
& Industrial Engineering, 62, pp. 161-176 (2012).
3. Inderfurth, K., Janiak, A., Kovalyov, M.Y., and
Werner, F. Batching work and rework processes with
limited deterioration of reworkables", Computers &
Operations Research, 33, pp. 1595-1605 (2006).
4. Chiu, S.W., Ting, C.K., and Chiu, Y.S.P. Optimal
production lot sizing with rework, scrap rate, and
service level constraint", Mathematical and Computer
Modelling, 46, pp. 535-549 (2007).
5. Sarker, B.R., Jamal, A.M.M., and Mondal, S. Optimal
batch sizing in a multi-stage production system
with rework consideration", European Journal of Operational
Research, 184, pp. 915-929 (2008).
6. Liu, N., Kim, Y., and Hwang, H. An optimal operating
policy for the production system with rework",
Computers & Industrial Engineering, 56, pp. 874-887
7. Gribkovskaia, I.V., Kovalev, S., and Werner, F.
Batching for work and rework processes on dedicated
facilities to minimize the makespan", Omega, 38, pp.
522-527 (2010).
8. Kang, Y.H., Kim, S.S., and Shin, H.J. A dispatching
algorithm for parallel machines with rework processes",
Journal of the Operational Research Society,
61, pp. 144-155 (2010).
9. Ramezanian, R. and Saidi-Mehrabad, M. Multiproduct
unrelated parallel machines scheduling problem
with rework processes", Scientia Iranica E, 19(6),
pp. 1887-1893 (2012).
10. Taleizadeh, A.A., Jalali-Naini, S.G., Wee, H.M., and
Kuo, T.C. An imperfect multi-product production
system with rework", Scientia Iranica E, 20(3), pp.
811-823 (2013).
11. Sarkar, B., Cardenas-Barron, L.E., Sarkar, M., and
Singgih, M.L. An economic production quantity
model with random defective rate, rework process
and backorders for a single stage production system",
Journal of Manufacturing Systems, 33(3), pp. 423-435
12. Hossain, M.S.J. and Sarker, B.R. Optimal locations
of on-line and o -line rework stations in a serial production
system", International Journal of Production
Research, 54(12), pp. 3603-3621 (2016).
13. Beynaghi, A., Moztarzadeh, F., Shahmardan, A.,
Alizadeh, R., Salimi, J., and Mozafari, M. Makespan
minimization for batching work and rework process
on a single facility with an aging e ect: a hybrid
meta-heuristic algorithm for sustainable production
management", Journal of Intelligent Manufacturing,
(2016). DOI: 10.1007/s10845-016-1223-0.
14. Moussawi-Haidar, L., Salameh, M., and Nasr, W.
Production lot sizing with quality screening and rework",
Applied Mathematical Modelling, 40, pp. 3242-
3256 (2016).
15. Baker, K.R. and Trietsch, D., Principles of Sequencing
and Scheduling, New York, Wiley (2009).
1700 B. Bootaki and M.M. Paydar/Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 1688{1700
16. Rinnooy Kan A.H.G., Machine Scheduling Problems:
Classi cation, Complexity and Computations,
The Hague, Netherlands, Martinus Nijho Publishers
17. Palmer, D.S. Sequencing jobs through a multistage
process in the minimum total time: a quick method of
obtaining a near optimum", Journal of the Operational
Research Society, 16, pp. 101-107 (1965).
18. Campbell, H.G., Dudek, R.A., and Smith, M.L. A
heuristic algorithm of the n-job, m-machine sequencing
problem", Management Science, 16(10), pp. 630-637
19. Gupta, J.N.D. A functional heuristic algorithm for
ow-shop scheduling problem", Operational Research
Quarterly, 22(1), pp. 39-47 (1971).
20. Nawaz, M., Enscore, J.E., and Ham, I. A heuristic algorithm
for the m-machine, n-job
ow-shop sequencing
problem", Omega, 11(1), pp. 91-95 (1983).
21. Li, X. and Yin, M. A discrete arti cial bee colony
algorithm with composite mutation strategies for permutation

ow shop scheduling problem", Scientia
Iranica E, 19(6), pp. 1921-1935 (2012).
22. Johnson, S.M. Optimal two and three-stage production
schedules with set-up times included", Naval
Research Logistics Quarterly, 1, pp. 61-68 (1954).
23. Holland, J.H., Adaptation in Natural and Arti cial
Systems, Cambridge, MIT Press (1975).
24. Goldberg, D.E., Genetic Algorithms: Search, Optimization
and Machine Learning, Boston, Addison-
Wesley Press (1989).
25. Mahdavi, I., Paydar, M.M., Solimanpur, M., and Heidarzade,
A. Genetic algorithm approach for solving
a cell formation problem in cellular manufacturing",
Expert Systems with Applications, 36(3), pp. 6598-
6604 (2009).
26. Paydar, M.M. and Saidi-Mehrabad, M. A hybrid
genetic-variable neighborhood search algorithm for the
cell formation problem based on grouping ecacy",
Computers & Operations Research, 40(4), pp. 980-990
27. Bootaki, B., Mahdavi, I., and Paydar, M.M. A
hybrid GA-AUGMECON method to solve a cubic cell
formation problem considering di erent worker skills",
Computers & Industrial Engineering, 75, pp. 31-40
28. Kirkpatrick, S., Gelatt, C., and Vecchi, M. Optimization
by simulated annealing", Science, 220(4598), pp.
671-680 (1983).
29. Mladenovic, N. and Hansen, P. Variable neighborhood
search", Computers & Operations Research, 24,
pp. 1097-1100 (1997).