Online Bi-Criteria Scheduling on Batch Machines with Machine Costs

Wenhua Li, Weina Zhai and Xing Chai
Additional contact information
Wenhua Li: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
Weina Zhai: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
Xing Chai: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China

Mathematics, 2019, vol. 7, issue 10, 1-11

Abstract: We consider online scheduling with bi-criteria on parallel batch machines, where the batch capacity is unbounded. In this paper, online means that jobs’ arrival is over time. The objective is to minimize the maximum machine cost subject to the makespan being at its minimum. In unbounded parallel batch scheduling, a machine can process several jobs simultaneously as a batch. The processing time of a job and a batch is equal to 1. When job J j is processed on machine M i , it results cost c i j . We only consider two types of cost functions: c i j = a + c j and c i j = a · c j , where a is the fixed cost of machines and c j is the cost of job J j . The number of jobs is n and the number of machines is m . For this problem, we provide two online algorithms, which are showed to be the best possible with a competitive ratio of ( 1 + β m , ⌈ n m ⌉ ) , where β m is the positive root of the equation ( 1 + β m ) m + 1 = β m + 2 .

Keywords: bi-criteria scheduling; online algorithm; makespan; maximum machine cost; competitive ratio (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/10/960/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/10/960/ (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:7:y:2019:i:10:p:960-:d:275974

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 ().