Pada tahun 1999, Petra Schuurman dan Gerhard J. Woeginger menerbitkan makalah "Algoritma perkiraan waktu polinomial untuk penjadwalan mesin: Sepuluh masalah terbuka" . Sejak itu, sejauh yang saya ketahui, ulasan yang menyangkut daftar masalah yang sama belum muncul. Dengan demikian akan sangat bagus dan bermanfaat jika kita masing-masing dapat membuat ringkasan tentang beberapa dari sepuluh masalah terbuka dan berkontribusi di sini.
22
Jawaban:
Makespan minimalisasi pada mesin yang identik di bawah kendala prioritas
Inilah yang terlintas dalam pikiran saya adalah makalah tahun ini oleh Ola Svensson "Kekerasan Bersyarat dari Presedensi Terjadwal Penjadwalan pada Mesin Identik". Dalam makalahnya, Ola membuktikan hal itu
Pada tahun 2008 ada diterbitkan kertas "Precedence dibatasi penjadwalan di · optimal "menggambarkan suatu algoritma untukP|prec,pj=1|Cmaxdengan rasio kinerja, disebutkan dalam judulnya. Ini meningkat pada algoritma Coffman-Graham dengan batas2-2(2−73p+1) P|prec,pj=1|Cmax , di manapadalah jumlah mesin.2−2p p
Makalah "Algoritma aproksimasi untuk menjadwalkan pekerjaan dengan batasan rantai prioritas" oleh Jansen dan Solis-Oba berisi PTAS untuk , dan, sebagai konsekuensinya, untuk P m | c h a i n s | C m a x sebagai kasus khusus dari mantan masalah.Qm|chains|Cmax Pm|chains|Cmax
Tahun ini muncul artikel "Skema perkiraan untuk penjadwalan pekerjaan dengan batasan rantai prioritas" oleh Jansen dan Solis-Oba (versi jurnal yang sebelumnya), yang menyangkut PTAS untuk dengan jumlah tetap pekerjaan di setiap rantai dan P | p r e c | C m a x dengan sejumlah konstan pekerjaan dalam komponen terhubung setiap order.P|chains|Cmax P|prec|Cmax
Makespan minimalisasi pada mesin yang seragam di bawah kendala prioritas
Makalah tahun 2003 "Algoritma aproksimasi untuk penjadwalan pekerjaan dengan batasan rantai prioritas" oleh Jansen dan Solis-Oba berisi PTAS untuk .Qm|chains|Cmax
Makespan minimalisasi di bawah batasan prioritas dengan keterlambatan komunikasi
Makespan minimalisasi pada mesin yang tidak terkait
Makespan minimisasi di toko terbuka
Makespan minimalisasi di toko aliran
Dalam makalah Nagarajan dan Sviridenko dari 2008 "Batas Ketat untuk Penjadwalan Toko Alur Permutasi" kita dapat menemukan batas atas pada rasio antara makespan optimal dan makespan dari jadwal permutasi terbaik. Batas ini adalah rasio perkiraan dari suatu algoritma yang diusulkan, dan itu adalah yang terbaik di antara algoritma berdasarkan batas bawah sepele, hingga faktor. Kebetulan, algoritma yang diusulkan saat ini adalah yang dengan rasio perkiraan terbaik.22–√
Makespan minimisasi di job shop
Disertasi oleh Svensson "Perkiraan Beberapa Grafik Klasik dan Masalah Penjadwalan" berisi hasil yang menunjukkan bahwa tidak dapat diperkirakan dalam waktu O ( ( log l b ) 1 - ε ) dengan asumsi N P ⊆ Z T I M E ( 2 log n O ( 1 / ε ) ) dan bahwa J 2 | | C m a xJ||Cmax O((loglb)1−ϵ) NP⊆ZTIME(2lognO(1/ϵ)) J2||Cmax tidak memiliki PTAS kecuali .NP⊆DTIME(nO(logn))
Total waktu penyelesaian pekerjaan tanpa kendala diutamakan
Total waktu penyelesaian pekerjaan di bawah kendala diutamakan
Dalam "Tes kode panjang optimal dengan satu bit gratis" Bansal dan Khot membuktikannya, tetapi dengan asumsi varian baru dari dugaan game unik.
Kriteria waktu mengalir
sumber
Halaman web ini mungkin memiliki beberapa informasi penggunaan:
http://www.mathematik.uni-osnabrueck.de/research/OR/class/
sumber