Back to Search
Start Over
Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines.
- Source :
- Optimization; Jun2014, Vol. 63 Issue 6, p867-882, 16p
- Publication Year :
- 2014
-
Abstract
- In this paper, we consider semi-online scheduling problems on parallel identical machine system which result from the online scheduling problem for jobs with arbitrary release times by knowing part information of the release times or processing sizes. The conditions are informed that the release times are nondecreasing sequence and the processing lengths are similar inwith. An upper bound of the competitive ratio of List Scheduling (LS) algorithm is given and it is proved that the LS schedule is optimal whenfor any. Furthermore, forwe present a tight bound when. We also show that the competitive ratio of the LS algorithm is improved when additional information is known by letting each job have release time zero. However, if the processing lengths are arbitrary, then no impact on the competitive ratio of the LS algorithm occurs after imposing the additional information. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02331934
- Volume :
- 63
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 96039495
- Full Text :
- https://doi.org/10.1080/02331934.2014.895902