Online Batch Scheduling of Simple Linear Deteriorating Jobs with Incompatible Families

We considered the online scheduling problem of simple linear deteriorating job families on m parallel batch machines to minimize the makespan, where the batch capacity is unbounded. In this paper, simple linear deteriorating jobs mean that the actual processing time p j of job J j is assumed to be a...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics (Basel) 2020-02, Vol.8 (2), p.170
Main Authors: Li, Wenhua, Wang, Libo, Chai, Xing, Yuan, Hang
Format: Article
Language:English
Subjects:
batch scheduling
competitive ratio
job families
linear deterioration
online algorithm
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We considered the online scheduling problem of simple linear deteriorating job families on m parallel batch machines to minimize the makespan, where the batch capacity is unbounded. In this paper, simple linear deteriorating jobs mean that the actual processing time p j of job J j is assumed to be a linear function of its starting time s j , i.e., p j = α j s j , where α j > 0 is the deterioration rate. Job families mean that one job must belong to some job family, and jobs of different families cannot be processed in the same batch. When m = 1 , we provide the best possible online algorithm with the competitive ratio of ( 1 + α max ) f , where f is the number of job families and α max is the maximum deterioration rate of all jobs. When m ≥ 1 and m = f , we provide the best possible online algorithm with the competitive ratio of 1 + α max .
ISSN:2227-7390
2227-7390
DOI:10.3390/math8020170