𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On complexity of minimizing weighted number of late jobs in unit time open shops

✍ Scribed by A.A. Gladky

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
295 KB
Volume
74
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the problem of minimizing the weighted number of late jobs in open shop with given release dates and unit time operations is strongly .I '?-hard. The complexity status of this problem was unknown.

πŸ“œ SIMILAR VOLUMES

Open shop scheduling to minimize the num
Open shop scheduling to minimize the number of late jobs
✍ Christos Koulamas; George J. Kyparisis πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 63 KB πŸ‘ 2 views

We develop polynomial algorithms for several cases of the NP-hard open shop scheduling problem of minimizing the number of late jobs by utilizing some recent results for the open shop makespan problem. For the two machine common due date problem, we assume that either the machines or the jobs are or

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