Optimal Tarih Dizisi hakkında Algoritma sorusu...

[mrmarman]

Merhaba..

- Soruyu nasıl ifade edeceğimi oldukça düşündüm. Sorum şöyle...

- Tetris oyununu bir çoğumuz bilirler. Buna benzer bir durum var.

- Farklı boyutlarda yatay çubuklar mevcut.
- Sağa sola kaydırma şansı yok.
- Bu yatay çubukları üste/alta almak şekilde yerlerini değiştirerek en az alana sığdırmak istiyoruz...

- Konu ile ilişkisi ise şöyle oluyor. Çalıştığım servis için bir yazılım hazırlıyorum. Bir aylık dönem ve yapılacak çekimler var. Bu bir ay içinde yapılacak işler için tarihsel dilimler halinde -çoğunluğu çakışan- iş istekleri var.

Kod: Tümünü seç

"01.01.2006'dan 10.01.2006'ya kadar", 
"08.01.2006'dan 13.01.2006'ya kadar",
"15.01.2006'dan 21.01.2006'ya kadar",
"16.01.2006'dan 20.01.2006'ya kadar",
"18.01.2006'dan 24.01.2006'ya kadar",

gibi..

- Bu iş isteklerini en az satırda en çok iş yapmak üzere optimize etmek üzere çalışıyorum.

- Aslında grafik olarak görünce daha iyi anlayacaksınız...


- Bu konuda fikirlerini paylaşacak herkes için şimdiden teşekkürler...

[Kuri_YJ]

Selamlar,

Kasdettiğini pek anlayamadım

Aynı sütun üzerindeki bilgileri, yukarı yada aşağı kaydıramaktan mı bahsediyorsun.

Şöyle, mantıksal olarak şekillerini ifade edersen yardımcı olabiliriz belki.

Örnek ;

Kod: Tümünü seç

  S1 
  01 DD
  02 DD
  03 DD
  04 
  05
  06
  07 AA
  08 AA

bu şekli

Kod: Tümünü seç

  S1 
  01 DD
  02 DD
  03 DD
  04 AA
  05 AA
  06 BB
  07 BB
  08 

Şekline dönüştürmek gibi. Yani tam anlayamadım. Biraz daha açarak örneklersen iyi olur.

Kolay Gelsin

[bluekid]

sanırım bu işler için doğrusal programlama -lineer programming- kullanılıyor.
wikipediadan bakılınca
http://en.wikipedia.org/wiki/Linear_programming
http://en.wikipedia.org/wiki/Job-shop_problem
http://www-unix.mcs.anl.gov/otc/Guide/f ... g-faq.html
daha da olmadı non-lineerprogramming -problemin durumuna göre-
kolay gelsin..

[tuanna]

muharrem hocam resme bakınca bir sey söleyebilecem sorun su çalışan saaatleri çıkararak sutunları tam boşaltmak veya tam doldurmak istiyorsun...

bunu belirlerkende çekimin süresi önemli oluyor....

verilen çekimlerinin artık saat vey agün bazında hesağlayıp ona göre boş yerleştirmeyi düşünsen...
tetristeki gibi bu çekim su şekil bunu koyabileceğim en uygun boşluk ?...
kolay gelsin...

[mrmarman]

@Kuri_YJ

- Doğru ifade etmek için uygun örneği aramakta zorlanmıştım. Böyle anlaman doğal. Malesef öyle olsa işim çok kolay olacaktı.

- Tetris gibi dediğim zaman bunun yatay düzlemde olduğunu belirtmeyi atlamışım...

- Şöyle düşünün, verdiğim resim linkindeki tabloyu saatin ters yönünde rotate edince 1 numaralı sütun en alta gelecek, 2 numaralı sütun onun bir üzerine ... Sütunlar satır olacak...

- Bu son durumda Tetris örneği uygun oluyor... Tarihler sabitlendiğinden sağa sola (yani tarihlerle oynama yapmak) imkanı yok...

@bk

- Verdiğin linkler güzel, özellikle üçüncüsü. Çünkü diğer ikisi aritmetik ağırlıklı ve mevcut dizilimin kalitesini veriyor. Benim combinasyonlar halinde dizilimi hazırlayıp mattrix'i bu ilk iki linkteki formül dizisi ile sorgulamak gerekiyor.

- Bunu zaten en az satır/sütun ilişkisine ulaştığımız hali şeklinde sorgulayabiliyoruz.. Matematikçiler ile Mühendisler arasındaki fark bu olmalı. Birisi sorgular ve ispat eder, diğeri uygulayarak hayata geçirir.

@tuanna

- Sütunların oluşması zaten sıradaki iş isteğinin ürünü. Yani bir istek geldiğinde. İlk sütundan son sütuna kadar bakılıyor.

- İlgili isteğe ait tarhlerde yer varsa -ilk sütunda da olabilir, ikinci hatta son sütunda da- yerleşiyor, eğer hiçbirinde yoksa en sona yeni bir sütun açılıp oraya yerleşiyor.

- Mantık olarak uygun yerler gibi görünse de, örnekte gördüğün üzere yer değişimi ile damlalar halindeki işgücü kaybını bir araya getirip kazanmaya çalışıyorum.

- Bu program bizim servisin yeni şefi olacak anlayacağın. Yoksa bunu zaten insan zekası kolayca hallediyor..

[mege]

http://www.devexpress.com/Products/VCL/ExScheduler/

zaman çakışmalarını tespit eden eventları varmış, sadece demosunu incelemiştim zamanında. ui için faydalı olabilir. tamam biraz pahalı

[mrmarman]

Sağol @mege Zaman çakışmalarını tespit etmekte zorlanmadım. Zaten istek yapılan işleri sırayla karşılaştırdığımdan basit bir SQL sorgusu yetiyor...

örnek SQL.

- BasT ve BitT tarihleri program (iş) başlama ve bitiş tarihleri olsun.

- Bahsi geçen tarihler aralığı ise sütundaki her program için başlangıç ve bitiş tarihleri olsun...

P.S. : H : Hareket (iş isteği) tablosu, parametrik değişkenler ise sıradaki iş isteği başlangıç ve bitiş tarihleri...

Kod: Tümünü seç

    SQL.Add('     WHERE (    :d1 BETWEEN H.BasT and H.BitT ) OR (    :d2 BETWEEN  H.BasT and H.BitT )');
    SQL.Add('     AND   ( H.BasT BETWEEN    :d3 and    :d4 ) OR ( H.BitT BETWEEN     :d5 and    :d6 )');

- Başlama tarihi ile bitiş tarihi, bahsi geçen tarihler arasında olanlar ile bahsi geçen tarihler, başlama tarihi ile bitiş tarihi arasında olanları seçilir.

- Böylece tüm günleri bahsi geçen tarih içinde olan istekler ve herhangi bir gün veya aralığı bu bahsi geçen tarihler arasına denk gelen programlar (işler) seçilmiş oluyor...

- Gördüğünüz tablodaki iş dağılımını sergileyen sistem böyle kurmuştum. Şimdi kurulu bu sistemi yer değişikliği ile minimum ekibe düşürmem lazım.

- Her ihtimale karşı mouse ile tutup taşıma ve yerdeğiştirme opsiyonumu hazırladım. Ola ki bunu başaramam, eldeki kuş daldaki kuş misali...

[Kuri_YJ]

Selamlar,

Hocam yakınlarda bir yerde olaydın da yüzyüze görebilseydik sorunu. Ben çok bir şey anlayamadım, konsantre olamadım belki de.

Neyse bir ara yine bakarım.

Kolay Gelsin

[mrmarman]

- Bu soruyu ilerde karşılaşabileceğini bir sorun gibi düşünün.

- Alternatif çözümümü sunabildiğim sürece kendimi sıkıntıya sokmam zaten ki şimdi de böyle yapıcam.

- Er geç bunu yapmak isterim. Bu daha sonra maliyet muhasebesi ve iş havuz sistemi için önemli bir kurgu olacak. Bunun için önemsedim ve işi kabul ettim.

- Taahhütlerim arasında zaten bu söylediklerimi koymadım. Zor olacağını biliyordum.

- Aklıma gelen çözümlerden inciler sunayım... İlk faz olarak örnekte -resimde- gördüğünüz tabloyu elde ettik

1. Her iş isteğini sütundaki tek iş kabul edip, diğer işleri sırasıyla aynı sütuna yerleştirip, en az gün artan şeklinde o sütunu tamamlayıp bir sonraki sütuna başlamak...

2. Sırayla her iş etüd edilerek, eğer bir (iş isteği + takip eden boş gün) sayısı sıradaki iş isteğinden -takip eden boş güne bakılmaksızın- büyük ise, ilgili iş isteği ile sorgulanan iş isteği yer değiştirilir. Bu işlem değişiklik yapılmayana kadar sürer...

- Bu iki metod üzerinde yoğunlaştım...