SavedAdd your journal

Journals / Gazi Üniversitesi Fen Bilimleri Dergisi / 2003 / Cilt: 16 - Sayı: 1

An application of Graph theory (Hamiltonian technique) and branch and bound technique on facility layout problems

Tesis düzenlemesi problemlerine karşılaştırmalı iki yaklaşım: (Graf teorisi (Hamilton tekniği) ve dal-sınır tekniği uygulaması)

Orhan TÜRKBEY
Pages
89–103
Publication Date
2022-10-18
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The final solutions are discussed in the last section.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:In this study, two different algorithms have been used to obtain the alternative plant layout in order to minimize the materials handling cost.
📊
Key Findings & Data:The first algorithm is the Foulkes Algorithm, which is essentially the Hamiltonian Cycles with minimized cost and is based on Graph Theory.
💡
Conclusion & Impact:The final solutions are discussed in the last section.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Domain Parameters

Abstract

In this study, two different algorithms have been used to obtain the alternative plant layout in order to minimize the materials handling cost. The first algorithm is the Foulkes Algorithm, which is essentially the Hamiltonian Cycles with minimized cost and is based on Graph Theory. The second one is the Branch and Bound Algorithm, which is considered as the Travelling Salesman Problem. The computer programs of both algorithms have been prepared specifically for the research and no package program has been used. It was observed that the Foulkes Algorithm provides better solutions compared to Branch and Bound Algorithm under necessary and satisfactory conditions. The final solutions are discussed in the last section.

Özet

Bu çalışmada, mevcut bir tesisin Malzeme Yönetimi Maliyet Giderleri (MYMG)'ni enazlamak ve yerleşim düzenlemesini seçenekli olarak elde edebilmek için birbirinden farklı iki değişik algoritma kullanılmıştır. Bu algoritmalardan ilki, Graf (Serim)Teorisi (GT)'ne dayanan ve en küçük maliyetli Hamilton Çevrimleri (HÇ)'ni esas alan Foulkes Algoritması (FA), ikincisi ise Gezgin Satıcı Problemi (GSP) gibi düşünülen probleme Dal-Sınır Algoritması (DSA) uygulamasıdır. Her iki algoritmanın bilgisayar programı tarafımızdan yazılmış (Quick Basic), paket program kullanılmamıştır. Bir grafta HÇ'nin bulunmasında kullanılan FA'nın, DSA'na nazaran, gerek ve yeter şartlar yerine getirildiğinde daha iyi sonuçlar verdiği görülmüş, elde edilen çözüm neticeleri sonuç bölümünde tartışılmıştır.

🔖

Cite This Article

TÜRKBEY, O. (2022). An application of Graph theory (Hamiltonian technique) and branch and bound technique on facility layout problems. Gazi Üniversitesi Fen Bilimleri Dergisi, Cilt: 16 - Sayı: 1, 89–103. https://ajindex.com/articles/521795

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (19)

  1. Baybars, I. and Eastman, C.M., "Enumerating architectural arrangements by generating their underlying graphs", Building and Environment, 7(2): 289-310 (1980)
  2. Bondy, J.A. and Murty, U.S.R., "Graph theory with applications", North Holland, Amsterdam (1976)
  3. Broersma, H.J. and Veldman, H.J., "Around three lemmas in hamiltonian graph theory", in: Topics in Combinatorics and Graph theory, Physica-Verlag, Heidelberg (1990)
  4. Carrie, A.S., Moore, J.M., Roczniak, R. and Seppanen, J.J., "Graph theory and computer aided facilities design", Omega, 6(4): 353-361 (1978)
  5. Clark, J. and Holton, D.A., "A first look at graph theory", World Scientific Pub.Co.Pte.Ltd., Singapore (1991)
  6. Drezner, Z., "DISCON: A new method for the layout problem", Operations Research, 28(6): 1375-1384 (1980)
  7. Foulds, L.R. and Robinson, D.F., "Graph theoretical heuristic for the plant layout problem", I. J. of Prod. Res., 16(1): 27-37 (1978)
  8. Hammouche, A. and Webster, D.B., "Evaluation of an application of graph theory to the layout problem", I. J. of Prod. Res., 23(5): 987-1000 (1985)
  9. Harary, F., Graph theory, Addison Wesley Publishing Co., Boston (1972)
  10. Kaufmann, A., "Methodes et modéles de la recherce operationnelle (Les Mathematiques de l'entreprise)",Dunod, Paris (1968)
  11. Krasikov, I. and Roditty, Y., "A Las-vergnas type theorem for trees", in: Topics in Combinatorics and Graph Theory, Physica-Verlag, Heidelberg (1990)
  12. Lal, T.H. and Spraque, A., "Performance of parallel branch and bound algorithms", IEEE Transactions on Computations, 14(10): 79-81 (1985)
  13. Levin, P.H., "Use of graphs to decide the optimum layout of buildings", The Architects' J. of Infrastructure Library, 4: 809-815, 1223-1224 (1964)
  14. Little, J.D.C., Murty, K.G., Sweeney, D.W. and Karel, C., "An algorithm for the travelling salesman problem", Operations Research, 11(6): 972-989 (1963)
  15. Montreuil, B., Ratliff, H.D. and Goetschalckx, M., "Matching based interactive facility layout." IIE Transactions", 19(3): 271-279 (1987)
  16. Muther, R., "Systematic layout planning (2nd ed.)", Cahners Books, Boston (1974)
  17. Reed, R., "Plant Layout: factors, principles and techniques", Richard D. Irwin Inc., Homewood, Illinois, (1961)
  18. Roth, J., Hashimshory, R. and Wachman, A., "Turning a graph into a rectangular floor plan", Building and Environment, 17(3): 163-173, (1982)
  19. Tompkins, J.A., "Modularity and flexibility: Dealing with future shock in facilities design", Industrial