Atölye tipi çizelgelemede komşuluk yapılarının tabu arama tekniği ile karşılaştırılması

Çizelgeleme üretim planlama ile beraber, bir imalat sisteminin etkinlik ve verimliliğini belirleyen önemli bir fonksiyondur. Bu yüzden, eğer atölye düzeyi ne kadar iyi çizelgelenebilirse, imalat sisteminin etkinlik ve verimliliği o oranda arttırılmış olur. Atölye tipi üretimde etkinliğin (tabii yapısı gereği) genel olarak düşük olduğu düşünüldüğünde, çizelgeleme fonksiyonunun önemi daha iyi anlaşılmaktadır. Bu çalışmanın amacı, komşuluk araması temelinde, çağdaş optimizasyon teknikleriyle daha iyi çizelgeleme yöntemlerinin oluşturulmasına katkı sağlamaktır. Atölye tipi üretim çizelgeleme problemlerinin çeşitli yerel arama, genetik algoritma, benzetimli tavlama ve tabu arama gibi komşuluk araştırması temeline dayanan arama yöntemleriyle çözümünde komşuluk yapısı çok önemli bir Unsur olarak ortaya çikar. Çünkü bu yöntemlerde kullanılan komşu çözüm üretme düzeneğinin yapısının çözüm kalitesini etkilediği düşünülmektedir. Bu çalışmada, literatürde yer alan 5 komşuluk yapısı ile bu çalışma kapsamında geliştirilen yeni bir komşuluk yapısının Gantt diyagramları üzerinde detaylı açıklanması ve birbirleriyle karşılaştırılması amaçlanmıştır. Bu amaçla oluşturulan tabu arama algoritması Pascal dili ile programlanmıştır. Sonuçta, amaçlanan yeni komşuluk yapısının, komşuluk arama yöntemleriyle atölye tipi çizelgelemede etkinlikle kullanılabileceği gibi bazı sonuçlar ifade edilmiştir.

A Comparison of the neighbourhood structures in job-shop scheduling by the tabu search procedure

Scheduling together with production planning is an important function which determines the efficiency and productivity of a manufacturing system. Therefore, the much better a job shop level is scheduled, the more likely the efficiency and productivity of the manufacturing system can be increased. When it is conceived that the efficiency of the job shop production is intrinsically low, the important of the scheduling function will be realized well. The aim of this paper is to contribute to creating of the better scheduling methods by modern optimization techniques based on neighbourhood search. Neighbourhood structure is an important element among the search methods based neighbourhood search such as local search, genetic algorithm, simulated annealing, tabu search etc. for job shop scheduling. Because the neighbourhood relationships used in these methods affect the solution quality. It is aimed to compare the 5 neighbourhood structures from the literature and a new neighbourhood structure developed in this paper. As regards the neighbourhood structures, the detailed explanations on Gantt diagrams are given. We compare these neighbourhoods by the tabu search procedure coded in Pascal. In conclusion, it is stated that the proposed neighbourhood structure can efficiently be used in the neighbourhood search methods for job shop scheduling.

___

  • 1. Pinedo, M., Scheduling: Theory, Algorithms and Systems, Prentice-Hall, New Jersey, 1995.
  • 2. Geyik, F. & Cedimoglu, I.H., "A review of the production scheduling approaches based-on artificial intelligence and the integration of process planning and scheduling", in A. Belhi, P.J. Erard and A. Bouras (Ed.), Proceedings on Swiss Conference of CAD/CAM'99, Neuchatel University, Switzerland, 22-24 February,pp. 167-174, 1999.
  • 3. Baker, K.R., Elements Of Sequencing and Scheduling, Dartmounth College, Hannover, 1994.
  • 4. Glover, F., "Future paths for integer programming and links to artificial intelligence", Computers and Operations Research, Vol.13. No.5, pp.533-549, 1986.
  • 5. Glover, F., "Tabu Search - Part I", ORSA Journal on Computing, Summer, Vol.1, No.3, pp.190-206, 1989.
  • 6. Glover, F., "Tabu Search - Part II", ORSA Journal on Computing, Winter, Vol.2, No.1, pp.4-32, 1990.
  • 7. Brucker, P., Scheduling Algorithms, Springer- Verlag, Berlin, 1995.
  • 8. Fisher, H. & Thompson, G.L., "Probabilistic learning combinations of local job-shopscheduling rules", in J.F. Muth and G.L. Thompson (Ed.), Industrial Scheduling, Prentice Hall, Englewood Cliffs, New Jersey, pp.225-251, 1963.
  • 9. Brucker, P., Jurisch, B. & Sievers, B., A Branch and Bound Algorithm for the Job-Shop Scheduling Problem, Discrete Applied Mathematics, Vol.49, pp. 107-127, 1994.
  • 10. Laarhoven, P.J.M. Van, Aarts, E.H.L. & Lenstra, J.K., Job Shop Scheduling by Simulated Annealing, Operational Research, Vol.40, No. 1, pp. 113-125, 1992.
  • 11. Matsuo, H, Suh, C.J. & Sullivan, R.S., "A controlled search simulated annealing method for the general job-shop scheduling problem", Working Paper No: 03-04-88, Graduate School of Business, The University of Texas at Austin, Austin, Texas, USA, 1988.
  • 12. Nowicki, E. & Smutnicki, C., A Fast Taboo Search Algorithm for the Job Shop Problem, Management Science, Vol.42, pp.797-813, 1996.
  • 13. Balas, E. & Vazacopoulos, A., Guided Local Search with Shifting Bottleneck for Job Shop Scheduling, Management Science, Vol.44, pp.262-275, 1998.
  • 14. Geyik, F., Atölye Tipi Çizelgeleme için Uzman-Tabu Arama Modeli, Doktora tezi, Sakarya Üniversitesi Fen Bilimleri Enstitüsü, 2000.
  • 15. Adams, J., Balas, E. & Zawack, D., The Shifting Bottleneck Procedure for the Job Shop Scheduling, Management Science, Vol.34,pp.391-401, 1988.
  • 16. Lawrence, S., Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (Supplement), Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburg, Pennsylvania, 1984.
  • 17. Applagate, D. & Cook, W., A Computational Study of the Job-Shop Scheduling instance, ORSA Journal on Computing Vol.3, pp. 149-156,1991.
  • 18. Storer, R.H., Wu, S.D. & Vaccari, R., New Search Spaces for Sequencing Instances with Application to Job Shop Scheduling, Management Science Vol.38, pp. 1495-1509, 1992.
  • 19. Tailard, E., Benchmarks for Basic Scheduling Problems, European Journal of Operational Research, Vol.64, No.2, pp 278-285, 1993.