| author: | Angelelli, Enrico, Speranza, Maria Grazia, and Tuza, Tsolt |
|---|---|
| title: | New bounds and algorithms for on-line scheduling: two identical processors, known sum and upper bound on the tasks |
| keywords: | semi on-line scheduling, parallel processors, competitive analysis |
| abstract: | In this paper we study a semi on-line version of the classical multiprocessor scheduling problem on two identical processors. We assume that the sum of the tasks and an upper bound gamma on the size of each task are known. Each task has to be assigned upon arrival and the assignment cannot be changed later. The objective is the minimization of the maximum completion time on the processors. In this paper we propose new algorithms and improve known lower and upper bounds on the competitive ratio. Algorithms and bounds depend on the value of gamma. An optimal algorithm is obtained for gamma in the interval [ 1/n,2(n+1)/n(2n+1) ] and gamma = (2n-1)/2n(n-1), where n is any integer value larger or equal 2. |
| If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. | |
| reference: | Angelelli, Enrico and Speranza, Maria Grazia, and Tuza, Tsolt (2006), New bounds and algorithms for on-line scheduling: two identical processors, known sum and upper bound on the tasks, Discrete Mathematics and Theoretical Computer Science 8, pp. 1-16 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dm080101.ps.gz (255 K) |
| ps-source: | dm080101.ps (945 K) |
| pdf-source: | dm080101.pdf (538 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.