✦ LIBER ✦

Time complexity and linear-time approximation of the ancient two-machine flow shop

✍ Scribed by Günter Rote; Gerhard J. Woeginger

Publisher: Springer US
Year: 1998
Tongue: English
Weight: 87 KB
Volume: 1
Category: Article
ISSN: 1094-6136
DOI: 10.1002/(sici)1099-1425(1998100)1:3<149::aid-jos10>3.0.co;2-4

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the scheduling problems F2 "" C and F2"no-wait"C , i.e. makespan minimization in a two-machine flow shop, with and without no wait in process. For both problems solution algorithms based on sorting with O(n log n) running time are known, where n denotes the number of jobs. [1,2].

We prove that no asymptotically faster algorithms can solve these problems. This is done by establishing (n log n) lower bounds in the algebraic computation tree model of computation. Moreover, we develop for every '0 approximation algorithms with linear running time O(n log(1/ )) that deliver feasible schedules whose makespan is at most 1# times the optimum makespan.

📜 SIMILAR VOLUMES

Asymptotically optimal linear time algor

Asymptotically optimal linear time algorithms for two-stage and three-stage flexible flow shops

✍ Christos Koulamas; George J. Kyparisis 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

Direct numerical simulation of a turbule

Direct numerical simulation of a turbulent channel flow with a linear spanwise nonuniformity of time-mean temperature (Examination of the turbulence statistics)

✍ Koji Matsubara; Mutsuo Kobayashi; Hiroshi Maekawa; Kenjiro Suzuki 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB 👁 1 views

Direct numerical simulation (DNS) was performed for a turbulent channel flow with the time-mean temperature linearly varying in the spanwise direction. Spanwise heat transfer in wall turbulence was explored in this simple case where the turbulent heat flux has only a spanwise component. The computed