İçeriğe atla
Arama sonuçlarına dön

İş İstasyonu Çizelgeleme

Ortaya koyan
Pinedo, M. L.
Yıl
2016
Tür
Combinatorial scheduling problem
Aile
Optimization

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

İş istasyonu çizelgeleme, bir dizi görevin (işin) bir dizi makineye (kaynağa) zaman içinde atanması, öncelik ve kapasite kısıtlarına tabi olarak, toplam tamamlama süresi (makespan), gecikme veya maliyet gibi performans metriklerini optimize etme hedefiyle yapılan bir problemdir.

İş istasyonu problemi, operasyon araştırmalarında klasik bir kombinatoryal optimizasyon problemidir ve sezgisel yöntemlerle (açgözlü sevk kuralları, benzetilmiş tavlama, genetik algoritmalar) ve kesin algoritmalarla (dallanma ve sınırlandırma, kısıt programlama) ele alınır. İmalat, proje yönetimi ve hesaplamalı çizelgeleme için temeldir.

Yöntemin mantığı

10 makinelik küçük bir makine atölyesi hayal edin. Bir müşteri siparişi (iş), her biri farklı makinelerde bir dizi işlem gerektiren 5 parçadan oluşur: Parça 1'in Makine A'da işlenmesi, ardından Makine C'de delinmesi gerekir. Parça 2'nin Makine B'de delinmesi, ardından Makine D'de kaynaklanması gerekir. Tüm parçalar nihai montaj için bir araya gelir. Zorluk: toplam tamamlama süresini en aza indirmek, makine kapasitesini aşmamak ve her parça için işlem sırasını korumak için tüm işlemleri çizelgelemek. Parça 1'i Makine A'ya çok geç atarsanız, Makine C boşta kalır. Makine C'yi aşırı yüklerseniz, her şey aksar. İş istasyonu problemi bu karmaşıklığı yakalar: 100 iş ve 20 makine ile olası çizelgelerin sayısı astronomiktir, bu da kesin çözümü pratik olmaktan çıkarır. Bunun yerine, hızlı bir şekilde iyi (mutlaka optimal olmayan) bir çizelge bulmak için sezgisel yöntemler kullanılır.

Tarih

İş istasyonu çizelgeleme problemi, 1950'lerde operasyon araştırmalarında bir araştırma problemi olarak ortaya çıktı. Johnson'ın (1954) öncü çalışması iki makine problemini optimal olarak çözdü; Fisher ve Thompson (1963) bugün hala kullanılan referans problemlerini yarattı. Problem NP-zorludur (1970'lerde kanıtlanmıştır), bu da sezgisel ve meta-sezgisel yöntemlerin geliştirilmesini teşvik etmiştir. Modern yaklaşımlar arasında kısıt programlama (1990'lar-2000'ler), genetik algoritmalar ve hibrit yöntemler yer almaktadır. İş istasyonu çizelgeleme artık imalatın ötesinde bulut bilişim, telekomünikasyon ve ulaşıma kadar uzanan uygulamalara sahip olgun bir alandır.

Ne zaman kullanılır?

İş istasyonu çizelgeleme, birden fazla makine/kaynağa ve farklı işlem sıralarına sahip işlere sahip herhangi bir üretim veya hizmet ortamına uygulanır. Tipik uygulamalar arasında makine atölyeleri, matbaalar, yarı iletken wafer üretimi, hastaneler (cerrahi süit çizelgeleme) ve proje çizelgeleme bulunur. İş karmaşıklığının yüksek olduğu (iş başına birden fazla işlem), makine kullanımının kritik olduğu veya teslim tarihlerinin sıkı olduğu durumlarda kullanın. Montaj hattı ortamlarında (doğrusal akış) veya basit, tek makine işlemlerinde daha az kritiktir.

Sınırlar ve dikkat edilmesi gerekenler

  • Kombinatoryal karmaşıklık: optimal çözümler bulmak NP-zorludur; pratik çözümler küresel olarak optimal olmayabilecek sezgisel yöntemler gerektirir
  • Sezgisel çözümler bağlama bağlıdır; bir atölye için iyi çalışan bir kural, başka bir atölyede kötü performans gösterebilir, bu da ayar ve doğrulama gerektirir
  • Statik girdi (sabit işler ve makineler) varsayar; gerçek atölyeler dinamik gelişler, iptaller ve ekipman arızaları yaşar, bu da sık sık yeniden çizelgeleme gerektirir
  • Çizelge kararlılığı: çizelgelerdeki sık değişiklikler (yeni işler veya kesintiler nedeniyle) maliyetleri artırabilir ve çalışanlar ve müşterilerle koordinasyonu karmaşıklaştırabilir

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Basit çizelgeleme kurallarının başa çıkamayacağı karmaşık, gerçekçi kısıtları (öncelik, makine yetenekleri, teslim tarihleri) barındırır
  • Rastgele kurallar yerine ilgili iş metriklerini (makespan, gecikme, makine kullanımı) optimize eder
  • Kesintilere hızlı yanıtı mümkün kılar; bir makine arızalandığında veya acil bir iş geldiğinde çizelgeleme algoritmaları revize edilmiş planlar oluşturabilir
  • Matematiksel formülasyon, hassasiyet analizi ve ödünleşme keşfine (örneğin, gecikme ve makespan) olanak tanır
  • Verimli yazılım araçları ve olgun meta-sezgisel algoritmalar tarafından desteklenir

Uygulama alanları

  • Bir hassas makine atölyesi, 15 CNC makinesinde 200'den fazla özel parçayı çizelgelemek için benzetilmiş tavlama ile iş istasyonu çizelgeleme kullanır, makespan'ı %15 azaltır ve zamanında teslimatı %85'ten %95'e çıkarır
  • Bir yarı iletken üretim tesisi, 50'den fazla araçta 500'den fazla işlem adımını yönetmek için kısıt tabanlı çizelgeleme uygular, wafer döngü süresini en aza indirir ve süreç içi envanteri %20 azaltır
  • Bir matbaa şirketi, farklı yeteneklere sahip 8 baskı makinesine baskı işlerini atamak, iş karışımını (yüksek hacimli ve özel) optimize etmek ve geçiş süresini en aza indirmek için dinamik iş istasyonu çizelgeleme kullanır
  • Bir hastane çizelgeleme ekibi, cerrahları, cerrahi ekipleri ve ekipmanları koordine ederek ameliyathane kullanımını %65'ten %82'ye çıkararak ameliyathane çizelgelemesi için iş istasyonu algoritmaları uygular

Nasıl çalışır?

Nasıl çalışır?

1

İşlemlerin sıraları, makine gereksinimleri, işleme süreleri ve teslim tarihleri ile işleri (siparişler, görevler) tanımlayın. Mevcut makineleri ve bunların kullanılabilirlik pencerelerini tanımlayın.

2

Kısıtları belirtin: işlem önceliği (Parça 1, Parça B'ye başlamadan önce A işlemini bitirmelidir), kapasite (her makine aynı anda bir işi işleyebilir) ve isteğe bağlı olarak, yayınlanma süreleri ve teslim tarihleri.

3

Her makinede işleri sıralamak için bir sevk kuralı (örneğin, en kısa işlem süresi, en erken teslim tarihi, kritik oran) uygulayarak ilk çizelgeyi oluşturun.

4

Yerel arama veya popülasyon tabanlı yöntemler aracılığıyla çizelgeyi iyileştirmek için meta-sezgisel yöntemler (benzetilmiş tavlama, tabu arama, genetik algoritmalar, karınca kolonisi optimizasyonu) kullanın.

5

Çizelge kalitesini değerlendirin (makespan, gecikme, boşta kalma süresi, tampon süresi). Kabul edilebilirse uygulayın; aksi takdirde, parametreleri ayarlayın ve yeniden optimize edin.

Sık yapılan hatalar

  • Yanlış metriği optimize etmek; makine kullanımını en üst düzeye çıkarmak iş gecikmesini artırabilir, tüm teslim tarihlerini karşılamak ise önemli boş zaman gerektirebilir
  • Kurulum sürelerini ve geçişleri göz ardı etmek; boş zamanı en aza indiren ancak sık, zaman alan kurulumlar gerektiren bir çizelge pratikte optimal olmayabilir
  • Sezgisel çizelgelerin gerçek atölye davranışı karşısında doğrulanmadan aşırı güvenilmesi; kısıtlar genellikle modelin yakaladığından daha karmaşıktır

Sık sorulan sorular

Makespan nedir ve neden önemlidir?

Makespan, ilk işlemin başlangıcından son işlemin tamamlanmasına kadar geçen toplam süredir. Ekipman kullanımı, nakit akışı (daha hızlı tamamlama = daha hızlı ödeme) ve müşteri memnuniyeti ile doğrudan ilişkilidir. Makespan'ı en aza indirmek, iş istasyonu çizelgelemede yaygın birincil hedeftir.

Statik ve dinamik iş istasyonu çizelgeleme arasındaki fark nedir?

Statik çizelgeleme, tüm işlerin önceden bilindiğini varsayar; sabit bir küme optimize edilir. Dinamik çizelgeleme, zaman içinde gelen işleri ele alır; yeni işler geldikçe veya kesintiler meydana geldikçe çizelgeler revize edilir. Çoğu gerçek atölye dinamiktir, bu da hızlı yeniden optimizasyon algoritmaları gerektirir.

Hangi sevk kuralını kullanmalıyız?

Tek bir kural baskın değildir. En Kısa İşlem Süresi (SPT) makespan'ı en aza indirir; En Erken Teslim Tarihi (EDD) gecikmeyi en aza indirir; Kritik Oran her ikisini de dengeler. Atölyenizin öncelikleri ve kısıtları için en uygun olanı bulmak üzere geçmiş veriler veya simülasyon ile kuralları test edin.

İş istasyonu çizelgeleme, çalışan becerilerini ve çapraz eğitimi ele alabilir mi?

Evet, kaynak modelini genişleterek: sadece 'Makine A' yerine, 'Çalışan 1 ile Makine A' veya 'Çalışan 2 ile Makine A'yı belirtin. Ancak bu, problem karmaşıklığını artırır; çizelgeleme yazılımınızın çoklu kaynak kısıtlarını desteklediğinden emin olun.

İlgili yöntemler

Kaynaklar

  1. Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.

    DOI kaynağını aç
    Kopyalandı.
  2. Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.

    DOI kaynağını aç
    Kopyalandı.