✦ LIBER ✦

A simple semi on-line algorithm for P2//Cmax with a buffer

✍ Scribed by Guochuan Zhang

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 355 KB
Volume: 61
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00006-9

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we investigate a semi on-line version of the parallel machine scheduling problem. We are given a buffer of length k which is available to maintain k jobs. The jobs arrive one by one and can be temporarily assigned to the buffer if the buffer is not full. The goal is to assign all jobs to the identical machines such that the makespan is minimized. For two machines, Kellerer et al. ( 1995) showed that no heuristic for this problem can have a worst-case ratio lower than 4/3. This paper presents a simple algorithm with worst-case ratio 4/3 for PZ//C max with a buffer of length 1. @

📜 SIMILAR VOLUMES

b9000A 14 approximate algorithm for P2/t

b9000A 14 approximate algorithm for P2/tree/Cmax

✍ Giorgio Gallo; Fulvio Piccinonno 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 766 KB

We consider the problem of scheduling a set of tasks whose precedence relation is representable as a directed forest, on two identical machines, in order to minimize the total completion time. A new heuristic algorithm is presented which provides a l/4 approximate solution. This algorithm is based o

A scheduling algorithm for flexible flow

A scheduling algorithm for flexible flow lines with limited intermediate buffers

✍ Sawik, Tadeusz J. 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 681 KB

A simple algorithm for on-line predictio

A simple algorithm for on-line prediction of BOD5 by a microprocessor-based system

✍ Roni Raviv; Sam Ben-Yaakov 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 509 KB

A comment on “A simple sequencing algori

A comment on “A simple sequencing algorithm for mixed-model assembly lines in just-in-time production systems”

✍ Julian Scott Yeomans 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 215 KB

On a Shooting Algorithm for Sturm-Liouvi

On a Shooting Algorithm for Sturm-Liouville Eigenvalue Problems with Periodic and Semi-periodic Boundary Conditions

✍ Xingzhi Ji 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 266 KB

This paper is concerned with the eigenvalues of Sturm-Liouville problems with periodic and semi-periodic boundary conditions to be approximated by a shooting algorithm. The proposed technique is based on the application of the Floquet theory. Convergence analysis and a general guideline to provide s

(p − 1)(p + 1)-approximate algorithms fo

(p − 1)(p + 1)-approximate algorithms for p-traveling salesmen problems on a tree with minmax objective

✍ Igor Averbakh; Oded Berman 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 950 KB

Suppose p traveling salesmen must visit together all points/nodes of a tree, and the objective is to minimize the maximum of lengths of their tours. For location allocation problems (where both optimal home locations of the salesmen and their tours must be found), which are NP-complete, fast polynom