✦ LIBER ✦

Open shop scheduling to minimize the number of late jobs

✍ Scribed by Christos Koulamas; George J. Kyparisis

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 63 KB
Volume: 45
Category: Article
ISSN: 0894-069X
DOI: 10.1002/(sici)1520-6750(199808)45:5<525::aid-nav6>3.0.co;2-5

No coin nor oath required. For personal study only.

✦ Synopsis

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 ordered. For the m machine common due date problem, we assume that one machine is maximal and impose a restriction on its load.

📜 SIMILAR VOLUMES

A note on the complexity of family sched

A note on the complexity of family scheduling to minimize the number of late jobs

✍ T. C. Edwin Cheng; Zhaohui Liu; Yakov M. Shafransky 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 65 KB 👁 2 views

The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and pro

Note: Open-shop scheduling with release

Note: Open-shop scheduling with release dates to minimize maximum lateness

✍ Hans Kellerer; Thomas Tautenhahn; Gerhard Woeginger 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 295 KB 👁 1 views

We present the first polynomial-time algorithm for an open-shop problem with unit execution times, arbitrary release dates, and due dates. The objective is to minimize maximum lateness. 0 I995 John Wiley & Sons. Inc.

Scheduling on a single machine with a si

Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs

✍ I. Adiri; E. Frostig; A. H. G. Rinnooy Kan 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 412 KB 👁 2 views

The open shop scheduling problem with a

The open shop scheduling problem with a given sequence of jobs on one machine

✍ Y.M. Shafransky; V.A. Strusevich 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB 👁 2 views

The paper considers the open shop scheduling problem to minimize the makespan, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not a

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