𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by T. C. Edwin Cheng; Zhaohui Liu; Yakov M. Shafransky

Publisher
Springer US
Year
2001
Tongue
English
Weight
65 KB
Volume
4
Category
Article
ISSN
1094-6136

No coin nor oath required. For personal study only.

✦ Synopsis

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 processing times are one unit.

📜 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

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

How to determine the number of inner-sph
How to determine the number of inner-sphere water molecules in Lanthanide(III) complexes by 17O NMR spectroscopy. A technical note
✍ Kristina Djanashvili; Joop. A. Peters 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB

## Abstract Lanthanide(III) complexes of polyaminocarboxylates are widely used in MRI as contrast agents. The paramagnetic properties of the metal ion contribute to the increase of ^1^H relaxation rates, while the chelate offers a stable binding with the metal. The number of water molecules, coordi

Kurzgefässter Lehre v. d. Knochenbrüchen
Kurzgefässter Lehre v. d. Knochenbrüchen mit besonderer Berücksichtigung ihrer Mechanik u. Biologie (A summary of the teaching concerning Fractures, with special reference to Mechanics and Biology). Edited Dr. F. de QUervain, with the assistance of Dr. Th. Christen and Dr. H. Iselin; founded on the notes of the late Dr. H. Zuppinger Part I. Pp. 140, with 123 illustrations, and with portrait of Dr. Hermann Zuppinger. 1913. Leipzig: F. C. W. Vogel. Price 9 marks
📂 Article 📅 1914 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 1 views

REVIEW9 AND NOTICES OF BOOKS 187 described, with careful histological descriptions and drawings. The distinction of cardiac, pulmonary, and cerebral types of symptom-groups is a good one, and there can be no doubt that the nature of many of these cases must be overlooked nowadays, or mistaken for so