Zamansal Planlama ve Çizelgeleme
Zamansal planlama ve çizelgeleme, zaman alan, eşzamanlı olarak yürütülebilen ve sınırlı kaynak tüketen eylemleri ele almak için planlamayı genişletmekte, sadece ne yapılacağını değil, ne zaman yapılacağını da belirten planlar üretmektedir.
Tanım
Zamansal planlama, eylemlerin süreleri olduğu ve zamansal ve kaynak kısıtlarına tabi olarak çakışabileceği bir plan üretmektedir; çizelgeleme ise bir dizi faaliyete başlangıç zamanları (ve kaynaklar) atayarak sıralama, son teslim tarihleri ve kapasiteler gibi tüm kısıtların karşılanmasını sağlamaktadır.
Kapsam
Bu konu, açık zaman ve kaynaklarla yapılan planlama ve çizelgelemeyi kapsamaktadır: süreli eylemler, eşzamanlılık ve zamansal kısıtlar, zamansal kısıt ağlarının (basit zamansal problem gibi) gösterimi ve çözümü ile Allen'ın aralık cebiri ve kaynak kısıtlı faaliyetlerin çizelgelemesiyle planlamanın entegrasyonu. Zaman ve kaynak fizibilitesinin eylem seçimiyle birlikte nasıl muhakeme edildiğini ele almaktadır. Saf kaynak-serbest klasik planlama ilgili konularda işlenmektedir.
Temel sorular
- Süreli eylemler ve bunların başlangıç ve bitiş koşulları nasıl temsil edilmektedir?
- Olaylar arasındaki zamansal kısıtlar nasıl modellenmekte ve tutarlılıkları nasıl kontrol edilmektedir?
- Sınırlı kaynaklar eşzamanlı faaliyetler arasında nasıl tahsis edilmektedir?
- Planlama (hangi eylemlerin yapılacağına karar verme) ve çizelgeleme (ne zaman yapılacağına karar verme) nasıl birleştirilmekte veya ayrılmaktadır?
Anahtar kavramlar
- süreli eylemler
- eşzamanlılık ve çakışma
- zamansal kısıtlar
- basit zamansal problem
- Allen'ın aralık cebiri
- kaynak kısıtları
- çizelgeleme
- son teslim tarihleri ve tamamlanma süresi (makespan)
Temel kuramlar
- Zamansal kısıt ağları
- Zaman noktaları arasındaki nicel zamansal kısıtlar, tutarlılığı ve en sıkı sınırları basit zamansal problem için verimli bir şekilde hesaplanabilen bir ağ olarak temsil edilebilmekte, birçok planlayıcı ve çizelgeleyicinin zamansal akıl yürütme omurgasını oluşturmaktadır.
- Nitel zaman için aralık cebiri
- Allen'ın aralık cebiri, zaman aralıkları arasındaki olası nitel ilişkileri (önce, sırasında, çakışır vb.) yakalamakta ve kesin zamanlar bilinmediğinde zamansal bilgi hakkında akıl yürütmeyi desteklemektedir.
- Planlamayı çizelgelemeyle entegre etme
- Gerçekçi problemler, eylemlerin seçilmesini ve bunlara zaman ve kaynakların birlikte atanmasını gerektirmektedir; otomatik planlama kuramı, süreli eylemleri, eşzamanlılığı ve kaynak kısıtlarını, eylem seçimini kısıt tabanlı çizelgelemeyle birleştiren uzantılar olarak ele almaktadır.
Klinik önem
Zamansal planlama ve çizelgeleme, uzay aracı ve gezgin operasyonlarında, üretim ve proje çizelgelemesinde, ulaşım ve mürettebat çizelgelemesinde ve zamanlanmış, eşzamanlı, kaynak kısıtlı faaliyetlerin koordine edilmesi gereken her türlü ortamda temel bir öneme sahiptir; bu tür sistemler gerçek uzay görevleri için planlanmış operasyonlara sahiptir.
Tarihçe
Nitel zamansal akıl yürütme, Allen'ın aralık cebiri (1983) tarafından, nicel zamansal kısıt ağları ise Dechter, Meiri ve Pearl (1991) tarafından formüle edilmiştir. Bu temeller, 2000'li yılların başında PDDL'ye eklenen süreli eylem modelleriyle birlikte, otonom uzay aracı kontrolü gibi uygulamalarda kullanılan zamansal planlayıcıları mümkün kılmıştır.
Öne çıkan isimler
- James F. Allen
- Rina Dechter
- Judea Pearl
- Itay Meiri
- Nicola Muscettola
İlgili konular
Temel eserler
- dechter1991
- allen1983
Sıkça sorulan sorular
- Planlama ve çizelgeleme arasındaki fark nedir?
- Planlama, hedeflere ulaşmak için hangi eylemlerin yapılacağına karar verirken, çizelgeleme ise sıralama ve kapasite kısıtları göz önüne alındığında bu eylemlerin ne zaman gerçekleşeceğine ve hangi kaynakları kullanacaklarına karar vermektedir. Birçok gerçek problem her ikisini de gerektirmekte olup, zamansal planlama eylem seçimini zamanlama ve kaynak muhakemesiyle bütünleştirmektedir.
- Basit zamansal problem nedir?
- Basit zamansal problem, her bir kısıtın iki zaman noktası arasındaki farkı bir aralık ile sınırladığı bir zamansal kısıt ağıdır. Tutarlılığı ve en sıkı ima edilen sınırları verimli bir şekilde hesaplanabilmekte, bu da onu planlayıcı ve çizelgeleyicilerde zamansal akıl yürütme için pratik bir çekirdek haline getirmektedir.