Makespan Algorithms and Heuristic for Internet-Based Collaborative Manufacturing Process Using Bottleneck Approach

Salleh Ahmad BAREDUAN, Sulaiman HASAN

.

DOI: 10.4236/jsea.2010.31011                

Abstract

This paper presents makespan algorithms and scheduling heuristic for an Internet-based collaborative design and manufacturing process using bottleneck approach. The collaborative manufacturing process resembles a permutation re-entrant flow shop environment with four machines executing the process routing of M1,M2,M3,M4,M3,M4 in which the combination of the last three processes of M4,M3,M4 has high tendency of exhibiting dominant machine character-istic. It was shown that using bottleneck-based analysis, effective makespan algorithms and constructive heuristic can be developed to solve for near-optimal scheduling sequence. At strong machine dominance level and medium to large job numbers, this heuristic shows better makespan performance compared to the NEH.

Keywords

Heuristic, Re-Entrant Flow Shop, Bottleneck, Scheduling, Dominant Machine

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. Pinedo, “Scheduling: theory, algorithms, and sys-tems,” 2nd Edtion, Upper Saddle River, Prentice-Hall, N.J., 2002.
[2]	Z. Lian, X. Gu, and B. Jiao, “A novel particle swarm optimization algorithm for permutation flow-shop sched-uling to minimize makespan,” Chaos, Solitons and Frac-tals, Vol. 35, No. 5, pp. 851–861, 2008.
[3]	S. C. Graves, H. C. Meal, D. Stefek, and A. H. Zeghmi, “Scheduling of re-entrant flow shops,” Journal of Opera-tions Management, Vol. 3, No. 4, pp. 197–207, 1983.
[4]	J. S. Chen, “A branch and bound procedure for the reen-trant permutation flow-shop scheduling problem,” Inter-national Journal of Advanced Manufacturing Technology, Vol. 29, pp. 1186–1193, 2006.
[5]	S. W. Choi, and Y. D. Kim, “Minimizing makespan on a two-machine reentrant flowshop,” Journal of The Opera-tional Research Society, Vol. 58, pp. 972–981, 2007.
[6]	E. Demirkol, R. Uzsoy, “Decomposition methods for reentrant flow shops with sequence dependent setup times,” Journal of Scheduling, Vol. 3, pp. 115–177, 2000.
[7]	J. C. Pan, and J. S. Chen, “Minimizing makespan in re-entrant permutation flow-shops,” Journal of Operation Research Society, Vol. 54, pp. 642–653, 2003.
[8]	S. W. Choi, Y. D. Kim, and G. C. Lee, “Minimizing total tardiness of orders with reentrant lots in a hybrid flow-shop,” International Journal of Production Research, Vol. 43, pp. 2049–2067, 2005.
[9]	S. W. Choi, and Y. D. Kim, “Minimizing makespan on an m-machine re-entrant flowshop,” Computers & Opera-tions Research, Vol. 35, No. 5, pp. 1684–1696, 2008.