𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The power of α-points in preemptive single machine scheduling

✍ Scribed by Andreas S. Schulz; Martin Skutella

Publisher
Springer US
Year
2002
Tongue
English
Weight
143 KB
Volume
5
Category
Article
ISSN
1094-6136

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the NP-hard preemptive single-machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith's ratio rule is to preempt the currently active job whenever a new job arrives that has higher ratio of weight to processing time. We prove that the competitive ratio of this simple on-line algorithm is precisely 2. We also show that list scheduling in order of random -points drawn from the same schedule results in an on-line algorithm with competitive ratio 4 3 . Since its analysis relies on a well-known integer programming relaxation of the scheduling problem, the relaxation has performance guarantee 4 3 as well. On the other hand, we show that it is at best an 8 7 -relaxation.

📜 SIMILAR VOLUMES

Possible and necessary optimality of sol
Possible and necessary optimality of solutions in the single machine scheduling problem with fuzzy parameters
✍ Stefan Chanas; Adam Kasperski 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 386 KB

The single machine scheduling problem with parameters given in the form of fuzzy numbers is considered. It is assumed that the optimal schedule in such a problem cannot be determined precisely (since the parameters of the problem are not known a priori). In this paper the concepts of possible and ne

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.

STRUCTURE-BORNE SOUND TRANSMISSION FROM
STRUCTURE-BORNE SOUND TRANSMISSION FROM MACHINES IN BUILDINGS, PART 2: INDIRECT MEASUREMENT OF FORCE AND MOMENT AT THE MACHINE-RECEIVER INTERFACE OF A SINGLE POINT CONNECTED SYSTEM BY A RECIPROCAL METHOD
✍ S.H. Yap; B.M. Gibbs 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 313 KB

There is increasing evidence that moments are signi®cant contributors in machine induced structure-borne sound. Omission of these components in prediction can therefore lead to an underestimate of total power in some cases, although it is recognised that considering all transmission paths in predict