KaydedilenlerDerginizi ekleyin

Dergiler / Endüstri Mühendisliği / 2011 / Cilt: 22 - Sayı: 4

Sıra bağımlı hazırlık süreli iki ölçütlü tek makine çizelgeleme problemi için sezgisel bir çözüm yöntemi

A heuristic for bicriteria single machine scheduling problem with sequence dependent setup times

Feriştah ÖZÇELİK
Tuğba SARAÇ
Sayfa
48–57
Yayın Tarihi
2022-10-18
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

Önerilen yöntemlerin etkinliği rassal olarak türetilen test problemleri kullanılarak araştırılmıştır.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez:Bu çalışmada sıra bağımlı hazırlık süreli, son işin tamamlanma zamanını ve toplam gecikmeyi en aza indirmeyi amaçlayan tek makine çizelgeleme problemi ele alınmıştır.
📊
Temel Bulgular & Veri:Bu problem NP-zor sınıfında yer almaktadır.
💡
Sonuç & Katkı:Önerilen yöntemlerin etkinliği rassal olarak türetilen test problemleri kullanılarak araştırılmıştır.
🔬Tür:Literatür & Derleme Çalışması
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Alan Parametreleri

Özet

Bu çalışmada sıra bağımlı hazırlık süreli, son işin tamamlanma zamanını ve toplam gecikmeyi en aza indirmeyi amaçlayan tek makine çizelgeleme problemi ele alınmıştır. Bu problem NP-zor sınıfında yer almaktadır. Problemin çözümü için ilk olarak, SST (en kısa hazırlık süresi) sıralama kuralının ağırlıklandırılmış hali olan yeni bir sıralama kuralı (WSST) önerilmiştir. Bu sıralama kuralı, literatürde yer alan EDD (en küçük teslim zamanı), SST ve ATCS (Apparent Tardiness Cost with Setups) sıralama kurallarıyla karşılaştırılmıştır. Daha sonra, önerilen sıralama kuralının çözümlerini, bir yerel arama yöntemiyle iyileştirme amacını güden yeni bir sezgisel algoritma önerilmiştir. Önerilen yöntemlerin etkinliği rassal olarak türetilen test problemleri kullanılarak araştırılmıştır.

Abstract

In this study, the bi-criteria scheduling problem of minimizing the makespan and total tardiness on a single machine with sequence dependent setup times is considered. This problem is known as NP-hard. To solve this problem, firstly we propose a new dispatching rule named as WSST that is the weighted form of the SST (Shortest Setup Time) rule. The proposed rule is compared with EDD (Earliest Due Date), SST and ATCS (Apparent Tardiness Cost with Setups) dispatching rules. And then, a new heuristic which improves the solutions of the WSST by a local search algorithm is proposed. The performance of the proposed heuristics is tested by using randomly generated test problems.

🔖

Bu Makaleye Atıf Yap

ÖZÇELİK, F., SARAÇ, T. (2022). Sıra bağımlı hazırlık süreli iki ölçütlü tek makine çizelgeleme problemi için sezgisel bir çözüm yöntemi. Endüstri Mühendisliği, Cilt: 22 - Sayı: 4, 48–57. https://ajindex.com/articles/501198

📄 Tam Metin PDF Okuyucu

📄

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

Kaynakça (15)

  1. Armentano, V.A., Mazzini, R. 2000. “A Genetic Algorithm For Scheduling On A Single Machine With Set-Up Times And Due Dates,” Production Planning and Control, 11, 713–720
  2. Asano, M., Ohta, H. 1999. “Scheduling With Shutdowns And Sequence Dependent Set-Up Times,” International Journal of Production Research, 37, 1661–1676
  3. Chang, T.Y., Chou, F.D., Lee, C.E. 2004. “A Heuristic Algorithm To Minimize Total Weighted Tardiness On A Single Machine With Release Dates And Sequence-Dependent Setup Times,” Journal of the Chinese Institute of Industrial Engineers, 21, 289–300
  4. Chankong, V., Haimes, Y.Y. 1983. “Multiobjective Decision Making: Theory and Methodology”, Elsevier Science Publishing Co, New York
  5. Choobineh, F.F., Mohebbi, E., Khoo, H. 2006. “A Multi-Objective Tabu Search For A Single-Machine Scheduling Problem With Sequence-Dependent Setup Times,” European Journal of Operational Research, 175, 318–337
  6. Ehrgott, M. 2005. “Multicriteria Optimization,” Springer-Verlag, 2nd edition
  7. Eren, T., Guner, E. 2006. “A Bicriteria Scheduling With Sequence Dependent Setup Times,” Applied Mathematics and Computation, 179, 378–385
  8. Franca, P.M., Mendes, A., Moscato, P. 2001. “A Memetic Algorithm For The Total Tardiness Single Machine Scheduling Problem,” European Journal of Operational Research, 132, 224–242
  9. Gagne, C., Price, W.L., Gravel, M. 2002. “Comparing an ACO Algorithm With Other Heuristics For The Single Machine Scheduling Problem With Sequence-Dependent Setup Times,” Journal of the Operational Research Society, 53, 895–906
  10. Gupta, S.R., Smith, J.S. 2006. “Algorithms For Single Machine Total Tardiness Scheduling With Sequence Dependent Setups,” European Journal of Operational Research, 175, 722–739
  11. Kolahan, F., Liang, M. 1998. “An adaptive TS Approach To JIT Sequencing With Variable Processing Times And Sequencedependent Setups,” European Journal of Operational Research, 109, 142–159
  12. Lee, S.M., Asllani, A.A. 2004. “Job Scheduling With Dual Criteria And Sequence-Dependent Setups: Mathematical Versus Genetic Programming,” Omega, 32, 145–153
  13. Luc, D.T. 1989. “Theory of Vector Optimization,” Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin
  14. Mendes, A.S., Franca, P.M., Moscato, P. 2002. “Fitness Landscapes For The Total Tardiness Single Machine Scheduling Problem,” Neural Network World, 12, 165–180
  15. Miller, D.M., Chen, H.C., Matson, J., Liu, Q. 1999. “A Hybrid Genetic Algorithm For The Sing