✦ LIBER ✦

The Expected Competitive Ratio for Weighted Completion Time Scheduling

✍ Scribed by Alexander Souza; Angelika Steger

Publisher: Springer
Year: 2005
Tongue: English
Weight: 222 KB
Volume: 39
Category: Article
ISSN: 1433-0490
DOI: 10.1007/s00224-005-1261-z

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Scheduling to minimize the total weighte

Scheduling to minimize the total weighted completion time with a constraint on the release time resource consumption

✍ A. Janiak; C.-L. Li 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 475 KB

Quality of move-optimal schedules for mi

Quality of move-optimal schedules for minimizing total weighted completion time

✍ Tobias Brueggemann; Johann L. Hurink; Walter Kern 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 184 KB

We study the minimum total weighted completion time problem on identical machines. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio 3 2 . In a special case, the approximation ratio

Algorithms for the single machine total

Algorithms for the single machine total weighted completion time scheduling problem with release times and sequence-dependent setups

✍ Fuh-Der Chou; Hui-Mei Wang; Tzu-Yun Chang 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 275 KB

Scheduling to minimize the weighted sum

Scheduling to minimize the weighted sum of completion times with secondary criteria

✍ Richard N. Burns 📂 Article 📅 1976 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

Polynomial-time approximation scheme for

Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

✍ T.C. Edwin Cheng; Qingqin Nong; Chi To Ng 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB 👁 1 views

A note on the single-machine scheduling

A note on the single-machine scheduling problem with minimum weighted completion time and maximum allowable tardiness

✍ Suresh Chand; Hans Schneeberger 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB

This paper analyzes the Smith-heuristic for the single-machine scheduling problem where the objective is to minimize the total weighted completion time subject to the constraint that the tardiness for any job does not exceed a prespecified maximum allowable tardiness. We identify several cases of th