Operations Research Transactions >
2015 , Vol. 19 >Issue 4: 121 - 126
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2015.04.012
On-line algorithms for incompatible job families on parallel machines scheduling with lookahead
Received date: 2014-12-01
Online published: 2015-12-15
We consider the on-line scheduling of incompatible unit-length job families on unbounded parallel-batch machines with lookahead when the number of
job families is equal to the number of machines. In this paper online means that jobs arrive over time. The objective is to minimize the makespan. In the lookahead model, at a time instant t , an on-line algorithm can foresee the information of all jobs arriving in the time segment (t,t+\beta). By incompatible job
families, we mean that jobs from different families cannot be assigned together in the same batch. When \beta \geq 1, we provide an optimal online algorithm; When 0\leq \beta < 1, we give a best possible online algorithm of competitive ratio 1+\alpha, where \alpha is the positive root of the equation \alpha^{2}+(1+\beta) \alpha+\beta-1=0. We also provide a new lower bound on the competitive ratio for dense-algorithms, and present a best possible dense-algorithm matching this lower bound.
LI Wenhua, CHAI Xing, YUAN Hang, YANG Sufang . On-line algorithms for incompatible job families on parallel machines scheduling with lookahead[J]. Operations Research Transactions, 2015 , 19(4) : 121 -126 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.04.012
/
| 〈 |
|
〉 |