✦ LIBER ✦

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

✍ Scribed by Y.M. Shafransky; V.A. Strusevich

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 186 KB
Volume: 45
Category: Article
ISSN: 0894-069X
DOI: 10.1002/(sici)1520-6750(199810)45:7<705::aid-nav4>3.0.co;2-f

No coin nor oath required. For personal study only.

✦ Synopsis

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 allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5 4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme.

📜 SIMILAR VOLUMES

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 👁 1 views

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

Sequencing of a 9·9 kb Segment on the Ri

Sequencing of a 9·9 kb Segment on the Right Arm of Yeast Chromosome VII Reveals Four Open Reading Frames, includingPFK1, the Gene Coding for Succinyl-CoA Synthetase (β-chain) and Two ORFs Sharing Homology with ORFs of the Yeast Chromosome VIII

✍ GUERREIRO, PAULO; AZEVEDO, DULCE; BARREIROS, TANIA; RODRIGUES-POUSADA, CLAUDINA 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 311 KB 👁 2 views

A 9•9 kb DNA fragment from the right arm of chromosome VII of Saccharomyces cerevisiae has been sequenced and analysed. The sequence contains four open reading frames (ORFs) longer than 100 amino acids. One gene, PFK1, has already been cloned and sequenced and the other one is the probable yeast gen