Algoritma perkiraan waktu polinomial untuk penjadwalan mesin: berapa banyak masalah terbuka yang tersisa?

22

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.

Dai Le
sumber
Saya rasa ini tidak perlu dilakukan CW ...
Suresh Venkat
@ Surur Venkat: Bagaimana cara menghapus CW?
Oleksandr Bondarenko
Sayangnya, tidak ada cara untuk mengubah pertanyaan wiki komunitas menjadi pertanyaan non-CW. Menambahkan fitur ini ke mesin Stack Exchange diminta di: meta.stackexchange.com/questions/6821/…
Tsuyoshi Ito
Lihat juga FAQ tentang kapan harus menggunakan tag CW: meta.cstheory.stackexchange.com/questions/225/…
Suresh Venkat

Jawaban:

16

Makespan minimalisasi pada mesin yang identik di bawah kendala prioritas

Terbuka masalah 1. Sediakan hasil inapproximability untuk P | p r e c | C m a x .4/3+δP|prec|Cmax

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

"jika masalah mesin tunggal sulit diperkirakan dalam faktor maka masalah mesin paralel yang dipertimbangkan, bahkan dalam kasus waktu pemrosesan unit, sulit untuk diperkirakan dalam faktor 2 - ζ , di mana ζ cenderung 0 karena ϵ cenderung ke 0. "2ϵ2ζζϵ

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(273p+1)P|prec,pj=1|Cmax , di manapadalah jumlah mesin.22pp

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|CmaxPm|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|CmaxP|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

Buka masalah 7. Putuskan apakah ada algoritma perkiraan waktu polinomial untuk yang kinerjanya terburuk adalah independen dari jumlah m mesin dan / atau independen dari jumlah maksimum μ operasi. Menyediakan 5 / 4 + δ hasil inapproximability untuk J | | C m a x . Memberikan hasil yang tidak dapat diperkirakan untuk J | | C m sebuah x yang nilainya tumbuh dengan jumlah mJ||Cmaxmμ5/4+δJ||CmaxJ||Cmaxm mesin hingga tak terbatas.

Mendesain PTAS untuk untuk kasus di mana μ adalah bagian dari input; atau menyangkal keberadaan PTAS seperti itu di bawah P NP.J2||Cmaxμ

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||CmaxO((loglb)1ϵ)NPZTIME(2lognO(1/ϵ))J2||Cmaxtidak memiliki PTAS kecuali .NPDTIME(nO(logn))

Total waktu penyelesaian pekerjaan tanpa kendala diutamakan

Total waktu penyelesaian pekerjaan di bawah kendala diutamakan

Buka masalah 9. Buktikan bahwa dan 1 | p r e c | Σ w j C j tidak punya waktu algoritma pendekatan polinomial dengan kinerja jaminan 2 - ε kecuali P = NP.1|prec|Cj1|prec|wjCj2ϵ

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

Masalah terbuka 10. Desain algoritma perkiraan waktu polinomial dengan jaminan kinerja konstan untuk dan untuk P | p m t n ; r j | F j .1|pmtn;rj|wjFjP|pmtn;rj|Fj

O(1)1|pmtn;rj|wjFjO(1)

Ω(logPloglogP)P|pmtn;rj|FjΩ(logPloglogP)

Oleksandr Bondarenko
sumber