İsmail KARAOĞLAN, Fulya ALTIPARMAK, F. Nergis AKGÜL, M. Çağrı DÜZCE, Ozan ERDEM, Aslı KERİMOĞLU, Menekşe KOÇAK

TUSAŞ-Türk Havacılık ve Uzay Sanayii A.Ş.’ de paralel makinalarda çizelgeleme problemi için bir çözüm yaklaşımı

Bu projede, TUSAŞ-Türk Havacılık ve Uzay Sanayi A.Ş.’nin CNC Profil ve Parça İmalat Merkezi’ndeki sıra bağımlı hazırlık zamanının söz konusu olduğu paralel makinelerde çizelgeleme problemi dikkate alınmıştır. Problem için öncelikle karışık tamsayılı doğrusal programlama modeli geliştirilmiştir. Dikkate alınan çizelgeleme probleminin bir NP-zor problem olması ve çizelgelenecek iş gruplarının en az 50 yada daha fazla işten oluşması nedeniyle CPLEX gibi bilinen çözücüler ile eniyi çözüme ulaşmak mümkün değildir. Bu nedenle, makul zaman dilimleri içerisinde eniyi ya da eniyiye yakın iş çizelgelerini elde edebilmek için tavlama benzetimi (TB) algoritmasına dayalı bir sezgisel algoritma geliştirilmiştir. Geliştirilen algoritmanın performansı, çözüm kalitesi açısından çok başlangıçlı yerel arama algoritması ile karşılaştırmalı olarak incelenmistir. Küçük boyutlu test problemlerinde her iki algoritma aynı performansa sahipken, büyük boyutlu test problemlerinde TB algoritmasının daha iyi bir performans sergilediği görülmüştür. Ayrıca, geliştirilen sezgisel algoritma ile bütünleşik çalışan bir arayüz tasarlanmıştır. Bu arayüz ile firma veri tabanından çizelgelenecek iş listelerinin çekilmesine dayalı olarak istasyon bazında iş çizelgelerinin oluşturulması sağlanmıştır.

A solution approach for parallel machine scheduling problem in TAI-Turkish Aerospace Industries Inc.

In this project, a parallel machine scheduling problem with sequence dependent setup times in the CNC Profile and Part Manufacturing Center of Turkish Aerospace Industries, Inc. has been considered. Firstly, a mixed integer linear programming model is developed for the problem. Since the problem is an NP-hard problem and the work groups to be scheduled consist of 50 or more works, it is not possible to obtain optimal solution with well known solvers such as CPLEX. Therefore, in order to obtain optimal or near optimal schedules in an acceptable time period, a heuristic algorithm based on simulated annealing (SA) algorithm is developed. The performance of the developed algorithm is examined by using multi start local search algorithm in terms of solution quality. While both of the algorithms have same performance for small-size problems, SA algorithm exhibits better performance than multi start local search algorithm for large-size problems. Moreover, an interface integrated with the developed heuristic algorithm is designed. By means of the interface, schedules for the works drawn from the database of firm for each station are obtained.

PDF

___

1. Anghinolfi, D., Paolucci, M. 2006. "Parallel Machine Total Tardiness Scheduling with a New Hybrid Metaheuristic Approach", Computers and Operations Research, 34, 3471-3490.
2. Ferretti, E., Esquivel S. 2005. "An Efficient Approach of Simple and Multirecombinated Genetic Algorithms for Parallel Machines Scheduling", IEEE Congress on Evolutionary Computation, CEC 2005. 1340-1347.
3. Kim, D. W., Kim, K. H., Jang, W., Chen, F.F. 2002. "Unrelated Parallel Machine Scheduling With Setup Times Using Simulated Annealing", Robotics and Computer Integrated Manufacturing, 18, 223-231.
4. Kim, S., Choi, H.S., Lee, D.H. 2006. "Tabu Search Heuristics For Parallel Machine Scheduling With Sequence-Dependent Setup And Ready Times", LNCS 3982, 728-737.
5. Kirkpatrick, S., Gerlatt, Jr, C.D. ve Vecchi, M.P. 1983. "Optimization by Simulated Annealing", Science, 220(4598), 671-680.
6. Lee, Y. H., Pinedo, M. 1995. "Scheduling Jobs On Parallel Machines With Sequence-Dependent Setup Times", European Joumal Of Operational Research, 100, 464-474.
7. Logendran, R., Mcdonell, B., Smucker, B. 2006. "Scheduling Unrelated Parallel Machines With Sequence-Dependent Setups", Computers and Operations Research,34, 3420-3438.
8. Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E. 1953. "Equaiton of State Calculation by Fast Computing Machines, Journal of Chemical Physics, 21, 1087-1092.
9. Nessah. R., Chu. C., Yalaoui. F. 2005. "An Exact Method For Pm/Sds, Ri/ΣNi= 1 Ci Problem, Computers and Operations Research, 34, 2840 – 2848.
10. Nessah, R., Yalaoui, F., Chu, C. 2006. "A Branchand- Bound Algorithm to Minimize Total Weighted Completion Time on Identical Parallel Machines with Job Release Dates", Computers and Operations Research, 35,1176-1190.
11. Omar, M.K., Teo, S.C. 2006. "Minimizing The Sum of Earliness/Tardiness in Identical Parallel Machines Schedule with Incompatible Job Families: An Improved MIP Approach", Applied Mathematics and Computation, 181, 1008-1017.
12. Pinedo, M.,L. 2004. Planning and Scheduling in Manufacturing and Services, Springer, New York.
13. Rabadi, G., Moraga, R.J., Al-Salem, A. 2006. "Heuristics For The Unrelated Parallel Machine Scheduling Problem with Setup Times", Journal of Intelligent Manufacturing, 17, 85-97.
14. Rocha, P.L., Ravetti, M.G., Mateus, G.R., Pardalos, P.M. 2006. "Exact Algorithms for a Scheduling Problem with Unrelated Parallel Machines and Sequence and Machine- Dependent Setup Times", Computers and Operations Research, 35, 1250-1264.
15. Sivrikaya. F., Ulusoy, G. 1998. "Parallel Machine Scheduling with Earliness and Tardiness Penalties", Computers and Operations Research, 26, 773-787.
16. Tahar, D. N., Yalaoui, F., Chu C., Amodeo, L. 2005. "A Linear Programming Approach for Identical Paralel Machine Scheduling with Job Splitting and Sequence- Dependent Setup Times", International Journal of Production Economics, 99, 63-73.
17. Tamaki, H., Murao, H., Kitamura, S. 2003. "A Heuristic- Based Hybrid Solution for Parallel Machine Scheduling Problems with Earliness and Tardiness Penalties", IEEE Congress on Emerging Technologies and Factory Automation 2, 239-344.
18. Weng, M. X., Lu, J., Ren H. 2001. Unrelated Parallel Machine Scheduling with Setup Consideration and a Total Weighted Completion Time Objective, International Journal of Production Economics, 70, 215-226.

ISSN: 1300-3410
Yayın Aralığı: Yılda 3 Sayı
Başlangıç: 1989
Yayıncı: TMMOB MAKİNA MÜHENDİSLERİ ODASI

Arşiv