Back to University of Twente portal
Special cases of online parallel job scheduling
Hurink, Johann L. and Paulus, Jacob Jan (2007) Special cases of online parallel job scheduling. [Report]
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 205Kb |
| Abstract: | In this paper we consider the online scheduling of jobs, which require processing on a number of machines simultaneously. These jobs are presented to a decision maker one by one, where the next job becomes known as soon as the current job is scheduled. The objective is to minimize the makespan. For the problem with three machines we give a 2.8-competitive algorithm, improving upon the 3-competitive greedy algorithm. For the special case with arbitrary number of machines, where the jobs appear in non-increasing order of machine requirement, we give a 2.4815-competitive algorithm, improving the 2.75-competitive greedy algorithm. |
| Item Type: | Report |
| Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |
| Research Group: | |
| Link to this item: | http://purl.utwente.nl/publications/64518 |
| Publisher URL: | http://beta.ieis.tue.nl/node/1185 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page
Metis ID: 245844