Solving Re-entrant No-wait Flow Shop Scheduling Problem

Document Type : Research Paper

Author

Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran.

Abstract

In this study we consider the production environment of re-entrant flow-shop (RFS) with the objective of minimizing make span of the jobs. In a RFS, at least one job should visit at least one of the machines more than once. In a no-wait flow shop-scheduling problem, when the process of a specific job begins on the first machine, it should constantly be processed without waiting in the line of any machine until its processing is completed on the last one. Integration of the properties of both of these environments, which is applied in many industries such as robotic industries, is not investigated separately. In the paper, we present a simulated annealing (SA) and a genetic algorithm (GA) based on heuristics for the problem. First, we develop the mathematical model for the problem, and then we present the suggested algorithms. For small scale, results of GA and SA are compared to GAMS. For large-scale problems, results of GA and SA are compared to each other. Computational results show that both SA ad GA algorithms perform properly but totally, SA is likely to turn out well in finding better solutions especially in large-scale problems.     

Keywords

Main Subjects

References

[1]     Hall, N.G., Sriskandarajah, C., (1996). “A survey of machine scheduling problems with blocking and no-wait in process”, Operations Research, 44: 510-525.
[2]     Aldowaisan, T., Allahverdi, Ali., (2003). “New  heuristics for no-wait flowshops to minimize makespan”, Computers & Operations Research, 30: 1219–1231.
[3]     Gupta, J.N.D., Strusevich, V.A., Zwaneveld, CM., (1997). “Two-stage no-wait scheduling models with setup and removal times separated”, Compute Operation Research, 24: 1025–1031.
[4]     Choi, S.W., Kim, Y.D. (2008). “Minimizing  makespan on an -machine re-entrant flowshop”, Computers & Operations Research, 35: 1684-1696.
[5]     Chen, J.S., Pan, J.C.H., Lin, C.M., (2008). “A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem”, Expert Systems with Applications, 34: 570-577.
[6]     Jing, C., Tang, G., Qian, X., (2008). “Heuristic algorithms for two machine re-entrant flow shop”, Theoretical Computer Science, 400: 137-143.
[7]     Huang, R.H., Yu, S.C., Kuo, C.W., (2014). “Reentrant two-stage multiprocessor flow shop scheduling with due windows”, The International
Journal of Advanced Manufacturing Technology, 71: 1263-1276.
[8]     Li, Z.C., Qian, B., Hu, R., Zhang, C.S., Li, K., (2013). “A self-adaptive hybrid population-based incremental learning algorithm for M-machine reentrant permutation flow-shop scheduling”, Intelligent Computing Theories, 7995: 8-20.
[9]     Jing, C., Huang, W., Tang, G., (2011).  “Minimizing total completion time for re-entrant flow shop scheduling problems”, Theoretical Computer Science, 412: 6712-6719.
[10] Choi, S.W., Kim, Y.D., (2009). “Minimizing total tardiness on a two-machine re-entrant flow shop”, European Journal of Operational Research, 199: 375-384.
[11] Pan, J.C.H., Chen, J.S., (2003). “Minimizing  makespan in reentrant permutation flow-shops”, Journal of Operational Research Society, 57: 642- 653.
[12] Adressi, A., Hassanpour, S., Azizi, V., (2016). “Solving group scheduling problem in no-wait flexible flowshop with random machine breakdown”, Decision Science Letters, 5(1): 157-168.
[13] Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.R., (1979). “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Annals of discrete mathematics, 5: 287-326.
Journal of Industrial Engineering Research in Production Systems
Volume 4, Issue 9
Special Issue: 11th & 12th International Conference on Industrial Engineering
March 2017
Pages 271-279

Files

Share

How to cite

Statistics