Clustered Absolute Bottleneck Adjacent Matching Heuristic for Re-Entrant Flow Shop

Abstract:

The problem illustrated in this paper resembles a four machine permutation re-entrant flow shop with the process routing of M1,M2,M3,M4,M3,M4 where M1 and M4 have high tendency of being the dominant machines. Due to the re-entrant and permutation nature of the process routing, the actual bottlenecks were identified as M1 and combinations of M4+M3+M4. A constructive bottleneck-based heuristic known as C-ABAM was developed to minimise the makespan of the four machine permutation re-entrant flow shop using bottleneck analysis. The results showed that C-ABAM produces better result than the original ABAM heuristic introduced by Bareduan and Hasan in 2009. It was shown that at any P1 dominance level value, the C-ABAM heuristic was capable to produce near optimal results for the 6 jobs problem sizes studied. The C-ABAM heuristic was also capable to generate results which are very compatible to the NEH. To some extent, within 6 jobs problems simulation conducted during the study, the C-ABAM shows marginally better makespan performance compared to the NEH at strong dominance level.

• Periodical: Applied Mechanics and Materials (Volumes 465-466)
• Pages: 1138-1143
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.465-466.1138
• Online since: December 2013
• Authors: Salleh Ahmad Bareduan, Isstella Mengan Gani
• Keywords: Bottleneck, Heuristic, Re-Entrant Flow Shop, Scheduling

References

[1] I.A. El-Khouly, K.S. El-Kilany, A.E. El-Sayed, Modelling and simulation of re-entrant flow shop scheduling: An application in semiconductor manufacturing. Proceeding of the International Conference on Computers & Industrial Engineering, CIE, 6-9 July (2009).

DOI: 10.1109/iccie.2009.5223754

[2] A. Che, M. Chabrol, M. Gourgand, Y. Wang, Scheduling multiple robots in a no-wait re-entrant robotic flowshop. International Journal of Production Economics 135(1) (2012) 199-208.

DOI: 10.1016/j.ijpe.2011.07.008

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

DOI: 10.1016/j.eswa.2010.08.139

[4] J. Adams, E. Balas, D. Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science 34 (1988) 391-401.

DOI: 10.1287/mnsc.34.3.391

[5] S. Mukherjee, A.K. Chatterjee, Applying machine based decomposition in 2-machine flow shops, European Journal of Operational Research 169 (2006) 723-741.

DOI: 10.1016/j.ejor.2004.10.028

[6] A.A. Kalir, S.C. Sarin, A near optimal heuristic for the sequencing problem in multiple-batch flow-shops with small equal sublots, The International Journal of Management Science (Omega) 29 (2001) 577-584.

DOI: 10.1016/s0305-0483(01)00046-9

[7] J.B. Wang, F. Shan, B. Jiang, L.Y. Wang, Permutation flow shop scheduling with dominant machines to minimize discounted total weighted completion time, Applied Mathematics and Computation 182(1) (2006) 947-957.

DOI: 10.1016/j.amc.2006.04.052

[8] E. Demirkol, R. Uzsoy, Decomposition methods for reentrant flow shops with sequence dependent setup times, Journal of Scheduling 3 (2000) 115-177.

DOI: 10.1002/(sici)1099-1425(200005/06)3:3<155::aid-jos39>3.0.co;2-e

[9] S.A. Bareduan, S. Hasan, Bottleneck-Based heuristic for Re-entrant Flow Shop with Two Potential Dominant Machine, Proceedings of the International Conference on Computers and Industrial Engineering (CIE 39), Troyes, France, 6-9 July 2009. pp.176-181.

DOI: 10.1109/iccie.2009.5223957