✦ LIBER ✦

Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals

✍ Scribed by Kacem, Imed; Kellerer, Hans; Lanuel, Yann

Book ID: 120694295
Publisher: Springer US
Year: 2013
Tongue: English
Weight: 189 KB
Volume: 30
Category: Article
ISSN: 1382-6905
DOI: 10.1007/s10878-013-9643-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Maximizing the weighted number of on-tim

Maximizing the weighted number of on-time jobs in single machine scheduling with time windows

✍ C. Koulamas 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 541 KB

The problem of maximizing the weighted number of on-time jobs on a single machine with time windows (STW) is shown to be strongly NP-hard. An efficient. heuristic is presented for STW. Computational experiments indicate that the performance of the heuristic is quite good.

Weighted completion time minimization on

Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability

✍ Imed Kacem; Vangelis Th. Paschos 📂 Article 📅 2013 🏛 Elsevier Science 🌐 English ⚖ 291 KB

Approximation algorithms for the makespa

Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval

✍ Imed Kacem 📂 Article 📅 2007 🏛 Springer US 🌐 English ⚖ 675 KB

Maximizing the weighted number of just-i

Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times

✍ Gur Mosheiov, Dvir Shabtay 📂 Article 📅 2013 🏛 Springer US 🌐 English ⚖ 275 KB

Two simple constant ratio approximation

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

✍ Hans Kellerer; Mikhail A. Kubzin; Vitaly A. Strusevich 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 205 KB

Polynomial time algorithms for minimizin

Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times

✍ Philippe Baptiste 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 102 KB 👁 2 views

We study the problem of minimizing the weighted number of late jobs to be scheduled on a single machine when processing times are equal. In this paper, we show that this problem, as well as its preemptive variant, are strongly polynomial. When preemption is not allowed ( 1"p H "p, r H " w H ; H ), t