Online Batch Scheduling of Simple Linear Deteriorating Jobs with Incompatible Families

Wenhua Li, Libo Wang, Xing Chai and Hang Yuan
Additional contact information
Wenhua Li: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
Libo Wang: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
Xing Chai: College of Science, Henan University of Technology, Zhengzhou 450001, China
Hang Yuan: Department of Economics, State University of New York at Binghamton, Binghamton, NY 13902, USA

Mathematics, 2020, vol. 8, issue 2, 1-12

Abstract: 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 .

Keywords: online algorithm; batch scheduling; linear deterioration; job families; competitive ratio (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/2/170/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/2/170/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:2:p:170-:d:315117

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().